On encountering an error, the parser starts popping symbols from
its stack until it encounters a state with a shift action on error
.
The parser shifts the token error
on to the stack and
then skips ahead in the input until it finds a newline which it shifts
onto the stack. The parser reduces error '\n'
to
lines
and emits the error message "reenter previous line:".
The special Yacc routine yyerrok
resets the parser to its
normal mode of operation.
3. Syntax-Directed Definitions
- The syntax analyzer translates its input token stream into an intermediate
language representation of the source program, usually an abstract
syntax tree.
- A syntax-directed definition can be used to specify this translation.
- An SDD is a context-free grammar with semantic rules attached to the productions.
- The semantic rules define values for attributes associated with the
nonterminal symbols of the productions. These values can be computed by
creating a parse tree for the input and then making a sequence of
passes over the parse tree, evaluating some or all of the rules on each
pass.
4. Synthesized and Inherited Attributes
- Attributes are values attached to the nodes of a parse tree.
- Synthesized attributes
are values that can be computed bottom-up in the parse tree.
The identifiers $$, $1, $2, etc., in Yacc actions are
synthesized attributes. Synthesized attributes can be
easily computed by a shift-reduce parser that keeps the
values of the attributes on the parsing stack.
See Fig. 5.19, p. 325.
- Inherited attributes are values that can be computed
top-down in the parse tree.
5. SDD for Binary-to-Decimal Translation
- Here is an SDD translating signed bit strings
into decimal numbers. The attributes,
BNum.val
,
Sign.val
, List.val
, and
Bit.val
, are all synthesized attributes that
represent integers.
BNum → Sign List { BNum.val = Sign.val × List.val }
Sign → + { Sign.val = +1 }
Sign → - { Sign.val = -1 }
List → List1 Bit { List.val = 2 × List1.val + Bit.val }
List → Bit { List.val = Bit.val }
Bit → 0 { Bit.val = 0 }
Bit → 1 { Bit.val = 1 }
Same example in Yacc:
BNum : Sign List { $$ = $1 * $2; }
;
Sign : '+' { $$ = +1; }
| '-' { $$ = -1; }
;
List : List Bit { $$ = 2*$1 + $2; }
| Bit
;
Bit : '0' { $$ = 0; }
| '1' { $$ = 1; }
;
6. From Arithmetic Expressions into Syntax Trees
- Here is a Yacc program that translates arithmetic expressions
into syntax trees. The function
mkleaf(op, left, right)
returns a pointer to a node with three fields:
the first labeled op
, the second a pointer
to a left subtree, and the third a pointer to a right subtree.
mkleaf(num, value)
returns a pointer to a node
with two fields, the first labeled num
and the
second its value.
E : E '+' T { $$ = mknode('+', $1, $3); }
| T
;
T : T '*' F { $$ = mknode('*', $1, $3); }
| T
;
F : '(' E ')' { $$ = $2; }
| num { $$ = mkleaf('num', $1); }
;
6. Reading
- ALSU: Sections 4.9, 5.1-5.3
aho@cs.columbia.edu