Slide 4.3: Syntax-directed definitions

Slide 4.2: Syntax-directed translation
Slide 4.4: Annotated parse trees
Home

Syntax-Directed Definitions

A syntax-directed definition (SDD) is a context-free grammar together with attributes and rules. Attributes are associated with grammar symbols and rules are associated with productions.

An attribute grammar is an SDD without side effects, which are modifications of a non-local environment such as printing a value.

The following SDD (attribute grammar) evaluates arithmetic expressions with operators + and * terminated by an endmarker n. For example, the expression “3 * 5 + 4 n” is evaluated to 19.

In the SDD, each of the nonterminals has a single attribute, called Val. Explanations of some productions are

	Production	Semantic Rules
1.	`<L> ::= <E> n`	`Val(<L>) = Val(<E>)`
2.	`<E> ::= <E₁> + <T>`	`Val(<E>) = Val(<E₁>) + Val(<T>)`
3.	`<E> ::= <T>`	`Val(<E>) = Val(<T>)`
4.	`<T> ::= <T₁> * <F>`	`Val(<T>) = Val(<T₁>) × Val(<F>)`
5.	`<T> ::= <F>`	`Val(<T>) = Val(<F>)`
6.	`<F> ::= ( <E> )`	`Val(<F>) = Val(<E>)`
7.	`<F> ::= digit`	`Val(<F>) = Lexval(digit)`

The rule for Production 1 sets Val(<L>) to Val(<E>), which is the numerical value of the entire expression.

Production 2, <E> ::= <E₁> + <T>, has one rule, which computes the Val attribute for the head <E> as the sum of the values at <E₁> and <T>. At any parse-tree node N labeled <E>, the value of Val for <E> is the sum of the values of Val at the children of node N labeled <E> and <T>.

For the last production, the terminal digit has an attribute Lexval, which is an integer value returned by the lexical analyzer. The analyzer is software converting a sequence of characters into a sequence of tokens.