Context-free grammars and pushdown memory

Prerequisites: Finite automata, recursion, and basic stack operations.

Learning objectives

• Derive strings from a context-free grammar.
• Use stack invariants to recognize balanced delimiters.
• Distinguish a language from an ambiguous grammar for it.

Productions define recursive structure

A context-free grammar contains terminal symbols, nonterminal symbols, a start nonterminal, and productions replacing one nonterminal with a sequence of symbols. A derivation repeatedly applies productions until only terminals remain. The generated language contains every terminal string reachable from the start symbol, regardless of which derivation produces it.

The grammar S -> (S)S | epsilon generates balanced parentheses, where epsilon denotes the empty string. A nonempty balanced sequence consists of an opening parenthesis, a balanced interior, its matching closing parenthesis, and a balanced remainder. For example, S becomes (S)S, then ((S)S)S; replacing the remaining nonterminals with empty strings yields (()). Alternatively, a nonempty remainder produces ()(). The grammar mirrors the recursive decomposition of the strings.

A stack remembers unfinished nesting

A pushdown automaton adds an unbounded stack to finite control. For one kind of parenthesis, recognition can use a counter for the number of unmatched opens: increase on opening, decrease on closing, reject a negative count, and accept only zero at the end. With several delimiter types, a stack stores their order. On ([{}]), push (, then [, then {; each closing symbol must match the current top before it is removed.

The invariant is that the stack contains exactly the unmatched opening delimiters in their nesting order after the consumed prefix. A closing delimiter on an empty stack fails immediately. Finishing with a nonempty stack also fails. Merely comparing totals is insufficient: )( has equal numbers of opens and closes but violates the prefix condition, while ([)] violates nesting types.

Parsing needs more than acceptance

A parser builds a tree representing how productions generated the input. This tree guides later interpretation, compilation, or validation. A grammar is ambiguous if some string has more than one parse tree. For E -> E+E | EE | number, the expression 2+34 permits different groupings and therefore different evaluations. Operator precedence and associativity can be encoded by a better grammar or an explicit parsing policy.

Ambiguity belongs to a grammar, not automatically to its language. A different grammar may describe the same strings unambiguously. Context-free descriptions also have limits: matching arbitrary duplicated identifiers or enforcing all declaration-before-use rules generally needs additional semantic analysis. Separate lexical recognition, syntactic structure, and semantic constraints rather than forcing every requirement into one parser. This separation makes errors more precise and each stage easier to reason about.

Practice problem

Write a delimiter checker for parentheses, square brackets, and braces that reports the index of the first mismatched closing delimiter. On end of input, report any remaining unmatched opening positions. Ignore other characters. State a stack invariant and trace a([b)]. Then give two parse trees, described with parentheses, for 8-3-1 under grammar E -> E-E | number. Explain why a language specification must decide associativity even if both trees use valid productions.

Worked solution

Store pairs of opening symbol and index on the stack. Push opening delimiters. For a closer, reject if the stack is empty or its top has the wrong opening type; otherwise pop. After the full scan, any remaining stack entries identify unmatched opens. For a([b)], positions 1 and 2 push ( and [; the closing parenthesis at index 4 mismatches the top [, so index 4 is the first reported error. The stack invariant records unmatched openings in order and justifies the local comparison. The arithmetic parses are (8-3)-1, yielding 4, and 8-(3-1), yielding 6. Both are grammatical, so parsing must implement a specified associativity rule rather than selecting an arbitrary tree and treating it as the only meaning.

Check your understanding

Why is equal total opening and closing delimiter count insufficient?

• Counts cannot detect a closing delimiter before its opening or crossed delimiter types.
• A balanced string must have odd length.
• Counting is impossible in linear time.

Explanation

Balanced syntax imposes prefix and nesting constraints, not just equality of totals.

What does grammar ambiguity mean?

• Every string in its language has multiple spellings.
• At least one generated string has more than one parse tree.
• No parser can reject invalid input.

Explanation

Ambiguity concerns multiple structural derivations of the same terminal string.

Primary reading

• Automata, Computability, and Complexity: MIT OpenCourseWare

Open the study and save your work →