K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 52
Текст из файла (страница 52)
In this scenario, an attribute rule can record information directlyinto a global table, where other rules can read the information. This hybridapproach can eliminate many of the problems that arise from nonlocal information. Since the table can be accessed from any attribution rule, it has theeffect of providing local access to any information already derived.Adding a central repository for facts complicates matters in another way.If two rules communicate through a mechanism other than an attribution4.3 The Attribute-Grammar Framework 197rule, the implicit dependence between them is removed from the attributedependence graph.
The missing dependence should constrain the evaluator to ensure that the two rules are processed in the correct order; withoutit, the evaluator may be able to construct an order that, while correct forthe grammar, has unintended behavior because of the removed constraint.For example, passing information between the declaration syntax and anexecutable expression through a table might allow the evaluator to processdeclarations after some or all of the expressions that use the declared variables.
If the grammar uses copy rules to propagate that same information,those rules constrain the evaluator to orders that respect the dependencesembodied by those copy rules.SECTION REVIEWAttribute grammars provide a functional specification that canbe used to solve a variety of problems, including many of theproblems that arise in performing context-sensitive analysis. Inthe attribute-grammar approach, the compiler writer producessuccinct rules to describe the computation; the attribute-grammarevaluator then provides the mechanisms to perform the actualcomputation. A high-quality attribute-grammar system wouldsimplify the construction of the semantic elaboration section of acompiler.The attribute-grammar approach has never achieved widespreadpopularity for a number of mundane reasons. Large problems, suchas the difficulty of performing nonlocal computation and the need totraverse the parse tree to discover answers to simple questions, havediscouraged the adoption of these ideas.
Small problems, such as spacemanagement for short-lived attributes, evaluator efficiency, and the lackof widely-available, open-source attribute-grammar evaluators have alsomade these tools and techniques less attractive.Review Questions1. From the “four function calculator” grammar given in the margin,construct an attribute-grammar scheme that attributes each Calcnode with the specified computation, displaying the answer on eachreduction to Expr.2. The “define-before-use” rule specifies that each variable used in a procedure must be declared before it appears in the text. Sketch anattribute-grammar scheme for checking that a procedure conformswith this rule. Is the problem easier if the language requires that alldeclarations precede any executable statement?Calc → ExprExpr → Expr + Term| Expr − Term| TermTerm → Term × num| Term ÷ num| numFour Function Calculator198 CHAPTER 4 Context-Sensitive Analysis4.4 AD HOC SYNTAX-DIRECTED TRANSLATIONThe rule-based evaluators for attribute grammars introduce a powerful ideathat serves as the basis for the ad hoc techniques used for context-sensitiveanalysis in many compilers.
In the rule-based evaluators, the compiler writerspecifies a sequence of actions that are associated with productions in thegrammar. The underlying observation, that the actions required for contextsensitive analysis can be organized around the structure of the grammar,leads to a powerful, albeit ad hoc, approach to incorporating this kind ofanalysis into the process of parsing a context-free grammar. We refer to thisapproach as ad hoc syntax-directed translation.In this scheme, the compiler writer provides snippets of code that executeat parse time. Each snippet, or action, is directly tied to a production in thegrammar.
Each time the parser recognizes that it is at a particular place in thegrammar, the corresponding action is invoked to perform its task. To implement this in a top-down, recursive-descent parser, the compiler writer simplyadds the appropriate code to the parsing routines. The compiler writer hascomplete control over when the actions execute. In a bottom-up, shift-reduceparser, the actions are performed each time the parser performs a reduceaction. This is more restrictive, but still workable.To make this concrete, consider reformulating the signed binary numberexample in an ad hoc syntax-directed translation framework.
Figure 4.11shows one such framework. Each grammar symbol has a single value associated with it, denoted val in the code snippets. The code snippet for eachrule defines the value associated with the symbol on the rule’s left-hand side.Rule 1 simply multiplies the value for Sign with the value for List. Rules 2and 3 set the value for Sign appropriately, just as rules 6 and 7 set the valuefor each instance of Bit.
Rule 4 simply copies the value from Bit to List. Thereal work occurs in rule 5, which multiplies the accumulated value of theleading bits (in List.val) by two, and then adds in the next bit.So far, this looks quite similar to an attribute grammar. However, it has twokey simplifications. Values flow in only one direction, from leaves to root.It allows only a single value per grammar symbol. Even so, the scheme inFigure 4.11 correctly computes the value of the signed binary number. Itleaves that value at the root of the tree, just like the attribute grammar forsigned binary numbers.These two simplifications make possible an evaluation method that workswell with a bottom-up parser, such as the lr(1) parsers described in Chapter 3.
Since each code snippet is associated with the right-hand side of aspecific production, the parser can invoke the action each time it reduces by4.4 Ad Hoc Syntax-Directed Translation 199Production1234567NumberSignSignListList0BitBit→→→→→→→Sign List+-BitList1 Bit01Code SnippetNumber . val ← Sign . val × List . valSign . val ← 1Sign . val ← -1List . val ← Bit . valList0 .val ← 2 × List1 .val + Bit . valBit . val ← 0Bit . val ← 1n FIGURE 4.11 Ad Hoc Syntax-Directed Translation for Signed Binary Numbers.that production.
This requires minor modifications to the reduce action inthe skeleton lr(1) parser shown in Figure 3.15.else if Action[s,word] = “reduce A→β” theninvoke the appropriate reduce actionpop 2 × |β| symbolss ← top of stackpush Apush Goto[s, A]The parser generator can gather the syntax-directed actions together, embedthem in a case statement that switches on the number of the production beingreduced, and place the case statement just before it pops the right-hand sidefrom the stack.The translation scheme shown in Figure 4.11 is simpler than the scheme usedto explain attribute grammars.
Of course, we can write an attribute grammarthat applies the same strategy. It would use only synthesized attributes. Itwould have fewer attribution rules and fewer attributes than the one shownin Figure 4.5. We chose the more complex attribution scheme to illustratethe use of both synthesized and inherited attributes.4.4.1 Implementing Ad Hoc Syntax-DirectedTranslationTo make ad hoc syntax-directed translation work, the parser must includemechanisms to pass values from their definitions in one action to their usesin another, to provide convenient and consistent naming, and to allow foractions that execute at other points in the parse. This section describesmechanisms for handling these issues in a bottom-up, shift-reduce parser.200 CHAPTER 4 Context-Sensitive AnalysisAnalogous ideas will work for top-down parsers.
We adopt a notation introduced in the Yacc system, an early and popular lalr(1) parser generatordistributed with the Unix operating system. The Yacc notation has beenadopted by many subsequent systems.Communicating between ActionsTo pass values between actions, the parser must have a methodology forallocating space to hold the values produced by the various actions. Themechanism must make it possible for an action that uses a value to find it.An attribute grammar associates the values (attributes) with nodes in theparse tree; tying the attribute storage to the tree nodes’ storage makes it possible to find attribute values in a systematic way.
In ad hoc syntax-directedtranslation, the parser may not construct the parse tree. Instead, the parsercan integrate the storage for values into its own mechanism for tracking thestate of the parse—its internal stack.Recall that the skeleton lr(1) parser stored two values on the stack for eachgrammar symbol: the symbol and a corresponding state.
When it recognizesa handle, such as a List Bit sequence to match the right-hand side of rule 5,the first pair on the stack represents the Bit. Underneath that lies the pairrepresenting the List. We can replace these hsymbol, statei pairs with triples,hvalue, symbol, statei. This provides a single value attribute per grammarsymbol—precisely what the simplified scheme needs. To manage the stack,the parser pushes and pops more values. On a reduction by A→β, it pops3 × |β| items from the stack, rather than 2 × |β| items. It pushes the valuealong with the symbol and state.This approach stores the values at easily computed locations relative tothe top of the stack. Each reduction pushes its result onto the stack as part ofthe triple that represents the left-hand side.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
