Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 30

It selects a nonterminal symbol on the lower fringe of the treeand extends it by adding children that correspond to the right-hand side of3.3 Top-Down Parsing 97some production for that nonterminal. It cannot extend the frontier from aterminal. This process continues until eithera. the fringe of the parse tree contains only terminal symbols, and the inputstream has been exhausted, orb. a clear mismatch occurs between the fringe of the partially built parsetree and the input stream.In the first case, the parse succeeds.

In the second case, two situations arepossible. The parser may have selected the wrong production at some earlierstep in the process, in which case it can backtrack, systematically reconsidering earlier decisions. For an input string that is a valid sentence, backtrackingwill lead the parser to a correct sequence of choices and let it constructa correct parse tree. Alternatively, if the input string is not a valid sentence, backtracking will fail and the parser should report the syntax error tothe user.One key insight makes top-down parsing efficient: a large subset of thecontext-free grammars can be parsed without backtracking.

Section 3.3.1shows transformations that can often convert an arbitrary grammar intoone suitable for backtrack-free top-down parsing. The two sections that follow it introduce two distinct techniques for constructing top-down parsers:hand-coded recursive-descent parsers and generated ll(1) parsers.Figure 3.2 shows a concrete algorithm for a top-down parser that constructs a leftmost derivation. It builds a parse tree, anchored at the variableroot. It uses a stack, with access functions push( ) and pop( ), to track theunmatched portion of the fringe.The main portion of the parser consists of a loop that focuses on the leftmost unmatched symbol on the partially-built parse tree’s lower fringe.

Ifthe focus symbol is a nonterminal, it expands the parse tree downward; itchooses a production, builds the corresponding part of the parse tree, andmoves the focus to the leftmost symbol on this new portion of the fringe. Ifthe focus symbol is a terminal, it compares the focus against the next wordin the input. A match moves both the focus to the next symbol on the fringeand advances the input stream.If the focus is a terminal symbol that does not match the input, the parsermust backtrack. First, it systematically considers alternatives for the mostrecently chosen rule.

If it exhausts those alternatives, it moves back up theparse tree and reconsiders choices at a higher level in the parse tree. If thisprocess fails to match the input, the parser reports a syntax error. Backtracking increases the asymptotic cost of parsing; in practice, it is an expensiveway to discover syntax errors.98 CHAPTER 3 Parsersroot ← node for the start symbol, S ;focus ← root;push(null);word ← NextWord( );while (true) do;if (focus is a nonterminal) then begin;pick next rule to expand focus (A → β1 , β2 , . . . , βn );build nodes for β1 , β2 . .

. βn as children of focus;push(βn , βn−1 , . . . , β2 );focus ← β1 ;end;else if (word matches focus) then begin;word ← NextWord( );focus ← pop( )end;else if (word = eof and focus = null)then accept the input and return root;else backtrack;end;n FIGURE 3.2 A Leftmost, Top-Down Parsing Algorithm.To facilitate finding the "next" rule, the parsercan store the rule number in a nonterminal’snode when it expands that node.The implementation of “backtrack” is straightforward. It sets focus to itsparent in the partially-built parse tree and disconnects its children. If anuntried rule remains with focus on its left-hand side, the parser expandsfocus by that rule.

It builds children for each symbol on the right-hand side,pushes those symbols onto the stack in right-to-left order, and sets focusto point at the first child. If no untried rule remains, the parser moves upanother level and tries again. When it runs out of possibilities, it reports asyntax error and quits.When it backtracks, the parser must also rewind the input stream.

Fortunately, the partial parse tree encodes enough information to make this actionefficient. The parser must place each matched terminal in the discardedproduction back into the input stream, an action it can take as it disconnects them from the parse tree in a left-to-right traversal of the discardedchildren.3.3.1 Transforming a Grammar for Top-Down ParsingThe efficiency of a top-down parser depends critically on its ability to pickthe correct production each time that it expands a nonterminal. If the parseralways makes the right choice, top-down parsing is efficient.

If it makespoor choices, the cost of parsing rises. For some grammars, the worst case3.3 Top-Down Parsing 99behavior is that the parser does not terminate. This section examines twostructural issues with cfgs that lead to problems with top-down parsers andpresents transformations that the compiler writer can apply to the grammarto avoid these problems.A Top-Down Parser with Oracular ChoiceAs an initial exercise, consider the behavior of the parser from Figure 3.2with the classic expression grammar in Figure 3.1 when applied to the stringa + b x c. For the moment, assume that the parser has an oracle that picks thecorrect production at each point in the parse.

With oracular choice, it mightproceed as shown in Figure 3.3. The right column shows the input string,with a marker ↑ to indicate the parser’s current position in the string. Thesymbol → in the rule column represents a step in which the parser matchesa terminal symbol against the input string and advances the input. At eachstep, the sentential form represents the lower fringe of the partially-builtparse tree.With oracular choice, the parser should take a number of steps proportionalto the length of the derivation plus the length of the input. For a + b x c theparser applied eight rules and matched five words.Notice, however, that oracular choice means inconsistent choice.

In boththe first and second steps, the parser considered the nonterminal Expr. In thefirst step, it applied rule 1, Expr → Expr + Term. In the second step, it appliedrule 3, Expr → Term. Similarly, when expanding Term in an attempt to matcha, it applied rule 6, Term → Factor, but when expanding Term to match b,Rule1369→→469→→9→Sentential FormInputname + name x namename + name x nameExprExpr + TermTerm + TermFactor + Termname + Termname + Termname + Termname + Term x Factorname + Factor x Factorname + name x Factorname + name x Factorname + name x Factornamenamenamenamenamename + name x namename + name x namename + name x ↑ namename + name x name ↑↑↑↑↑↑name + name x namename + name x namename + name x namename ↑ + name x namename ++++++↑↑↑↑name xxxxxnamenamenamename ↑name xn FIGURE 3.3 Leftmost, Top-Down Parse of a+bxc with Oracular Choice.namenamenamenamename↑ name100 CHAPTER 3 Parsersit applied rule 4, Term → Term x Factor.

It would be difficult to make thetop-down parser work with consistent, algorithmic choice when using thisversion of the expression grammar.Eliminating Left RecursionOne problem with the combination of the classic expression grammar and aleftmost, top-down parser arises from the structure of the grammar. To seethe difficulty, consider an implementation that always tries to apply the rulesin the order in which they appear in the grammar.

Its first several actionswould be:RuleSentential Form111ExprExpr + TermExpr + Term + Term···Input↑↑↑↑namenamenamename++++namenamenamename××××namenamenamenameIt starts with Expr and tries to match a. It applies rule 1 to create the sentential form Expr + Term on the fringe. Now, it faces the nonterminal Expr andthe input word a, again. By consistent choice, it applies rule 1 to replace Exprwith Expr + Term. Of course, it still faces Expr and the input word a.

Withthis grammar and consistent choice, the parser will continue to expand thefringe indefinitely because that expansion never generates a leading terminalsymbol.Left recursionA rule in a CFG is left recursive if the first symbolon its right-hand side is the symbol on itsleft-hand side or can derive that symbol.The former case is called direct left recursion,while the latter case is called indirect leftrecursion.This problem arises because the grammar uses left recursion in productions1, 2, 4, and 5. With left-recursion, a top-down parser can loop indefinitelywithout generating a leading terminal symbol that the parser can match (andadvance the input). Fortunately, we can reformulate a left-recursive grammarso that it uses right recursion—any recursion involves the rightmost symbolin a rule.The translation from left recursion to right recursion is mechanical.

Fordirect left recursion, like the one shown below to the left, we can rewritethe individual productions to use right recursion, shown on the right.Fee →|Fee αβFeeFee0→ β Fee0→ α Fee0|The transformation introduces a new nonterminal, Fee0 , and transfers therecursion onto Fee0 . It also adds the rule Fee0 →, where represents theempty string. This -production requires careful interpretation in the parsing algorithm.

To expand the production Fee0 →, the parser simply sets3.3 Top-Down Parsing 101focus ← pop( ), which advances its attention to the next node, terminalor nonterminal, on the fringe.In the classic expression grammar, direct left recursion appears in theproductions for both Expr and Term.OriginalExpr →||Term →||TransformedExpr + TermExpr - TermTermExprExpr 0Term x FactorTerm ÷ FactorFactorTerm →Term 0 →||→ Term Expr 0→ + Term Expr 0||- Term Expr 0Factor Term 0x Factor Term 0÷ Factor Term 0Plugging these replacements back into the classic expression grammar yieldsa right-recursive variant of the grammar, shown in Figure 3.4.

It specifies thesame set of expressions as the classic expression grammar.The grammar in Figure 3.4 eliminates the problem with nontermination. Itdoes not avoid the need for backtracking. Figure 3.5 shows the behavior ofthe top-down parser with this grammar on the input a + b x c. The examplestill assumes oracular choice; we will address that issue in the next subsection.

It matches all 5 terminals and applies 11 productions—3 more than itdid with the left-recursive grammar. All of the additional rule applicationsinvolve productions that derive .This simple transformation eliminates direct left recursion. We must alsoeliminate indirect left recursion, which occurs when a chain of rules such asα →β, β →γ , and γ →αδ creates the situation that α →+ αδ. Such indirectleft recursion is not always obvious; it can be obscured by a long chain ofproductions.012345Goal →Expr →Expr 0 →||Term →ExprTerm Expr 0+ Term Expr 0- Term Expr 0Factor Term 067891011Term 0→x Factor Term 0||÷ Factor Term 0Factor →||n FIGURE 3.4 Right-Recursive Variant of the Classic Expression Grammar.( Expr )numname102 CHAPTER 3 ParsersRule1511→82→511→6→11→84Sentential FormExprTerm Expr 0Factor Term 0 Expr 0name Term 0 Expr 0name Term 0 Expr 0name Expr 0name + Term Expr 0name + Term Expr 0name + Factor Term 0 Expr 0name + name Term 0 Expr 0name + name Term 0 Expr 0name + name x Factor Term 0name + name x Factor Term 0name + name x name Term 0name + name x name Term 0name + name x name Expr 0name + name x nameInputnamenamenamenamename ↑name ↑name ↑name +name +name +name +name +name +name +name +name +name +↑↑↑↑Expr 0Expr 0Expr 0Expr 0+++++++namenamenamenamenamenamename↑ name↑ name↑ namename ↑name ↑name xname xname xname xname xxxxxxxxxxxxxnamenamenamenamenamenamenamenamenamenamenamename↑ name↑ namename ↑name ↑name ↑n FIGURE 3.5 Leftmost, Top-Down Parse of a+bxc with the Right-Recursive Expression Grammar.To convert indirect left recursion into right recursion, we need a moresystematic approach than inspection followed by application of our transformation.