Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 32

User Rating:  / 0

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Evaluation Methods

A number of ways can be used to evaluate the attributes. When using Dynamic method, the compiler application builds the parse tree and then builds the dependence graph. A topological sort of the graph is carried out and attributes are evaluated or defined in topological order. In rule-based (or treewalk) methodology, the attribute rules are analyzed at compiler-generation time. A fixed (static) ordering is determined and the nodes in the dependency graph are evaluated this order. In oblivious (passes, dataflow) methodology, the attribute rules and parse tree are ignored. A convenient order is picked at compiler design time and used.

Attribute grammars have not achieved widespread use due to a number of problems. For example: non-local computation, traversing parse tree, storage management for shortlived attributes and lack of high-quality inexpensive tools. However, a variation of attribute grammars and evaluation schemes is used in many compilers. This variation is called ad-hoc analysis.

In rule-based evaluators, a sequence of actions is associated with grammar productions.
Organizing actions required for context-sensitive analysis around structure of the grammar leads to powerful, albeit ad-hoc, approach which is used on most parsers. A snippet of code (action) is associated with each production that executes at parse time In top-down parsers, the snippet is added to the appropriate parsing routine. In a bottomup shift-reduce parsers, the actions are performed each time the parser performs a reduction. Here the LR(1) skeleton parser indicating the place where the snippet is executed.

stack.push(dummy); stack.push(0);
done = false; token = scanner.next();
while (!done) {
s = stack.top();
if( Action[s,token] == “reduce A→β”) {
invoke the code snippet
s = stack.top();
else if( Action[s,token] == “shift i”){
stack.push(token); stack.push(i);
token = scanner.next();

The following table shows the code snippets for the SBN example.

Productions Code snippet
Number → Sign List Number.val ← – Sign.val × List.val
Sign → + Sign.val ← 1
Sign → – Sign.val ← –1
List → Bit List.val ← Bit.val
List0 → List1 Bit List0.val ← 2×List1.val + Bit.val
Bit → 0 Bit.val ← 0
Bit → 1 Bit.val ← 1