Chapter 07 of 33

Syntax Analysis & Context-Free Grammars

The lexical analyzer from the previous chapters, including the one we generated with Lex & Flex, turns a program into a flat stream of tokens like id = id + num ;. But a stream of valid tokens is not yet a valid program. = id + ; num id is made of perfectly good tokens and is still nonsense.

Checking how tokens fit together, and recovering the structure of the program (which expression is inside which statement, which statement is inside which loop), is the job of the second phase: syntax analysis, or parsing.

To parse, we first need a precise way to describe the structure of a language. Regular expressions were enough for tokens, but they are not enough for programs. The tool we use instead is the context-free grammar (CFG). This chapter covers what the parser does, CFGs, derivations, parse trees, how to write grammars for common patterns, and how parsers deal with errors. Every grammar for a small language in this chapter (such as anbn or balanced parentheses) was checked by a program against its intended language for all strings up to length 10.


The Role of the Parser

                 token                          parse tree
source  ──►  [ Lexical  ] ────────►  [ Parser ]  ──────────►  [ rest of the  ]  ──► ...
program      [ analyzer ] ◄────────  [        ]               [ front end    ]
                         get next token    │
                  │                        │
                  └──────►  [ Symbol table ] ◄──┘

The parser:

  1. Asks the lexer for tokens one at a time (in Lex terms, it calls yylex()).

  2. Checks that the token sequence can be generated by the grammar of the language.

  3. Builds the structure: a parse tree, or more often a compact syntax tree, or it directly drives translation into intermediate code.

  4. Reports syntax errors clearly and recovers, so that one missing semicolon does not hide all the other errors in the file.

Why Not Regular Expressions?

Programming languages are full of nesting: parentheses inside parentheses, blocks inside blocks, if inside while inside if. To check that every ( has a matching ), a recognizer must count how many are still open, with no upper limit.

A regular expression is equivalent to a finite automaton, which has a fixed, finite number of states. With k states it cannot distinguish k + 1 different nesting depths, so it cannot recognize balanced parentheses, or the language { anbn | n ≥ 0 }. (The pumping lemma for regular languages in the Theory of Computation tutorial proves this formally.) Context-free grammars handle nesting naturally because a rule can contain itself in the middle, as in S → ( S ).

Aspect

Regular expressions

Context-free grammars

Used for

Tokens (lexical structure)

Program structure (syntax)

Recognized by

Finite automata

Pushdown automata (finite control plus a stack)

Can express unbounded nesting?

No

Yes

Power

Regular languages

Context-free languages (a strict superset)

Typical tool

Lex/Flex

Yacc/Bison

Every regular language can also be described by a CFG, so in principle the parser could do the lexer's job too. We still keep them separate because regular expressions are simpler for tokens, the DFA-based lexer is much faster, and the grammar becomes cleaner when it deals with tokens instead of individual characters.


Context-Free Grammars

A context-free grammar is a 4-tuple G = (V, T, P, S) where V is a finite set of variables (non-terminals), T is a finite set of terminals disjoint from V, P is a finite set of productions of the form A → α with A ∈ V and α ∈ (V ∪ T)*, and S ∈ V is the start symbol.

  • Terminals are the basic symbols that appear in the program. For a parser, these are the token names produced by the lexer: id, num, if, +, ( and so on.

  • Non-terminals are syntactic categories that stand for sets of strings: expression, statement, declaration.

  • A production A → α says "an A can be made of α". The left side is always a single non-terminal. That is what "context-free" means: A can be replaced by α no matter what surrounds A.

  • The start symbol stands for a whole program (or whatever the grammar describes).

Productions with the same left side are written together with |: A → α | β is short for the two productions A → α and A → β. A production A → ε means A can derive the empty string.

The Running Example: Arithmetic Expressions

E → E + T | T
T → T * F | F
F → ( E ) | id

Here V = {E, T, F}, T = {+, *, (, ), id}, S = E, and there are 6 productions. In words: an expression is a sum of terms, a term is a product of factors, and a factor is an identifier or a parenthesized expression. Keep this grammar in mind: it reappears in almost every parsing chapter.

Notation Conventions

Textbooks and GATE papers follow these conventions, so a grammar can be written without listing V and T explicitly:

Symbols

Usually denote

Uppercase letters early in the alphabet: A, B, C; also S

Non-terminals (S is the start symbol)

Lowercase letters early in the alphabet: a, b, c; operators; digits; bold keywords like if, id

Terminals

Uppercase letters late in the alphabet: X, Y, Z

A grammar symbol, either terminal or non-terminal

Lowercase letters late in the alphabet: u, v, w, x

Strings of terminals only

Greek letters: α, β, γ

Strings of grammar symbols (possibly empty)

The left side of the first production

The start symbol, unless stated otherwise


Derivations

A grammar generates strings by rewriting: start with S and repeatedly replace some non-terminal by the right side of one of its productions.

If A → γ is a production, then αAβ ⇒ αγβ ("derives in one step"). ⇒* means "derives in zero or more steps" and ⇒+ means "in one or more steps".

  • A sentential form is any string α (of terminals and non-terminals) with S ⇒* α.

  • A sentence is a sentential form made only of terminals.

  • The language of G is the set of all its sentences: L(G) = { w ∈ T* | S ⇒* w }.

At each step we choose which non-terminal to replace. Two systematic choices are important:

  • Leftmost derivation (⇒lm): always replace the leftmost non-terminal. Its sentential forms are called left-sentential forms. Top-down parsers build this derivation.

  • Rightmost derivation (⇒rm), also called canonical derivation: always replace the rightmost non-terminal. Bottom-up parsers build this derivation, in reverse.

Worked Example: Deriving id + id * id

Leftmost derivation (the non-terminal being replaced is always the first one):

E  ⇒ E + T            (E → E + T)
   ⇒ T + T            (E → T)
   ⇒ F + T            (T → F)
   ⇒ id + T           (F → id)
   ⇒ id + T * F       (T → T * F)
   ⇒ id + F * F       (T → F)
   ⇒ id + id * F      (F → id)
   ⇒ id + id * id     (F → id)

Rightmost derivation (the non-terminal being replaced is always the last one):

E  ⇒ E + T            (E → E + T)
   ⇒ E + T * F        (T → T * F)
   ⇒ E + T * id       (F → id)
   ⇒ E + F * id       (T → F)
   ⇒ E + id * id      (F → id)
   ⇒ T + id * id      (E → T)
   ⇒ F + id * id      (T → F)
   ⇒ id + id * id     (F → id)

Both take 8 steps and use exactly the same 8 productions, just in a different order. That is no accident: as we will see next, both describe the same parse tree.

A Second Example: Nested Parentheses

Leftmost derivation of ( id + id ) * id:

E ⇒ T ⇒ T * F ⇒ F * F ⇒ ( E ) * F ⇒ ( E + T ) * F ⇒ ( T + T ) * F
  ⇒ ( F + T ) * F ⇒ ( id + T ) * F ⇒ ( id + F ) * F ⇒ ( id + id ) * F
  ⇒ ( id + id ) * id

11 steps. Notice how the grammar forces the structure: the only way to get + under a * is through F → ( E ), so the parentheses really do group the sum first.


Parse Trees

A parse tree for a grammar G is a tree in which the root is labelled with the start symbol, each interior node is labelled with a non-terminal A whose children, from left to right, are the symbols of the right side of some production A → X1X2...Xn, and each leaf is labelled with a terminal or ε.

Reading the leaves from left to right gives the yield of the tree, which is the derived string. The parse tree for id + id * id:

                E
              / | \
             E  +  T
             |   / | \
             T  T  *  F
             |  |     |
             F  F     id
             |  |
             id id

The tree shows exactly what we want a compiler to know: id * id is a subtree (a T) that is added to the first id. Multiplication is done first, without any special rule; the grammar's shape forces it.

Trees vs Derivations

A parse tree records which productions were applied where, but forgets the order in which they were applied. Many derivations can therefore share one tree. However:

Every parse tree corresponds to exactly one leftmost derivation and exactly one rightmost derivation, and vice versa.

Expanding the tree in preorder, leftmost child first, gives the leftmost derivation; expanding the rightmost child first gives the rightmost derivation. So counting parse trees, counting leftmost derivations and counting rightmost derivations of a string always give the same number.

If some string has more than one parse tree, the grammar is ambiguous. Our expression grammar is not: id + id * id has exactly one tree (our checker enumerated all of them). Ambiguity is the main topic of the next chapter, Ambiguity, Left Recursion & Left Factoring.


Writing Grammars for Common Languages

Designing a grammar is a skill, and exam questions often ask for one. A few patterns cover most situations. Each grammar below was compared, by a program, against its language definition for all strings of length 0 to 10.

Language

Grammar

Idea

{ anbn | n ≥ 0 }

S → a S b | ε

Add one a and one b at a time, from the outside in

{ anb2n | n ≥ 0 }

S → a S b b | ε

Each a brings two b's

{ ambn | m ≥ n ≥ 0 }

S → a S b | a S | ε

Matched pairs, plus extra a's

{ ambn | m > n ≥ 0 }

S → a S b | A
A → a A | a

Matched pairs around a non-empty block of a's

{ anbmcmdn | m, n ≥ 0 }

S → a S d | A
A → b A c | ε

Nest one matched pair inside the other

Palindromes over {a, b}

S → a S a | b S b | a | b | ε

Same symbol at both ends; centre of odd or even length

Balanced parentheses

S → ( S ) S | ε

The first ( and its matching ), then whatever follows

Equal number of a's and b's

S → a S b S | b S a S | ε

Split at the point where the counts first balance

Worked Example: Why Does S → ( S ) S Work?

Any non-empty balanced string starts with (. Find the ) that matches it. The part between them is balanced, and the part after it is balanced. So every non-empty balanced string has the form ( x ) y with x and y balanced, which is exactly S → ( S ) S. Leftmost derivation of (())():

S ⇒ ( S ) S
  ⇒ ( ( S ) S ) S
  ⇒ ( ( ) S ) S          (S → ε)
  ⇒ ( ( ) ) S            (S → ε)
  ⇒ ( ( ) ) ( S ) S
  ⇒ ( ( ) ) ( ) S        (S → ε)
  ⇒ ( ( ) ) ( )          (S → ε)

The same reasoning ("split at the first point where things balance") gives the equal-a's-and-b's grammar: if a string with equal counts starts with a, the matching point is the first b that brings the counts back to equal.

Grammars for Programming Constructs

Real languages use the same patterns. A declaration such as int a, b, c;:

decl  → type idlist ;
type  → int | float | char
idlist → idlist , id | id

A block of statements with nesting:

stmt     → id = expr ;
         | while ( expr ) stmt
         | { stmtlist }
stmtlist → stmtlist stmt | ε

Notice the patterns: idlist → idlist , id | id is a list with separators (one or more), and stmtlist → stmtlist stmt | ε is a list without separators (zero or more). while ( expr ) stmt contains stmt inside itself, which gives unlimited nesting.

What a CFG Cannot Check

Some rules of real languages are not context-free:

  • "Every variable is declared before it is used." Abstractly, this is like the language { wcw | w ∈ (a|b)* }, which is not context-free.

  • "A function is called with as many arguments as it has parameters." This is like { anbmcndm }, also not context-free.

  • Type compatibility, such as not adding an integer to a function.

Compilers therefore use a CFG that is slightly too generous, and check these rules in the next phase, semantic analysis, using the symbol table. This split is deliberate: grammars for which efficient parsers exist are context-free, and the remaining checks are easy to do on the tree.


Types of Parsers

Kind

How it works

Examples

Used in practice?

Universal

Handles any CFG

CYK, Earley

Rarely in compilers: O(n3) time in general

Top-down

Builds the tree from the root down to the leaves; produces a leftmost derivation

Recursive descent, LL(1)

Yes: hand-written parsers (GCC and Clang use hand-written recursive descent)

Bottom-up

Builds the tree from the leaves up to the root; produces a rightmost derivation in reverse

Shift-reduce, operator precedence, LR(0), SLR, LALR, CLR

Yes: parser generators like Yacc/Bison (LALR)

Both efficient families read the input left to right, one token at a time, and run in time linear in the input length, but each works only for a restricted class of grammars. Much of the next several chapters is about those classes: what a grammar must look like for LL(1) or LR parsing to work, and how to transform it if it does not.


Syntax Error Handling

Programs being compiled are often wrong, so error handling is a real design goal, not an afterthought. A good parser should:

  • Report the presence of errors clearly and accurately, including the line.

  • Recover quickly enough to detect further errors.

  • Add minimal overhead to the processing of correct programs.

LL and LR parsers have the viable-prefix property: they detect an error as soon as the prefix read so far cannot be extended into any valid program. So the error is reported at the first token where things go wrong.

Error-Recovery Strategies

Strategy

Idea

Pros and cons

Panic mode

Discard input tokens until a synchronizing token (like ; or }) is found, then resume

Simple and never loops forever; may skip a lot of input and miss errors inside the skipped part

Phrase level

Make a local correction to the remaining input: insert a missing ;, delete an extra comma, replace , by ;

Fixes common typos well; a careless correction can cause an infinite loop (for example, inserting forever)

Error productions

Add productions to the grammar for common mistakes, such as stmt → if expr stmt without parentheses

Precise messages for anticipated errors; only covers what you anticipated and makes the grammar bigger

Global correction

Find the program closest to the input (minimum insertions, deletions, changes) that is valid

Theoretically ideal; far too expensive in time and space to use in practice

For example, on x = a + * b; a panic-mode parser would report an error at * and skip tokens up to ;. A phrase-level parser might insert a missing operand and continue. Yacc/Bison provide panic-mode recovery through a special error token, covered in the Yacc & Bison chapter.


Solved Problems

Problem 1: What Language Does This Grammar Generate?

S → a S b b | ε

Each use of the first production adds one a on the left and two b's on the right, and the derivation must end with ε. After n uses we get anb2n. So L = { anb2n | n ≥ 0 } = { ε, abb, aabbbb, ... }.

Problem 2: Is the String in the Language?

Using S → a S b S | b S a S | ε, is abba generated? It has two a's and two b's, and the grammar generates exactly the strings with equal counts. A derivation:

S ⇒ a S b S          (S → a S b S)
  ⇒ a b S            (S → ε, the first S)
  ⇒ a b b S a S      (S → b S a S)
  ⇒ a b b a S        (S → ε)
  ⇒ a b b a          (S → ε)

Yes. (Showing one derivation is enough to prove membership. To prove a string is not in the language you need an argument, such as an invariant: for example aab has unequal counts, and every production adds a's and b's in equal numbers, so it cannot be generated.)

Problem 3: Count the Derivation Steps

For the expression grammar, how many steps does the leftmost derivation of id * id take? The tree has nodes E → T, T → T * F, T → F, F → id, F → id: one step per interior node, so 5 steps. In general, the number of steps in any derivation equals the number of interior nodes of its parse tree.


Common Mistakes

  • Putting characters instead of tokens in the parser's grammar. The parser's terminals are token names like id and num; the spelling of identifiers is the lexer's business.

  • Thinking leftmost and rightmost derivations give different trees. For one parse tree, they are two orders of the same set of steps.

  • Calling a grammar ambiguous because a string has two derivations. Almost every string has many derivations. Ambiguity needs two different parse trees, equivalently two different leftmost derivations.

  • Confusing a sentential form with a sentence. A sentence contains only terminals.

  • Trying to enforce declarations or type rules in the grammar. These are not context-free and belong to semantic analysis.

  • Forgetting the base case. S → a S b alone generates nothing at all, because no derivation ever ends.


GATE and Interview Questions

What is the input and output of a parser?

Input: the stream of tokens from the lexical analyzer. Output: a parse tree (or syntax tree, or directly intermediate code) for a valid program, and error messages for an invalid one.

Why can't the lexical analyzer check that parentheses are balanced?

Lexers are based on regular expressions / finite automata, which have finitely many states and so cannot count unbounded nesting. Balanced parentheses form a context-free, non-regular language.

Define sentential form, left-sentential form and sentence.

A sentential form is any α with S ⇒* α. A left-sentential form is a sentential form that occurs in some leftmost derivation. A sentence is a sentential form consisting only of terminals.

Which derivation does a top-down parser trace, and which one does a bottom-up parser trace?

Top-down: a leftmost derivation. Bottom-up: a rightmost derivation, constructed in reverse order (from the string back to the start symbol).

For a given string, if there are k parse trees, how many leftmost derivations are there?

Exactly k. Parse trees, leftmost derivations and rightmost derivations are in one-to-one correspondence.

Write a grammar for { aibj | i ≠ j }.

It is the union of "more a's" and "more b's": S → A | B, A → a A b | a A | a (i > j), B → a B b | B b | b (j > i). A string with i ≠ j has either more a's or more b's, and each part generates matched pairs around a non-empty surplus.

Which error-recovery strategy uses synchronizing tokens? Which one is too costly to use?

Panic mode uses synchronizing tokens such as ; and }. Global correction is too costly in practice.

Is "variables must be declared before use" checked by the parser?

No. That rule is not context-free. The parser accepts any identifier; semantic analysis checks declarations using the symbol table.


Summary

  • The parser takes tokens, checks them against the grammar, builds a tree and reports and recovers from syntax errors.

  • Programming-language syntax needs context-free grammars, because regular expressions cannot describe unbounded nesting.

  • A CFG is G = (V, T, P, S); every production has a single non-terminal on the left.

  • A derivation rewrites non-terminals step by step. Leftmost derivations (top-down parsers) and rightmost derivations (bottom-up parsers, in reverse) are the two canonical orders.

  • A parse tree ignores the order of steps; each tree corresponds to exactly one leftmost and one rightmost derivation. Two trees for one string means the grammar is ambiguous.

  • Useful grammar patterns: matched pairs (a S b), nesting (S → ( S ) S), lists (L → L , id | id).

  • Non-context-free rules (declare before use, types) are left to semantic analysis.

  • Error recovery: panic mode, phrase level, error productions, global correction.

Tokens tell you what the words are; the grammar tells you how the words make sentences. The parse tree is the sentence diagram the rest of the compiler works from.