K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 39
Текст из файла (страница 39)
When the parser encounters an error, it discards inputsymbols until it finds a synchronizing word and then resets its internal stateto one consistent with the synchronizing word.In an Algol-like language, with semicolons as statement separators, thesemicolon is often used as a synchronizing word. When an error occurs,the parser calls the scanner repeatedly until it finds a semicolon. It thenchanges state to one that would have resulted from successful recognitionof a complete statement, rather than an error.In a recursive-descent parser, the code can simply discard words until it findsa semicolon. At that point, it can return control to the point where the routinethat parses statements reports success.
This may involve manipulating theruntime stack or using a nonlocal jump like C’s setjmp and longjmp.In an lr(1) parser, this kind of resynchronization is more complex. Theparser discards input until it finds a semicolon. Next, it scans backward downthe parse stack until it finds a state s such that Goto[s, Statement] is a valid,nonerror entry. The first such state on the stack represents the statement that142 CHAPTER 3 Parserscontains the error. The error recovery routine then discards entries on thestack above that state, pushes the state Goto[s, Statement] onto the stack andresumes normal parsing.In a table-driven parser, either ll(1) or lr(1), the compiler needs a wayof telling the parser generator where to synchronize. This can be doneusing error productions—a production whose right-hand side includes areserved word that indicates an error synchronization point and one ormore synchronizing tokens.
With such a construct, the parser generator canconstruct error-recovery routines that implement the desired behavior.Of course, the error-recovery routines should take steps to ensure that thecompiler does not try to generate and optimize code for a syntacticallyinvalid program. This requires simple handshaking between the errorrecovery apparatus and the high-level driver that invokes the various partsof the compiler.3.5.2 Unary OperatorsThe classic expression grammar includes only binary operators.
Algebraicnotation, however, includes unary operators, such as unary minus and absolute value. Other unary operators arise in programming languages, includingautoincrement, autodecrement, address-of, dereference, boolean complement, and typecasts. Adding such operators to the expression grammarrequires some care.Consider adding a unary absolute-value operator, k, to the classic expressiongrammar.
Absolute value should have higher precedence than either x or ÷.Goal0Goal → Expr123Expr456Term → Term x Value| Term ÷ Value| Value78Value → k Factor| Factor91011Factor → ( Expr )| num| nameExpr→ Expr + Term| Expr - Term| Term(a) The Grammar-Expr||TermTermValueValueFactorFactor<num,3><name,x>(b) Parse Tree for kx - 3n FIGURE 3.27 Adding Unary Absolute Value to the Classic Expression Grammar.3.5 Practical Issues 143However, it needs a lower precedence than Factor to force evaluation of parenthetic expressions before application of k. One way to write this grammaris shown in Figure 3.27. With these additions, the grammar is still lr(1).
Itlets the programmer form the absolute value of a number, an identifier, or aparenthesized expression.Figure 3.27b shows the parse tree for the string kx - 3. It correctly shows thatthe code must evaluate kx before performing the subtraction. The grammardoes not allow the programmer to write kkx, as that makes little mathematical sense. It does, however, allow k(kx), which makes as little senseas kkx.The inability to write kkx hardly limits the expressiveness of the language.With other unary operators, however, the issue seems more serious. Forexample, a C programmer might need to write **p to dereference a variable declared as char **p;.
We can add a dereference production for Valueas well: Value → * Value. The resulting grammar is still an lr(1) grammar,even if we replace the x operator in Term → Term x Value with *, overloading the operator “*” in the way that C does. This same approach works forunary minus.3.5.3 Handling Context-Sensitive AmbiguityUsing one word to represent two different meanings can create a syntacticambiguity. One example of this problem arose in the definitions of severalearly programming languages, including fortran, pl/i, and Ada.
These languages used parentheses to enclose both the subscript expressions of anarray reference and the argument list of a subroutine or function. Given atextual reference, such as fee(i,j), the compiler cannot tell if fee is atwo-dimensional array or a procedure that must be invoked. Differentiatingbetween these two cases requires knowledge of fee’s declared type. Thisinformation is not syntactically obvious. The scanner undoubtedly classifies fee as a name in either case. A function call and an array reference canappear in many of the same situations.Neither of these constructs appears in the classic expression grammar. Wecan add productions that derive them from Factor.Factor→ FunctionReference||||ArrayReference( Expr )numnameFunctionReference → name ( ArgList )ArrayReference→ name ( ArgList )144 CHAPTER 3 ParsersSince the last two productions have identical right-hand sides, this grammaris ambiguous, which creates a reduce-reduce conflict in an lr(1) tablebuilder.Resolving this ambiguity requires extra-syntactic knowledge.
In a recursivedescent parser, the compiler writer can combine the code for FunctionReference and ArrayReference and add the extra code required to check thename’s declared type. In a table-driven parser built with a parser generator,the solution must work within the framework provided by the tools.Two different approaches have been used to solve this problem. The compiler writer can rewrite the grammar to combine both the function invocationand the array reference into a single production.
In this scheme, the issue isdeferred until a later step in translation, when it can be resolved with information from the declarations. The parser must construct a representation thatpreserves all the information needed by either resolution; the later step willthen rewrite the reference to its appropriate form as an array reference or asa function invocation.Alternatively, the scanner can classify identifiers based on their declaredtypes, rather than their microsyntactic properties. This classification requiressome hand-shaking between the scanner and the parser; the coordination isnot hard to arrange as long as the language has a define-before-use rule.Since the declaration is parsed before the use occurs, the parser can makeits internal symbol table available to the scanner to resolve identifiers intodistinct classes, such as variable-name and function-name.
The relevantproductions become:FunctionReference → function-name ( ArgList )ArrayReference→ variable-name ( ArgList )Rewritten in this way, the grammar is unambiguous. Since the scannerreturns a distinct syntactic category in each case, the parser can distinguishthe two cases.3.5.4 Left versus Right RecursionAs we have seen, top-down parsers need right-recursive grammars ratherthan left-recursive ones. Bottom-up parsers can accommodate either left orright recursion. Thus, the compiler writer must choose between left and rightrecursion in writing the grammar for a bottom-up parser. Several factors playinto this decision.3.5 Practical Issues 145Stack DepthIn general, left recursion can lead to smaller stack depths.
Consider two alternate grammars for a simple list construct, shown in Figures 3.28a and 3.28b.(Notice the similarity to the SheepNoise grammar.) Using these grammars toproduce a five-element list leads to the derivations shown in Figures 3.28cand 3.28d, respectively. An lr(1) parser would construct these sequences inreverse. Thus, if we read the derivation from the bottom line to the top line,we can follow the parsers’s actions with each grammar.1. Left-recursive grammar This grammar shifts elt1 onto its stack andimmediately reduces it to List.
Next, it shifts elt2 onto the stack andreduces it to List. It proceeds until it has shifted each of the five elti sonto the stack and reduced them to List. Thus, the stack reaches a2maximum depth of two and an average depth of 106 = 13.2. Right-recursive grammar This version shifts all five elti s onto itsstack. Next, it reduces elt5 to List using rule two, and the remainingList → List elt| eltList → elt List| elt(a) Left-Recursive Grammar(b) Right-Recursive GrammarListListelt1 ListList elt5elt1 elt2 ListList elt4 elt5elt1 elt2 elt3 ListList elt3 elt4 elt5elt1 elt2 elt3 elt4 ListList elt2 elt3 elt4 elt5elt1 elt2 elt3 elt4 elt5elt1 elt2 elt3 elt4elt5 List(c) Derivation with Left Recursion(d) Derivation with Right Recursionelt5elt4elt3elt1 elt2(e) AST with Left Recursionn FIGURE 3.28 Left- and Right-Recursive List Grammars.elt1elt2elt3elt4elt5(f) AST with Right Recursion146 CHAPTER 3 Parserselti s using rule one.
Thus, its maximum stack depth will be five and itsaverage will be206= 3 13 .The right-recursive grammar requires more stack space; its maximum stackdepth is bounded only by the length of the list. In contrast, the maximumstack depth with the left-recursive grammar depends on the grammar ratherthan the input stream.For short lists, this is not a problem.
If, however, the list represents thestatement list in a long run of straight-line code, it might have hundredsof elements. In this case, the difference in space can be dramatic. If all otherissues are equal, the smaller stack height is an advantage.AssociativityAbstract syntax treeAn AST is a contraction of the parse tree. SeeSection 5.2.1 on page 227.Left recursion naturally produces left associativity, and right recursion naturally produces right associativity.
In some cases, the order of evaluationmakes a difference. Consider the abstract syntax trees (asts) for the two fiveelement lists, shown in Figures 3.28e and 3.28f. The left-recursive grammarreduces elt1 to a List, then reduces List elt2 , and so on. This produces theast shown on the left. Similarly, the right-recursive grammar produces theast shown on the right.For a list, neither of these orders is obviously incorrect, although the rightrecursive ast may seem more natural.
Consider, however, the result if wereplace the list constructor with arithmetic operations, as in the grammarsExpr → Expr + Operand| Expr - Operand| OperandExpr → Operand + Expr| Operand - Expr| OperandFor the string x1 + x2 + x3 + x4 + x5 the left-recursive grammar implies a leftto-right evaluation order, while the right-recursive grammar implies a rightto-left evaluation order. With some number systems, such as floating-pointarithmetic, these two evaluation orders can produce different results.Since the mantissa of a floating-point number is small relative to the range ofthe exponent, addition can become an identity operation with two numbersthat are far apart in magnitude.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
