Reading 17: 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 ::= ('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 ::= ('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')
         ('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')*

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

1 or more occurrences is represented by +:

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

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

x ::= [aeiou]  is equivalent to  x ::= 'a' | 'e' | 'i' | 'o' | 'u'
x ::= [a-c]    is equivalent to  x ::= 'a' | 'b' | 'c'

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

x ::= [^a-c] is equivalent to  x ::= 'd' | 'e' | 'f' 
                                         | ... (all other 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. 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 W3C HTML specification, WHATWG HTML 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 Java, you can use regexes for manipulating strings (see String.split, String.matches, java.util.regex.Pattern). They’re built-in as a first-class feature of modern scripting languages like Python, Ruby, and JavaScript, and you can use them in many text editors for find and replace. Regular expressions are your friend! Most of the time. Here are some examples.

Replace all runs of spaces with a single space:

String singleSpacedString = string.replaceAll(" +", " ");

Match a URL:

Pattern regex = Pattern.compile("http://([a-z]+\\.)+[a-z]+(:[0-9]+)?/");
Matcher m = regex.matcher(string);
if (m.matches()) {
    // then string is a url
}

Extract part of an HTML tag:

Pattern regex = Pattern.compile("<a href=\"([^\"]*)\">");
Matcher m = regex.matcher(string);
if (m.matches()) {
    String url = m.group(1); 
    // Matcher.group(n) returns the nth parenthesized part of the regex
}

Notice the backslashes in the URL and HTML tag examples. In the URL example, 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, and then we have to further escape it as \\. to protect the backslash from being interpreted as a Java string escape character. In the HTML example, we have to escape the quote mark " as \" to keep it from ending the string. The frequent necessity for backslash escapes makes regexes still less readable.

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

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 Java 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 '}'
| 'synchronized' '(' expression ')' '{' statement* '}'
| 'return' expression? ';'
| 'throw' expression ';' 
| 'break' identifier? ';'
| 'continue' identifier? ';'
| expression ';' 
| identifier ':' statement
| ';'