K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 53
Текст из файла (страница 53)
The action reads the values forthe right-hand side from their relative positions in the stack; the i th symbolon the right-hand side has its value in the i th triple from the top of the stack.Values are restricted to a fixed size; in practice, this limitation means thatmore complex values are passed using pointers to structures.To save storage, the parser could omit the actual grammar symbols fromthe stack. The information necessary for parsing is encoded in the state.This shrinks the stack and speeds up the parse by eliminating the operations that stack and unstack those symbols.
On the other hand, the grammarsymbol can help in error reporting and in debugging the parser. This tradeoff is usually decided in favor of not modifying the parser that the toolsproduce—such modifications must be reapplied each time the parser isregenerated.4.4 Ad Hoc Syntax-Directed Translation 201Naming ValuesTo simplify the use of stack-based values, the compiler writer needs a notation for naming them. Yacc introduced a concise notation to address thisproblem. The symbol $$ refers to the result location for the current production. Thus, the assignment $$ = 0; would push the integer value zeroas the result corresponding to the current reduction.
This assignment couldimplement the action for rule 6 in Figure 4.11. For the right-hand side, thesymbols $1, $2, . . . , $n refer to the locations for the first, second, throughnth symbols in the right-hand side, respectively.Rewriting the example from Figure 4.11 in this notation produces thefollowing specification:Production1234567NumberSignSignListList0BitBit→→→→→→→Sign List+-BitList1 Bit01Code Snippet$$$$$$$$$$$$$$←←←←←←←$1 × $21−1$12 × $1 + $201Notice how compact the code snippets are.
This scheme has an efficientimplementation; the symbols translate directly into offsets from the top ofthe stack. The notation $1 indicates a location 3 × |β| slots below the top ofthe stack, while a reference to $i designates the location 3 × (|β| − i + 1)slots from the top of the stack. Thus, the positional notation allows the actionsnippets to read and write the stack locations directly.Actions at Other Points in the ParseCompiler writers might also need to perform an action in the middle of aproduction or on a shift action. To accomplish this, compiler writers cantransform the grammar so that it performs a reduction at each point where anaction is needed. To reduce in the middle of a production, they can break theproduction into two pieces around the point where the action should execute.A higher-level production that sequences the first part, then the second part,is added.
When the first part reduces, the parser invokes the action. To forceactions on shifts, a compiler writer can either move them into the scanneror add a production to hold the action. For example, to perform an action202 CHAPTER 4 Context-Sensitive Analysiswhenever the parser shifts the terminal symbol Bit, a compiler writer canadd a productionShiftedBit → Bitand replace every occurrence of Bit with ShiftedBit. This adds an extrareduction for every terminal symbol. Thus, the additional cost is directlyproportional to the number of terminal symbols in the program.4.4.2 ExamplesTo understand how ad hoc syntax-directed translation works, considerrewriting the execution-time estimator using this approach.
The primarydrawback of the attribute-grammar solution lies in the proliferation of rulesto copy information around the tree. This creates many additional rules inthe specification and duplicates attribute values at many nodes.To address these problems in an ad hoc syntax-directed translation scheme,the compiler writer typically introduces a central repository for informationabout variables, as suggested earlier.
This eliminates the need to copy valuesaround the trees. It also simplifies the handling of inherited values. Since theparser determines evaluation order, we do not need to worry about breakingdependences between attributes.Most compilers build and use such a repository, called a symbol table. Thesymbol table maps a name into a variety of annotations such as a type, thesize of its runtime representation, and the information needed to generatea runtime address. The table may also store a number of type-dependentfields, such as the type signature of a function or the number of dimensions and their bounds for an array. Section 5.5 and Appendix B.4 delveinto symbol-table design more deeply.Load Tracking, RevisitedConsider, again, the problem of tracking load operations that arose as part ofestimating execution costs.
Most of the complexity in the attribute grammarfor this problem arose from the need to pass information around the tree.In an ad hoc syntax-directed translation scheme that uses a symbol table,the problem is easy to handle. The compiler writer can set aside a field inthe table to hold a boolean that indicates whether or not that identifier hasalready been charged for a load. The field is initially set to false.
Thecritical code is associated with the production Factor → name. If the name’ssymbol table entry indicates that it has not been charged for a load, thencost is updated and the field is set to true.4.4 Ad Hoc Syntax-Directed Translation 203ProductionSyntax-Directed ActionsBlock0 → Block1 Assign|AssignAssign → name = Expr ;{ cost = cost + Cost(store) }Expr→ Expr + Term{ cost = cost + Cost(add) }|Expr − Term{ cost = cost + Cost(sub) }|TermTerm→ Term × Factor|Term ÷ Factor|Factor{ cost = cost + Cost(mult) }{ cost = cost + Cost(div) }Factor → ( Expr )|num{ cost = cost + Cost(loadI) }|name{ if name’s symbol table fieldindicates that it has not been loadedthencost = cost + Cost(load)set the field to true }n FIGURE 4.12 Tracking Loads with Ad Hoc Syntax-Directed Translation.Figure 4.12 shows this case, along with all the other actions.
Because theactions can contain arbitrary code, the compiler can accumulate cost in asingle variable, rather than creating a cost attribute at each node in the parsetree. This scheme requires fewer actions than the attribution rules for thesimplest execution model, even though it can provide the accuracy of themore complex model.Notice that several productions have no actions. The remaining actions aresimple, except for the action taken on a reduction by name. All of the complication introduced by tracking loads falls into that single action; contrastthat with the attribute-grammar version, where the task of passing aroundthe Before and After sets came to dominate the specification. The ad hocversion is cleaner and simpler, in part because the problem fits nicely intothe evaluation order dictated by the reduce actions in a shift-reduce parser.Of course, the compiler writer must implement the symbol table or import itfrom some library of data-structure implementations.Clearly, some of these strategies could also be applied in an attributegrammar framework.
However, they violate the functional nature of theattribute grammar. They force critical parts of the work out of the attributegrammar framework and into an ad hoc setting.204 CHAPTER 4 Context-Sensitive AnalysisThe scheme in Figure 4.12 ignores one critical issue: initializing cost.
Thegrammar, as written, contains no production that can appropriately initializecost to zero. The solution, as described earlier, is to modify the grammar ina way that creates a place for the initialization. An initial production, such asStart → CostInit Block, along with CostInit → , does this. The frameworkcan perform the assignment cost ← 0 on the reduction from to CostInit.Type Inference for Expressions, RevisitedThe problem of inferring types for expressions fit well into the attributegrammar framework, as long as we assumed that leaf nodes already hadtype information.
The simplicity of the solution shown in Figure 4.7 derivesfrom two principal facts. First, because expression types are defined recursively on the expression tree, the natural flow of information runs bottom upfrom the leaves to the root. This biases the solution toward an S-attributedgrammar. Second, expression types are defined in terms of the syntax of thesource language. This fits well with the attribute-grammar framework, whichimplicitly requires the presence of a parse tree. All the type informationcan be tied to instances of grammar symbols, which correspond preciselyto nodes in the parse tree.We can reformulate this problem in an ad hoc framework, as shown inFigure 4.13. It uses the type inference functions introduced with Figure 4.7.The resulting framework looks similar to the attribute grammar for the samepurpose from Figure 4.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
