Questions: Context-Free Grammars in Compiler Design

Question 1

A grammar has two rules: `Expr → Expr + Term | Term` and `Term → Term * Factor | Factor`. A student asks why multiplication binds more tightly than addition without any explicit precedence declaration. What is the correct explanation?

• A. The parser is programmed to always evaluate * before +, so the grammar order doesn't matter
• B. Because * appears alphabetically before + in ASCII, parsers process it first
• C. Multiplication is handled at the Term level, which must be fully resolved before it can become part of an Expr; this nesting means * binds more tightly than + by the grammar's structure alone
• D. Precedence is specified separately in a precedence table; the grammar rules are just for syntax

Answer: (C)

In this grammar, to reduce an expression like 2 + 3 * 4, the parser must first reduce 3 * 4 to a Term (via Term → Term * Factor) before it can form an Expr (via Expr → Expr + Term). The grammar hierarchy forces multiplication to be resolved at a lower (inner) level before addition operates at the higher (outer) level. Operator precedence is not declared separately — it emerges automatically from the grammar's recursive structure. This is one of the most elegant features of CFG-based language definition.

Question 2

Why are context-free grammars necessary for describing programming language syntax, rather than simpler regular expressions?

• A. CFGs are not necessary — regular expressions are equally expressive but slower to evaluate
• B. Regular expressions can describe nested structures like matching parentheses or arbitrarily deep if-else blocks, but CFGs are preferred for efficiency
• C. Regular expressions cannot describe recursive nesting — matching parentheses, nested blocks, or arbitrarily deep expression trees require CFG productions that refer to themselves
• D. CFGs are required only for semantics (type checking); regular expressions suffice for syntax

Answer: (C)

By the pumping lemma, regular languages cannot count or match nested structures — a regular expression cannot enforce that every '(' has a matching ')' at arbitrary depth. Programming languages have inherently recursive structure: function bodies contain statements, which contain expressions, which contain function calls, which contain expressions — nesting arbitrarily deep. CFG productions can refer to themselves (e.g., Expr → ( Expr )), directly capturing this recursion. Regular expressions are used only for the token level (what identifiers, numbers, and keywords look like), not for syntax.

Question 3

A context-free grammar rule like `Expr → Expr + Term` simultaneously defines which token sequences are syntactically valid AND encodes that addition is left-associative through its recursive structure.

• T. True
• F. False

Answer: True

The left recursion `Expr → Expr + Term` means the left operand of + must itself be fully parsed as an Expr before the + is applied. This forces left-to-right grouping: a + b + c is parsed as (a + b) + c. If the rule were right-recursive (`Expr → Term + Expr`), + would be right-associative. The grammar's structure IS the semantic claim about associativity — no separate declaration is needed.

Question 4

A context-free grammar for a programming language also specifies the semantic rules, such as type checking and variable scope resolution, since these follow directly from the parse tree structure.

• T. True
• F. False

Answer: False

CFGs define syntax — which sequences of tokens form valid programs — and the structural relationships between them (encoded in the parse tree). Semantics (type checking, scope resolution, what a program means) are handled by later compiler phases (semantic analysis, type inference) that operate on the parse tree the grammar defined. The grammar tells you a + b is a valid expression; it says nothing about whether a and b are compatible types or whether b is in scope. This separation of syntax and semantics is a fundamental principle of compiler design.

Question 5

Explain why operator precedence and associativity fall out naturally from the grammar's structure, rather than needing to be declared as separate rules.

Model answer: In a CFG, the hierarchy of nonterminals determines which operations bind more tightly. An operator handled at a deeper level of the grammar (e.g., * in Term) must be resolved before an operator at a shallower level (e.g., + in Expr). This nesting means deeper-level operators have higher precedence. Associativity is encoded by which side the recursion appears on: left recursion forces left-to-right grouping (left-associative), right recursion forces right-to-left (right-associative). The parse tree structure directly reflects these groupings.

This insight — that grammar structure IS semantic structure — is why CFGs are the preferred specification language for programming language syntax. Writing down the grammar is not just saying what is syntactically valid; it is making precise claims about how expressions are to be interpreted. The grammar is both a definition of legal programs and a blueprint for how to build the parse tree that encodes their meaning.