Regular expressions are a convenient means of specifying certain simple (though possibly infinite) sets of strings. They are of practical interest because regular expressions can be used to specify the structure of the tokens used in a programming language. In particular, regular expressions can be used to program a scanner generator. The sets of strings defined by regular expressions are termed regular sets. We start with a finite character set, or vocabulary (denoted V). This vocabulary is normally the character set used to form tokens. An empty or null string is allowed (denoted λ, "lambda"). Strings are built from characters in V via concatenation (for example, :=, begin, 123).The null string, when concatenated with any string S, yields S. That is, Sλ ≡ λS ≡ S.

Concatenation can be extended to sets of strings as follows: Let P and Q be sets of strings. Then string S ∈ (P Q) if and only if S can be broken into two pieces: S = S1 S2, such that S1 ∈ P and S2 ∈ Q. Small finite sets are veniently represented by listing their elements, which can be individual characters or strings of charaters. Parentheses are used to delimit expressions, and |, the alternation operator, is used to separate alternatives.

The characters (, ), ‘, and | are meta-characters (punctuation and regular expression operators). Meta-characters can be quoted when used as ordinal characters to avoid ambiguity. (Any character or string may be quoted, but unnecessary quotation is avoided to enhance readability.) For example:

Alternation can be extended to sets of strings. Let P and Q be sets of strings. Then string S ∈ (P | Q) if and only if S ∈ P or S ∈ Q. Large (or infinite) sets are conveniently represented by operations on finite sets of characters and strings. Concatenation and alternation may be used. A third operation, Kleene closure, is also allowed. The operator * will represent the postfix Kleene closure operator. Let P be a set of strings. String S ∈ P* if and only if S can be broken into zero or more pieces: S = S1 S2 S3 … Sn such that each Si ∈ P. A string in P* is the concatenation of zero or more selections (possibly repeated) from P. (We explicitly allow n = 0, so that λ is always in P*.)

Regular expressions are defined as follows. Each regular expression denotes a set of strings ( a regular set).

• Ø is a regular expression denoting the empty set (the set containing no strings).
• λ is a regular expression denoting the set that contains only the empty string. Note that this set is not the same as the empty set, because it contains one element.
• A string S is a regular expression denoting a set containing only S. If S contains meta-characters, S can be quoted to avoid ambiguity.
• If A and B are regular expressions, denoting the alternation, concatenation, and Kleene closure of the corresponding regular sets.

Any finite set of strings can be represented by a regular expression of the form (S1 | S2 | … | Sn).

We often utilize the following operations as notational convenience. They are not strictly necessary, because their effect can be obtained (albeit somewhat clumsily) using the three standard regular operators (alternation, concatenation, kleene closure):

• P+ denotes the strings consisting of one or more strings in P concatenated together: P+ = (P+ | λ) and P+ = P P*.
• If A is a set of characters, Not(A) denotes (V – A); that is, all characters in V not included in A. Since Not(A) is finite, it is trivially regular. It is possible to extend Not to strings, rather that just V. That is, if S is a set or strings, we can define Note(S) to be (V* – S). Although it may be infinite, this set is also regular.
• If k is a constant, the set Ak represents all strings formed by concatenating k (not necessarily different) strings from A. That is, Ak = (A A A …) (k copies).

We now illustrate how regular expression can be used to specify tokens. Let

• A comment that begins with –– and ends with Eol (end of line) can be defined as:
  
  Comment = –– Not(Eol)* Eol
  
• A fixed decimal literal can be defined as:
  
  Lit = D+ . D+
  
• An identifier, composed of letters, digits, and underscores, that begins with a letter, ends with a letter or digit, and contains no consecutive underscores, can be defined as:
  
  ID = L (L | D)* (_ (L | D)+ )*
  
• A more complicated example is a comment delimited by ## markers which allows single #’s within the comment body:
  
  Comment2 = ## ((# | λ) Not(#))* ##

All finite sets and many infinite sets, such as those just listed, are regular. But not all infinite sets are regular. For example, consider { [k]k | I ≥ 1}, which is the set of balanced brackets of the form [[[[[ … ]]]]]. This is a well-known set that is not regular. The problem is that any regular set either does not get all balanced nesting or it includes extra, unwanted strings.

It is easy to write a context-free grammar (described in the next section) that defines balanced brackets precisely. All regular sets can be defined by context-free grammars; thus, the bracket example shows that context-free grammars are more powerful descriptive mechanism that regular expressions. Regular expressions are, however, quite adequate for specifying token-level syntax.

Traditionally, context–free grammars have been used as a basis of the syntax analysis phase of compilation. A context–free grammar is sometimes called a BNF (Backus–Naur form) grammar.

Informally, a context–free grammar is simply a set of rewriting rules or productions. A production is of the form

Two kinds of symbols may appear in a context–free grammar: nonterminal and terminals. In this tutorial, nonterminals are often delimited by < and > for ease of recognition. However, nonterminals can also be recognized by the fact that they appear on the left–hand sides of productions. A nonterminal is, in effect, a placeholder. All nonterminals must be replaced, or rewritten, by a production having the appropriate nonterminal on its LHS. In constrast, terminals are never changed or rewritten. Rather, they represent the tokens of a language. Thus the overall purpose of a set of productions (a context–free grammar) is to specify what sequences of terminals (tokens) are legal. A context–free grammar does this in a remarkably elegant way: We start with a single nonterminal symbol called the start or goal symbol. We then apply productions, rewriting nonterminals until only terminals remain. Any sequence of terminals that can be produced by doing this is considered legal. To see how this works, let us look at a context–free grammar for a small subset of Pascal that we call Small Pascal. λ will represent the empty or null string. Thus a production

Programming language constructs often involve optional items, or lists of items. To cleanly represent such features, an extended BNF notation is often utilised. An optional item sequence is enclosed in square brackets, [ and ]. For example, in

An extended BNF has the same definitional capability as ordinary BNFs. In particular, the following transforms can be used to map extended BNFs into standard form. An optional sequence is replaced by a new nonterminal that generates λ or the items in the sequence. Similarly, an optional sequence is replaced by a new nonterminal that genereates λ or the sequence of followed by the nonterminal. Thus our statement sequence can be transformed into

<statement sequence> → <statement> <statement tail>
<statement tail> → λ
<statement tail> → <statement> <statement tail>

The advantage of extended BNFs is that they are more compact and readable. We can envision a preprocessor that takes extended BNFs and produces standard BNFs.

Figure 3.1 shows a context–free grammar for a Small Pascal. An augmenting production

                                        1. <system goal> → <program> EOF
                                        2. <program> → begin <statement sequence> end .
                                        3. <statement sequence> → <statement> {<statement>}
                                        4. <statement> → ID := <expression> ;
                                        5. <statement> → readln ( <identifier list> ) ;
                                        6. <statement> → writeln ( <expression list> ) ;
                                        7. <identifier list> → ID {, ID}
                                        8. <expression list> → <expression> {, <expression>}
                                        9. <expression> → <factor> <addition operator> <factor>
                                        10. <factor> → ( <expression> )
                                        11. <factor> → ID
                                        12. <factor> → INTLITERAL
                                        13. <addition operator> → PLUS
                                        14. <addition operator> → MINUS

To see how this grammar defines legal Small Pascal programs, let’s follow the derivation of one such program, begin ID := ID + ( INTLITERAL – ID ) ; end EOF, starting from the nonterminal <system goal>.

<system goal>
<program> EOF                                                                 (rule 1)
begin <statement sequence> end EOF                                 (rule 2)
begin <statement> {, <statement} end EOF                         (rule 3)
begin <statement> end EOF                                                (Choose 0 repetitions)
begin ID := <expression> ; end EOF                                    (rule 4)
begin ID := <factor> <add op > <factor> ; end EOF             (rule 9)
begin ID := <factor> + <factor> ; end EOF                          (rule 13)
begin ID := ID + <factor> ; end EOF                                    (rule 11)
begin ID := ID + ( <expression> ) ; end EOF                         (rule 10)
begin ID := ID + ( <factor> {<add op> <factor>} ) end EOF  (rule 9)
begin ID := ID + ( <factor> <add op> <factor> ) end EOF     (Choose 1 repetition)
begin ID := ID + ( <factor> – <factor> ) end EOF                  (Apply rule 14)
begin ID := ID + ( INTLITERAL – <factor> ) end EOF              (Apply rule 12)
begin ID := ID + ( INTLITERAL – ID ) end EOF                        (Apply rule 11)

At this point no nonterminals remain, so our derivation of a Small Pascal program is completed.

A context–free grammar defines a language, which is a set of sequences of tokens. Any sequence of tokens that can be derived using the grammar is valid; any sequence that cannot be derived is not valid. Actually, to be precise, any token sequence derivable from a context–free grammar is considered syntactically valid. When static semantics are checked by the semantic routines, semantic errors in a syntactically valid program may be discovered. For example, in Pascal the statement

Structure as well as syntax can be defined in a context–free grammar. For expressions, this includes associctivity and operator precedence. Associativity is concerned with the order in which consecutive instances of an operator are applied (as in A–B–C). Operator precedence refers to the relative priority of operators. For example, we expect A+B*C to mean A+(B*C), since * is usually considered to be a higher precedence operator than +. Small Pascal has only one level of precedence, because it does not include multiplication nor addition. If multiplication were included, it would be at a higher level of precedence than addition. The following grammar fragment defines such a precedence relationship.

                                        <expression> → <term> {<add op> <term>}                                         <term> → <factor> {<mult op> <factor>}
                                        <factor> → ( <expression> )
                                        <factor> → ID
                                        <factor> → INTLITERAL

Examining a derivation tree for the expression A+B*C, which is derived from this grammar fragment, illustrates how this definition works. A derivation tree is formed by showing nonterminals expansions as subtrees. Figure 3.2 shows the tree for this expression.

The tree shows that * has a higher precedence than + because the second and third Ids are grouped together (with *) in a subtree, and then this subtree is grouped together with the first ID the first ID (using +) in the main derivation tree.

Now we may ask: can a derivation tree with wrong precedence ever be formed in this grammar? No – the production rules don’t allow it. Try to build ID+ID*ID with + applied first. Since a * can only be generated by a <term>, ID+ID must appear unless the subexpression is enclosed in parentheses. With parentheses, the desired grouping can be forced.

We have so far introduced regular expressions and context–free grammars, which are respectively used for defining the lexer and parser of a grammar. There is one more thing the reader must know, which is the type of grammar used in SableCC. In this paper we will give just a brief idea of a particular grammar, LALR(1), a subset of LR(1), which is commonly used in the description of almost any programming language. If you would like to know more about other types of grammars, such as LL(k) or LR(k), then you should refer to [1] or [2].

Instead of describing the LALR(1) type of grammar in full, we will just outline the conflicts that may occur in this type of grammar. There are two types of conflicts that may occur in this type of grammar: Reduce⁄Reduce and Shift⁄Reduce conflicts. A reduce⁄reduce conflict occurs when the parser does not know which production to reduce. For example, the grammar

As for shift⁄reduce conflicts, they occur when the parser does not know if it reduces or if it shifts (pushes the token or nonterminal to the stack) the current input. For instance, let’s analyse the grammar

                                        A → BaDe | BaDeCe
                                        B → c
                                        D → b
                                        C → s

Suppose that the input is cabe. When the parser receives this input, it first reduces c to B, then it shifts it (pushes it to the stack). It then reads a and shifts it, next it reads b, reduces it to D and shifts it, finally it reads e and know it does not know if it shifts e or if it reduces the string cabe to A.

Now that you know the theory behind regular expressions and grammars you can dive into the Sablecc tutorial, where I show you how to write a small compiler using a compiler generator tool called SableCC.

If you have any queries regarding this tutorial, just drop me an email.

References:

1. Andrew W. Appel, “Modern compiler implementation in Java”, Cambridge University Press, 1998.
2. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman, “Compilers Principles, Techniques, and Tools”, Addison-Wesley, 1986.