Cooper K.Engineering a compiler

arrange the non-terminals in some order

A1, A2, . . . , An

for i ← 1 to n

for j ← 1 to i-1

replace each production of the form Ai→Aj γ with the productions

Ai→δ1γ | δ2γ | . . . | δk γ, where Aj →δ1 | δ2 | . . . | δk are all the current Aj productions.

eliminate any immediate left recursion on Ai using the direct transformation

Figure 3.2: Removal of left recursion

The transformation shown above eliminates immediate left recursion. Left recursion can occur indirectly, when a chain of rules such as α→β, β→γ, and γ→αδ combines to create the situation that α→+αδ. This indirect left recursion is not always obvious; it can be hidden through an arbitrarily long chain of productions.

To convert these indirect left recursions into right recursion, we need a more systematic approach than inspection followed by application of our transformation. Figure 3.2 shows an algorithm that achieves this goal. It assumes that the grammar has no cycles (A →+ A) or productions (A → ).

The algorithm works by imposing an arbitrary order on the non-terminals. The outer loop cycles through the non-terminals in this order, while the inner loop ensures that a production expanding Ai has no non-terminal Aj with j < i. When it encounters such a non-terminal, it forward substitutes the non-terminal away. This eventually converts each indirect left recursion into a direct left recursion. The final step in the outer loop converts any direct recursion on Ai to right recursion using the simple transformation shown earlier. Because new non-terminals are added at the end of the order and only involve right recursion, the loop can ignore them—they do not need to be checked and converted.

Considering the loop invariant for the outer loop may make this more clear. At the start of the ith outer loop iteration

k < i, a production expanding Ak with Al in its rhs, for l < k.

At the end of this process, (i = n), all indirect left recursion has been eliminated through the repetitive application of the inner loop, and all immediate left recursion has been eliminated in the final step of each iteration.

3.3.3Predictive Parsing

When we parsed x − 2 × y with the right-recursive expression grammar, we did not need to backtrack. In fact, we can devise a parser for the right-recursive

For each N T A G

find the longest prefix α common to two or more right-hand sides

if α = then

replace the rules expanding A,

A → αβ1 | αβ2 | · · · | αβn | γ with

A → α fie | γ

fie → β1 | β2 | · · · | βn and add fie to N T

Repeat until no common prefixes remain.

Figure 3.3: Left Factoring a Grammar

11.Factor → Identifier

12.| Identifier [ Exprlist ]

13.| Identifier ( Exprlist )

20. Exprlist → Expr , Exprlist

21.| Expr

Here, we show the C syntactic convention of using parentheses for function calls and square brackets for array references. This grammar fragment is not predictive, because the initial terminal symbol generated in rules 11, 12, and 13 is the same. Thus, the parser, in trying to expand a Factor on the parse tree’s lower fringe, cannot decide between 11, 12, and 13 on the basis of a single word lookahead. Of course, looking ahead two tokens would allow it to predict the correct expansion.

We can rewrite rules 11, 12, and 13 to make them predictive.

13.| ( Exprlist )

In this case, we were able to transform the grammar into a predictive grammar. In essence, we introduced a new non-terminal to represent the common prefix of the three rules that were not predictive. We can apply this transformation, systematically and mechanically, to an arbitrary grammar. Figure 3.3 shows a simple algorithm that does this. However, left factoring the grammar will not always produce a predictive grammar.

Not all languages can be expressed in a predictive grammar. Using leftrecursion elimination and left factoring, we may be able to transform a grammar to the point where it can be predictively parsed. In general, however, it is undecidable whether or not a predictive grammar exists for an arbitrary contextfree language. For example, the language

if (current token First(β1)) { if (Parse γ() = false)

return false

else if (current token = δ) {

report an error finding δ in A → γδρ return false

}

current token ← next token() if (Parse ρ() = false)

return false else

return true

}

The routine Parse A will contain a code fragment like this for each alternative right-hand side for A.

To construct a complete recursive descent parser, then, the strategy is clear. For each non-terminal, we construct a routine that recognizes that non-terminal. Each routine relies on the other routines to recognize non-terminals, and directly tests the terminal symbols that arise in its own right hand sides. Figure 3.4 shows a top-down recursive descent parser for the predictive grammar that we derived in Section 3.3.2. Notice that it repeats code for similar right hand sides. For example, the code in ExprP() under the tests for ‘+’ and for ‘-’ could be combined to produce a smaller parser.

Automating the Process Top-down recursive-descent parsing is usually considered a technique for hand coding a parser. Of course, we could build a parser generator that automatically emitted top-down recursive descent parsers for suitable grammars. The parser generator would first construct the necessary First sets for each grammar symbol, check each non-terminal to ensure that the First sets of its alternative right-hand sides are disjoint, and emit a suitable parsing routine for each non-terminal symbol in the grammar. The resulting parser would have the advantages of top-down recursive-descent parsers, such as speed, code-space locality, and good error detection. It would also have the advantages of a grammar-generated system, such as a concise, high-level specification and a reduced implementation e ort.

3.4Bottom-up Parsing

To parse a stream of words bottom-up, the parser begins by creating leaves in the parse tree for each word. This creates the base of the parse tree. To construct a derivation, it adds layers of non-terminals on top of the leaves, in a structure dictated by both the grammar and the input stream. The upper edge of this partially-constructed parse tree is called its upper frontier. Each layer extends the frontier upward, toward the tree’s root.

To do this, the parser repeatedly looks for a part of that upper frontier that matches the right-hand side of a production in the grammar. When it finds a

Digression: Predictive parsers versus DFAs

Predictive parsing is the natural extension of dfa-style reasoning to parsers. A dfa makes its transition based on the next input character. A predictive parser requires that the expansions be uniquely determined by the next word in the input stream. Thus, at each non-terminal in the grammar, there must be a unique mapping from the first token in any acceptable input string to a specific production that leads to a derivation for that string. The real di erence in power between a dfa and a predictively-parsable, or ll(1), grammar, derives from the fact that one prediction may lead to a right-hand side with many symbols, whereas, in a regular grammar, it predicts only a single symbol. This lets predictive grammars include productions like

p → ( p )

which is beyond the power of a regular expression to describe. (Recall that a regular expression can recognize (+ Σ )+, but this does not specify that the opening and closing parentheses must match.)

Of course, a hand-constructed top-down, recursive-descent parser can use arbitrary tricks to disambiguate production choices. For example, if a particular left-hand side cannot be predicted with a single symbol lookahead, the parser could use two symbols. Done judiciously, this should not cause problems.

match, it builds a node to represent the non-terminal symbol on production’s left-hand side, and adds edges to the nodes representing elements of the righthand side. This extends the upper frontier. This process terminates under one of two conditions.

1.The parser reduces the upper frontier to a single node that represents the grammar’s start symbol. If all the input has been consumed, the input stream is a valid sentence in the language.

2.No match can be found. Since, the parser has been unable to build a derivation for the input stream, the input is not a valid sentence. The parser should issue an appropriate error message.

A successful parse runs through every step of the derivation. A failed parse halts when it can find no further steps, at which point it can use the context accumulated in the tree to produce a meaningful error message.

Derivations begin with the goal symbol and work towards a sentence. Because a bottom-up parser proceeds bottom-up in the parse tree, it discovers derivation steps in reverse order. Consider a production α→β where β T . A bottom-up parser will “discover” the derivation step α→β before it discovers the step that derives α. Thus, if a derivation consists of a series of steps that produces a series of sentential forms

S0 = γ0 γ1 γ2 · · · γn−1 γn = sentence,

Figure 3.5: States of the bottom-up parser on x − 2 × y

When the frontier does not contain a handle, the parser extends the frontier by adding a single non-terminal to the right end of the frontier. To see how this works, consider parsing the string x − 2 × y using the classic expression grammar. At each step, the parser either finds a handle on the frontier, or it adds to the frontier. The state of the parser, at each step, is summarized in Figure 3.5, while Figure 3.6 shows the corresponding partial parse tree for each step in the process; the trees are drawn with their frontier elements justified along the top of each drawing.

As the example shows, the parser only needs to examine the upper frontier of partially constructed parse tree. Using this fact, we can build a particularly clean form of bottom-up parser, called a shift-reduce parser. These parsers use a stack to hold the frontier; this simplifies the algorithm in two ways. First, the stack trivializes the problem of managing space for the frontier. To extend the frontier, the parser simply shifts the current input symbol onto the stack. Second, it ensures that all handles occur with their right end at the top of the stack; this eliminates any overhead from tracking handle positions.

Figure 3.7 shows a simple shift-reduce parser. To begin, it shifts an invalid symbol onto the stack and gets the first input symbol from the scanner. Then, it follows the handle-pruning discipline: it shifts symbols from the input onto the stack until it discovers a handle, and it reduces handles as soon as they are found. It halts when it has reduced the stack to Goal on top of invalid and consumed all the input.