Ch. 2: A Simple Compiler

Syntax-Directed Translation

A syntax-directed definition uses a context-free grammar to specify the syntactic structure of the input.

A syntax-directed definition defines semantic rules.

For example, for infix to postfix translations:

expr -> expr1 + term ||| expr.t := expr1.t || term.t || '+'

Depth-First Traversal

Visits child nodes starting from a root node going from left to right.

procedure visit (n: node);
begin
    for each child m of n, from left to right do
      visit(m);
    evaluate semantic rules at node n
end

Translation Schemes

Like a syntax-directed definition, except that the order of evaluation of the semantic rules is explicit.

From hoc:

expr:    | expr '+' expr    { $$ = $1 + $3; }

Parsing

Determine if a string of tokens can be generated by a given grammar. While compilers may not actually construct a parse tree, they must be able to in order to guarantee correctness.

Top-Down Parsing

Starting from the root, repeat the following:

1. At a node select a production and construct its children for symbols on the right side of the production.
2. Find the next node to construct a subtree.

To be continued...