Reading 18: Regular Expressions & Grammars

Productions can use operators to combine terminals and nonterminals on the righthand side. The three most important operators in a production expression are:

Repetition, represented by *:

x ::= y*        // x matches zero or more y

Concatenation, represented not by a symbol, but just a space:

x ::= y z       // x matches y followed by z 

Union, also called alternation, represented by |:

x ::= y | z     // x matches either y or z 

By convention, postfix operators like * have highest precedence, which means they are applied first. Concatenation is applied next. Alternation | has lowest precedence, which means it is applied last. Parentheses can be used to override precedence:

m ::= a (b|c) d      // m matches a, followed by either b or c, followed by d
x ::= (y z | a b)*   // x matches zero or more yz or ab pairs

Let’s use these operators to generalize our url grammar to match some other hostnames, such as http://stanford.edu/ and http://google.com/.

url ::= 'http://' hostname '/'
hostname ::= 'mit.edu' | 'stanford.edu' | 'google.com'

The first rule of this grammar demonstrates concatenation. The url nonterminal matches strings that start with the literal string http://, followed by a match to the hostname nonterminal, followed by the literal string /.

The hostname rule demonstrates union. A hostname can match one of the three literal strings, mit.edu or stanford.edu or google.com.

So this grammar represents the set of three strings, http://mit.edu/, http://google.com/, and http://stanford.edu/.

Let’s take it one step further by allowing any lowercase word in place of mit, stanford, google, com and edu:

url ::= 'http://' hostname '/'
hostname ::= word '.' word
word ::= letter*
letter ::= ('a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' 
                | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' 
                | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z')

The new word rule matches a string of zero or more lowercase letters, so the overall grammar can now match http://alibaba.com/ and http://zyxw.edu/ as well. Unfortunately word can also match an empty string, so this url grammar also matches http://./, which is not a legal URL. Here’s a verbose way to fix that, which requires word to match at least one letter.

word ::= letter letter*

We’ll see a simpler way to write word in the next section.

You can also use additional operators which are just syntactic sugar (i.e., they’re equivalent to combinations of the main three operators).

0 or 1 occurrence is represented by ?:

x ::= y?       // an x is a y or is the empty string
               //    equivalent to x ::=   | y
               //                        ^--- note the empty string here

1 or more occurrences is represented by +:

x ::= y+       // an x is one or more y
               //    equivalent to  x ::= y y*

An exact number of occurrences is represented by {n}, and a range of occurences by {n,m}, {n,}, or {,m}:

x ::= y{3}     // an x is three y
               //    equivalent to x ::= y y y 

x ::= y{1,3}   // an x is between one and three y
               //    equivalent to x ::= y | y y | y y y

x ::= y{,4}    // an x is at most four y
               //    equivalent to x ::=   | y | y y | y y y | y y y y
               //                        ^--- note the empty string here

x ::= y{2,}    // an x is two or more y
               //    equivalent to x ::= y y y*

A character class [...] represents the set of single-character strings matching any of the characters listed in the square brackets:

x ::= [aeiou]     // equivalent to  x ::= 'a' | 'e' | 'i' | 'o' | 'u'

Ranges of characters can be described compactly using -:

x ::= [a-ckx-z]   // equivalent to  x ::= 'a' | 'b' | 'c' | 'k' | 'x' | 'y' | 'z'

An inverted character class [^...] represents the set of single-character strings matching a character not listed in the brackets:

x ::= [^a-c]  // equivalent to  x ::= 'd' | 'e' | 'f' | ... | '0' | '1' | ... | '!' | '@'
              //                          | ... (all other possible characters)

These additional operators allow the word production to be expressed more compactly:

url ::= 'http://' hostname '/'
hostname ::= word '.' word
word ::= [a-z]+

How else do we need to generalize? Hostnames can have more than two components, and there can be an optional port number:

http://didit.csail.mit.edu:4949/

To handle this kind of string, the grammar is now:

url ::= 'http://' hostname (':' port)? '/' 
hostname ::= word '.' hostname | word '.' word
port ::= [0-9]+
word ::= [a-z]+

Notice how hostname is now defined recursively in terms of itself. Which part of the hostname definition is the base case, and which part is the recursive step? What kinds of hostnames are allowed?

Using the repetition operator, we could also write hostname without recursion, like this:

hostname ::= (word '.')+ word

Recursion can sometimes be eliminated from a grammar using operators like this, but not always.

Another thing to observe is that this grammar allows port numbers that are not technically legal, since port numbers can only range from 0 to 65535 (2¹⁶-1). We could write a more complex definition of port that would match only these integers, but that’s not typically done in a grammar. Instead, the constraint 0 ≤ port ≤ 65535 would be specified in the program that uses the grammar.

There are more things we should do to go farther:

• generalizing http to support the additional protocols that URLs can have
• generalizing the / at the end to a slash-separated path
• allowing hostnames with the full set of legal characters instead of just a-z

root    ::= integer ('-' integer)+
integer ::= [0-9]+

root   ::= (A B)+
A      ::= [Aa]
B      ::= [Bb]

https://websis.mit.edu/
ftp://ftp.athena.mit.edu/

ptth://web.mit.edu/
mailto:bitdiddle@mit.edu

url ::= protocol '://' hostname (':' port)? '/' 
protocol ::= TODO
hostname ::= word '.' hostname | word '.' word
port ::= [0-9]+
word ::= [a-z]+

Now let’s look at grammars for some file formats. We’ll be using two different markup languages that represent typographic style in text. Here they are:

Markdown:

This is _italic_.

(To learn about Markdown, see the Markdown syntax documentation or Markdown on Wikipedia.)

HTML:

Here is an <i>italic</i> word.

(To learn about HTML, see the HTML Living Standard, or HTML on Wikipedia.)

For simplicity, our example HTML and Markdown grammars will only specify italics, but other text styles are of course possible. Also for simplicity, we will assume the plain text between the formatting delimiters isn’t allowed to use any formatting punctuation, like _ or <.

Here’s the grammar for our simplified version of Markdown:

markdown ::= ( normal | italic ) *
italic ::= '_' normal '_'
normal ::= text
text ::= [^_]*

Here’s the grammar for our simplified version of HTML:

html ::= ( normal | italic ) *
italic ::= '<i>' html '</i>'
normal ::= text
text ::= [^<>]*

Regexes are widely used in programming, and you should have them in your toolbox.

In TypeScript/JavaScript, you can use regexes for manipulating strings (see string.split, string.match, RegExp). They’re built-in as a first-class feature of other modern scripting languages like Python and Ruby, and you can use them in many text editors for find and replace.

In some languages (including TypeScript/JavaScript), regexes have their own literal syntax delimited by forward slashes, /..../. In others (including Python and Java), there is no special syntactic support for regexes, so you just use a quoted string.

Here are some examples of using regexes in TypeScript.

Replace all runs of spaces in a string s with a single space:

const singleSpacedString = s.replace(/ +/g, " ");

Notice the g character in the example above. By default, a regex will only match the first instance in a string. Adding a g character after the regex makes this a “global” pattern which forces it to match all instances in the string.

Match a URL:

if (s.match(/http:\/\/([a-z]+\.)+[a-z]+(:[0-9]+)?\//)) {
    // then s is a url
}

Notice the backslashes in the example above. We want to match a literal period ., so we have to first escape it as \. to protect it from being interpreted as the regex match-any-character operator. Furthermore, we want to match literal forward slashes /, so we also have to escape them as \/ to prevent them from prematurely signalling the end of the regex literal. The frequent necessity for backslash escapes makes regexes less readable.

Extract parts of a date like "2020-03-18":

const s = "2020-03-18";
const regex = /(?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})/;
const m = s.match(regex);
if (m) {
  assert(m.groups);
  const year = m.groups.year;
  const month = m.groups.month;
  const day = m.groups.day;
  // m.groups.name is the part of s that matched (?<name>...)
}

This example uses named capturing groups like (?<year>...) to extract parts of the matched string and assign them names. The (?<name>...) syntax matches the regex ... inside the parentheses, and then assigns name to the string that match. Note that ? here does not mean 0 or 1 repetition. In this context, right after an open parenthesis, the ? signals that these parentheses have special meaning, not just grouping.

Named capturing groups can be retrieved by the groups property after a successful match. If this regex were matched against "2025-03-18", for example, then m.groups.year would return "2025", m.groups.month would return "03", and m.groups.day would return "18".

const input = "The <b>Good</b>, the <i>Bad</i>, and the <strong>Ugly</strong>";
const regex = /TODO/g;
const output = input.replace(regex, "");

const input = "77 Rose Court Ln";
const regex = /[0-9]+ .* (Rd|St|Ave|Ln)/;
const m = s.match(regex);
if (m) {
    ...
}

const houseNumber = m.groups.houseNumber; // should be "77"
const streetName = m.groups.streetName; // should be "Rose Court"
const streetType = m.groups.streetType; // should be "Ln"

In general, a language that can be expressed with our system of grammars is called context-free. Not all context-free languages are also regular; that is, some grammars can’t be reduced to single nonrecursive productions. Our HTML grammar is context-free but not regular.

The grammars for most programming languages are also context-free. In general, any language with nested structure (like nesting parentheses or braces) is context-free but not regular. That description applies to the TypeScript grammar, shown here in part:

statement ::= 
  '{' statement* '}'
| 'if' '(' expression ')' statement ('else' statement)?
| 'for' '(' forinit? ';' expression? ';' forupdate? ')' statement
| 'while' '(' expression ')' statement
| 'do' statement 'while' '(' expression ')' ';'
| 'try' '{' statement* '}' ( catches | catches? 'finally' '{' statement* '}' )
| 'switch' '(' expression ')' '{' switchgroups '}'
| 'return' expression? ';'
| 'throw' expression ';' 
| 'break' label? ';'
| 'continue' label? ';'
| expression ';' 
| label ':' statement
| ';'