Reading 17: Regular Expressions & Grammars

The three most important operators in a production expression are:

• concatenation, represented not by a symbol, but just a space:

x ::= y z     an x is a y followed by a z 

• repetition, represented by *:

x ::= y*      an x is zero or more y 

• union, also called alternation, represented by |:

x ::= y | z     an x is a y or a z 

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

• optional (0 or 1 occurrence), represented by ?:

x ::=  y?      an x is a y or is the empty string

• 1 or more occurrences: represented by +:

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

• a character class [...], representing the length-1 strings containing any of the characters listed in the square brackets:

x ::= [abc]  is equivalent to  x ::= 'a' | 'b' | 'c' 

• an inverted character class [^...], representing the length-1 strings containing any character not listed in the brackets:

x ::= [^abc] is equivalent to  x ::= 'd' | 'e' | 'f' 
                                         | ... (all other characters in Unicode)

By convention, the postfix operators *, ?, and + 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:

• grouping using parentheses:

x ::=  (y z | a b)*   an x is zero or more y-z or a-b pairs
m ::=  a (b|c) d      an m is a, followed by either b or c, followed by d

S ::= (B C)* T
B ::= M+ | P B P
C ::= B | E+

root ::= 'a'+ 'b'* 'c'?

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

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

Suppose we want to write a grammar that represents URLs. Let’s build up a grammar gradually by starting with simple examples and extending the grammar as we go.

Here’s a simple URL:

http://mit.edu/

A grammar that represents the set of strings containing only this URL would look like:

url ::= 'http://mit.edu/'

But let’s generalize it to capture other domains, as well:

http://stanford.edu/
http://google.com/

We can write this as one line, like this:

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

This grammar represents the set of all URLs that consist of just a two-part hostname, where each part of the hostname consists of 1 or more letters. So http://mit.edu/ and http://yahoo.com/ would match, but not http://ou812.com/. Since it has only one nonterminal, a parse tree for this URL grammar would look like the picture on the right.

In this one-line form, with a single nonterminal whose production uses only operators and terminals, a grammar is called a regular expression (more about that later). But it will be easier to understand if we name the parts using new nonterminals:

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

The parse tree for this grammar is now shown at right. The tree has more structure now. The leaves of the tree are the parts of the string that have been parsed. If we concatenated the leaves together, we would recover the original string. The hostname and word nonterminals are labeling nodes of the tree whose subtrees match those rules in the grammar. Notice that the immediate children of a nonterminal node like hostname follow the pattern of the hostname rule, word '.' word.

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 like this:

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

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 allow 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

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_.

HTML

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

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 ::= [^<>]*

Regular expressions (“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 frequency of 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
| ';'