CSCE 434 Lecture 22

« previous | Monday, October 14, 2013 | next »

Lecture Slides

Choose optimization project for pp6

preferably something about data flow

Associativity and Precedence

Used to resolve shift/reduce conflicts in ambiguous grammars

• Lookahead with higher precedence: shift
• Same precedence, left associative: reduce

Allows for:

• more concise, albeit ambiguous grammars
• Shallower parse trees (fewer reductions)

Simple expression grammar:

<expr> ::= <expr> * <expr>
         | <expr> / <expr>
         | <expr> + <expr>
         | <expr> - <expr>
         | ( <expr> )
         | - <expr>
         | id
         | num
         ;

Error Recovery

Synchronizing terminals (for each nonterminal): When an error occurs when looking for nonterminal $A$, scan until an element of $\mathrm {synch} (A)$ is found, then pop $A$ and continue.

Building:

1. If $a\in \mathrm {follow} (A)$, then $a\in \mathrm {synch} (A)$
2. Place keywords that start statements in $\mathrm {synch} (A)$

Problem: if we encounter an invalid token, we'll have bad pieces of tree hanging from the stack and incorrect entries in the symbol table.

• We need to find a state in which we can restart our parsing
• Move to consistent place in input
• Print an informative error message

Yacc/Bison

Special error token

invoke yyerror(char*)

Augmented grammar $G$ is LR(1) if the following 3 conditions:

1. $\mathrm {Start} \Rightarrow ^{*}\alpha Aw\Rightarrow ^{*}\alpha \beta w$
2. $\mathrm {Start} \Rightarrow ^{*}\alpha Ay\Rightarrow ^{*}\alpha \beta y$
3. $\mathrm {first} (w)=\mathrm {first} (y)$

imply that $\alpha Ay=\gamma Bx$ (i.e. $\alpha =\gamma$, $A=B$, and $y=x$)

LR(k) Items

Lookahead consists of strings of length $k$.

Items are like LR(0) items, but have additional lookahead:

$[A::=\alpha \cdot X\beta ,{\mathtt {a}}]$

Augmented start rule item is $[S'::=\cdot S,{\mathtt {eof}}]$

Context-Sensitive Analysis

Lecture Slides

Context: implicit or explicit declarations, scope

Answers questions like:

1. Is an expression type-consistent?
2. Does the dimension of a reference match its declaration?
3. Where can x be stored? (stack, heap, memory*, etc.)
4. Is x declared before it is used?

why is context-sensitive analysis hard?

• Need access to non-local information
• Answers depend on values, not syntax
• Answers may involve computation

Approaches to solve above problems:

1. Write context-sensitive grammars (computationally hard)
2. ad-hoc techniques (symbol tables and code; yacc "action routines"; this is what we use)
3. formal methods (syntax-directed translation; type systems, checking algorithms)

Attribute Grammars

Decorate the tree

• Add attributes (fields) to each node
• specify equations to define values
• Inherited (on parent) and synthesized (on self) attributes

• Add type and class attributes on expressions
• For example, assignment checks that LHS is a variable and that the LHS/RHS types are consistent or conformable