Formal Languages and Parsing

A formal language is a set of finite strings over an alphabet. A grammar defines productions that derive strings in that set. Compiler front ends use this model to separate local token recognition from recursive program structure.

Chomsky Families #

The Chomsky hierarchy classifies grammars by production restrictions:

1. Type 3, regular grammars, describe regular languages recognized by finite automata. Regular expressions and lexers operate here.
2. Type 2, context-free grammars (CFGs), have one nonterminal on the left of each production and are recognized by pushdown automata.
3. Type 1, context-sensitive grammars, restrict productions so they do not shorten sentential forms except for defined start-symbol cases.
4. Type 0, unrestricted grammars, impose no comparable production restriction.

Balanced delimiters illustrate the boundary. A finite automaton cannot remember an unbounded nesting depth, whereas a CFG can use recursion such as Group → '(' Group ')' Group | ε.

Derivations, Trees, and Ambiguity #

A derivation applies productions from a start symbol to terminals. A parse tree records that derivation’s hierarchical structure. A grammar is ambiguous when a string has more than one parse tree or equivalent leftmost derivation.

Expr → Expr '-' Expr | number

The input number - number - number has competing groupings under that grammar. Rewrite the grammar to encode associativity, for example with a left-recursive Expr → Expr '-' Term | Term, or use parser-generator precedence declarations when their conflict-resolution policy is intentional. Grammar structure is preferable when the resulting tree must directly represent the language’s semantics.

Top-Down and Bottom-Up Parsing #

An LL(\(k\)) parser reads left to right, constructs a leftmost derivation, and chooses a production from limited lookahead. Recursive-descent parsers implement this style directly; predictive grammars must eliminate left recursion and make alternatives distinguishable at their decision point.

An LR parser reads left to right and constructs the reverse of a rightmost derivation by shifting tokens and reducing recognized handles. LR-family parsers accommodate left-recursive expression grammars and a broader class of deterministic CFGs, but parser-generator conflicts signal an ambiguity or an insufficiently specified precedence policy.

Front-End Boundaries and Error Design #

A lexer groups characters into tokens such as identifiers, literals, operators, and source locations. A parser consumes those tokens according to grammar productions and produces a syntax tree or semantic actions. Keep lexical concerns—comments, escapes, numeric spelling—out of productions when they do not affect nesting or structure.

Design errors as part of the grammar interface. A lexer must identify invalid character sequences and advance safely. A parser should report the unexpected token and location, then synchronize at selected delimiters such as a statement terminator or closing brace. Recovery rules must guarantee progress; accepting arbitrary tokens only hides later errors and damages the resulting tree.