learn.ifs.name

Words and Tokens

Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 2

33 cards in “2.6 Regular expressions” · whole deck

2.6 Regular expressions

  1. What is a regular expression, formally and practically?
    Formally, an algebraic notation for characterizing a set of strings. Practically, a pattern language for searching text and specifying changes to it; used in grep, editors, every programming language, and BPE pretokenization.
  2. What does Python’s re.search(pattern, string) return?
    The first match of the pattern inside the string.
  3. Why are regexes in Python usually written as raw strings, r"..."?
    In raw strings backslashes are treated literally, so regex escapes like \b or \d reach the regex engine unchanged.
  4. What do square brackets do in a regex? Give examples.
    Character disjunction: match any one of the characters inside. [mM]ary matches Mary or mary; [abc] matches a, b or c.
  5. What does a dash inside brackets mean, as in [b-g]?
    A range: any one character from b to g. [A-Z] is an uppercase letter, [0-9] a digit.
  6. What does [^a] mean, and when does ^ inside brackets mean something else?
    Any single character except a. The caret negates only when it is the first symbol after [; elsewhere (e.g. [e^]) it is a literal caret.
  7. What does ? mean in a regex? Give an example.
    Zero or one occurrence of the previous character or expression: colou?r matches color and colour.
  8. What is the difference between the Kleene * and Kleene +?
    * means zero or more occurrences of the preceding character or expression; + means one or more.
  9. Write a regex for the sheep language baa!, baaa!, baaaa!, …, and say why ba*! fails.
    baa+! (or baaa*!). ba*! would also match b! and ba!, since * allows zero as.
  10. Why is an integer written [0-9]+ rather than [0-9]*?
    [0-9]* also matches the empty string.
  11. What do {3} and . mean in a regex?
    {3}: exactly 3 occurrences of the previous character or expression (ax{10}z). .: a wildcard matching any single character except newline.
  12. Write a regex to find lines in which the word rose appears twice.
    rose.*rose: .* matches any string of zero or more characters between them.
  13. What are anchors? What do ^ and $ match?
    Special characters that tie a match to a place in the string: ^ matches the start of a line, $ the end. ^The dog\.$ matches a line containing only “The dog.”.
  14. What are the three uses of the caret ^?
    Start of line (anchor), negation as the first symbol inside square brackets, and a literal caret.
  15. What do \b and \B match? Will \b99\b match in “299” and in “$99”?
    \b is a word boundary, \B a non-boundary, where a “word” is a run of letters, digits or underscores. It won’t match inside 299 (99 follows a digit), but will match $99 ($ is not a word character).
  16. What does it mean that anchors and \b are zero-width?
    They match the empty string at a position without consuming characters, so the following characters remain available to match.
  17. Why can’t [catdog] find “cat or dog”, and what should you write?
    Brackets match a single character from the set. Use the disjunction (pipe) operator: cat|dog.
  18. Why doesn’t guppy|ies match both guppy and guppies, and how is it fixed?
    Sequences bind tighter than |, so it means guppy or ies. Use parentheses: gupp(y|ies).
  19. Why does Column [0-9]+ * not match repeated column labels, and how do you fix it?
    The * applies only to the preceding space. Group the whole sequence: (Column [0-9]+ +)*.
  20. Give the regex operator precedence hierarchy, from highest to lowest.
    Parentheses () > counters * + ? {} > sequences and anchors > disjunction |. So the* matches theeee (not thethe), and the|any matches the or any.
  21. What does it mean that regex matching is greedy, and how do you get non-greedy matching?
    Patterns match the largest string they can ([a-z]* on “once upon” matches once). The non-greedy operators *? and +? match as little as possible.
  22. Refine a regex for the article the step by step.
    the misses sentence-initial The → [tT]he, which wrongly matches inside other or there → \b[tT]he\b.
  23. What are false positives and false negatives in pattern matching, and which measures do they correspond to?
    False positives are strings incorrectly matched (other); false negatives are strings incorrectly missed (The). Minimizing false positives increases precision; minimizing false negatives increases recall. The two efforts pull against each other.
  24. What do \d, \w and \s (and their capitals) match?
    \d a digit, \w an alphanumeric character or underscore, \s whitespace. \D, \W, \S are their complements.
  25. How do you match a literal period, star or bracket?
    Escape it with a backslash: \., \*, \[, \\.
  26. What are capture groups? Use one to convert US dates (mm/dd/yyyy) to dd-mm-yyyy.
    Parentheses store what they matched in numbered groups that can be referred to as \1, \2… re.sub(r"(\d{2})/(\d{2})/(\d{4})", r"\2-\1-\3", s) turns 10/15/2011 into 15-10-2011.
  27. Write a regex that finds a repeated word, like “the the”.
    \b([A-Za-z]+)\s+\1\b: capture a word, then require the same text again after whitespace.
  28. What is a non-capturing group, and when is it used?
    (?: pattern ): groups for operator precedence without storing the match, e.g. to repeat a long sub-pattern 14 times but capture only the 15th occurrence.
  29. How does ELIZA use regex substitutions?
    A cascade of substitutions on the uppercased input: first swap pronouns (MY → YOUR, I’M → YOU ARE), then match patterns and rewrite the whole response, e.g. .* YOU ARE (DEPRESSED|SAD) .* → “I AM SORRY TO HEAR YOU ARE \1”.
  30. What are lookahead assertions?
    Zero-width tests on what comes next: (?= pattern) succeeds if the pattern matches, (?! pattern) if it doesn’t, without advancing the match pointer. Negative lookahead is used to rule out special cases.
  31. Write a regex capturing the first word of a line only if it doesn’t start with T or t.
    ^(?![tT])(\w+)\b
  32. What does the GPT-2 pretokenizer regex split “We’re 350 dogs! Um, lunch?” into?
    We · ’re · ␣350 · ␣dogs · ! · ␣Um · , · ␣lunch · ?: contractions split off, words/numbers/punctuation runs separated, leading spaces attached.
  33. What do \p{L} and \p{N} match, and in which Python library?
    Any Unicode letter and any Unicode number (with \P{…} for the complements), in the external regex library, which is more powerful than the built-in re.

Source