What is the difference between a lexer and a parser?

A lexer groups raw characters into tokens such as identifiers and operators, while a parser arranges those tokens into a hierarchical syntax tree according to the language's grammar.

What is the difference between LL and LR parsing?

LL parsers work top-down, predicting productions from the input prefix, while LR parsers work bottom-up, reducing recognized substrings; LR handles a strictly larger class of grammars but is more complex to construct.

Lexical and Syntactic Analysis

Lexical and syntactic analysis form a compiler's front end, breaking source text into tokens and recognizing its grammatical structure as a parse or syntax tree.

Definition

Lexical analysis is the phase that groups input characters into tokens, and syntactic analysis (parsing) is the phase that determines whether and how those tokens form a valid program according to a grammar, producing a syntax tree.

Scope

This topic covers lexical analysis, which converts character streams into tokens using regular languages and finite automata, and syntactic analysis (parsing), which recognizes the phrase structure of a program against a context-free grammar. It includes top-down (LL) and bottom-up (LR) parsing, parser generators, ambiguity and error recovery, and the construction of abstract syntax trees.

Core questions

How are regular and context-free languages used to describe program structure?
What are the trade-offs between LL and LR parsing?
How are ambiguity and parse errors detected and handled?
How is an abstract syntax tree built from a token stream?

Key theories

LR parsing: Knuth introduced LR parsing, a bottom-up technique that deterministically parses the broad class of LR grammars in linear time, forming the basis of many parser generators.
General context-free parsing: Earley's algorithm parses arbitrary context-free grammars, including ambiguous ones, providing a general method when restricted deterministic parsers are insufficient.
Regular and context-free foundations of the front end: The Dragon Book systematizes the use of regular expressions and finite automata for scanning and context-free grammars for parsing, including the standard LL and LR construction algorithms.

Clinical relevance

Lexing and parsing are foundational not only to compilers but to interpreters, linters, formatters, IDEs, and data-format processors. Robust parsing with good error recovery is essential to the developer experience of any language tooling.

History

Chomsky's formal language hierarchy in the late 1950s provided the theory of regular and context-free languages. Knuth formalized LR parsing in 1965, and Earley gave a general context-free algorithm in 1970. Parser generators like yacc made LR parsing practical, while later work explored parsing expression grammars and combinator-based parsers.

Debates

Generated versus hand-written parsers: Practitioners debate using parser generators from formal grammars, which are concise and verifiable, against hand-written recursive-descent parsers, which often give better error messages and control at the cost of more code.

Key figures

Donald Knuth
Jay Earley
Alfred Aho
Noam Chomsky

Seminal works

knuth1965
earley1970
aho2006

Frequently asked questions

What is the difference between a lexer and a parser?: A lexer groups raw characters into tokens such as identifiers and operators, while a parser arranges those tokens into a hierarchical syntax tree according to the language's grammar.
What is the difference between LL and LR parsing?: LL parsers work top-down, predicting productions from the input prefix, while LR parsers work bottom-up, reducing recognized substrings; LR handles a strictly larger class of grammars but is more complex to construct.