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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{synch}(A)} is found, then pop Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and continue.

Building:

1. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \mathrm{follow}(A)} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in \mathrm{synch}(A)}
2. Place keywords that start statements in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} is LR(1) if the following 3 conditions:

1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{Start} \Rightarrow^* \alpha A w \Rightarrow^* \alpha \beta w}
2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{Start} \Rightarrow^* \alpha A y \Rightarrow^* \alpha \beta y}
3. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{first}(w) = \mathrm{first}(y)}

imply that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha A y = \gamma B x} (i.e. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha = \gamma} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A = B} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = x} )

LR(k) Items

Lookahead consists of strings of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} .

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

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [A ::= \alpha \cdot X \beta, \mathtt{a}]}

Augmented start rule item is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [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