Attribute Grammars: Determining the Evaluation Order of Attributes

Verified Sources

Nov 4, 2026

In attribute grammars, the evaluation order of attributes is determined by which computations depend on which other computations. This is captured by the Dependency graph, where nodes represent attribute occurrences and edges represent “must be evaluated before” relationships. Therefore, the correct option for “Which of the following is used to determine the evaluation order of attributes?” is (iii) Dependency graph.

A standard way to view this is: if attribute $A$ depends on attribute $B$ , then $B$ must be evaluated before $A$ . The dependency graph encodes these relations; a valid evaluation order corresponds to an ordering consistent with the graph’s edges (commonly via a topological-sort style reasoning).

Key concepts you’ll use:

Attribute grammar
Attribute occurrence
Semantic rule
Dependency graph

Attribute Grammars & Dependency-Driven Evaluation (Educational)

Let’s map the multiple-choice options to what they mean in compiler theory:

(i) Symbol table: stores identifiers (variables, functions, types) and scope-related info; it does not directly encode attribute-to-attribute evaluation dependencies.
(ii) Transition table: used in automata/parsers (e.g., LR parsing tables) to decide parser actions; it also does not determine evaluation order of semantic attribute computations.
(iii) Dependency graph: directly represents attribute dependencies and is used to derive a safe evaluation order.
(iv) Abstract grammar: refers to a higher-level representation of syntax/structure, not the dependency structure of attribute computations.

Correct answer: (iii) Dependency graph.

Key concepts:

Symbol table
Transition table
Abstract grammar
Evaluation order

How the dependency graph implies a valid attribute evaluation order

1
Step 1
For each attribute occurrence in the attribute grammar (e.g., synthesized/inherited attributes on each node), create a node in the dependency graph.
2
Step 2
For every semantic rule that computes attribute $X$ using attribute $Y$ , add an edge $Y \rightarrow X$ .
3
Step 3
Any evaluation schedule must compute each node only after all its predecessors are computed.
4
Step 4
If the dependency graph is acyclic, a schedule exists that follows the graph’s direction (topological ordering). If there’s a cycle, the order is invalid unless additional constraints exist.

Why each option is (or isn’t) about evaluation order

Dependency graph directly models attribute-to-attribute precedence; other options model different compiler tasks.

Common confusion checks

Pro Tip

When a question says “evaluation order of attributes,” look for an option that represents dependencies/precedence. In attribute grammars, that’s the dependency graph.

Exam Trap

Don’t confuse parsing control (transition tables) with semantic evaluation control (attribute dependency relations). They operate at different layers of the compiler.

Knowledge Check

Question 1 of 4

Q1Single choice

Which of the following is used to determine the evaluation order of attributes?

Symbol table

Transition table

Dependency graph

Abstract grammar

Explore Related Topics

Lexical Analysis and the Main Structure Used: Finite Automata

Lexical analysis relies on finite automata—typically deterministic finite automata (DFA)—to recognize token patterns defined by regular expressions.

Regular expressions for identifiers, numbers, etc., are converted to NFAs then to a DFA for fast scanning.
The DFA processes the source character by character, tracking a single current state and emitting a token at each accepting state.
Queues, stacks, and trees support other compiler phases (parsing, AST construction) but are not the primary model for token recognition.
Lexers output a stream of tokens that the parser consumes for syntax analysis.

Correct Answer: Eliminating Immediate Left Recursion $A \rightarrow A\alpha / \beta$

Compiler Phases: Which Analyzer Checks Every Character?

Browse all research articles