An Introduction to LL(1) Parsing

Last Update Time-stamp: "97/06/30 13:49:40 umrigar"

This is a brief intuitive introduction to LL(1) parsing. Any compiler text should provide more details. A elementary introduction to grammars and language analysis is also available.

Given a grammar, consider how one could write a parser for it. One possible approach would proceed as follows:

Keep a parse stack of grammar symbols which are expected in the input. Initially, the only grammar symbol expected in the input is the grammar start symbol; hence the stack is initialized to contain the start symbol. Then at each step of the parse, the action taken depends on the top grammar symbol.

If the symbol on top of the stack is a terminal, then if the current input lookahead matches the terminal on top of the stack, then the stack symbol is popped, and the input if advanced. If the terminal on top of the stack does not match the current lookahead, then an error is signalled.
If the symbol on top of the stack is a nonterminal, then it is popped off the stack. The nonterminal is used in conjunction with the current lookahead token to predict a rule to be used for that nonterminal. If no rule can be predicted, then an error is signalled. The grammar symbols on the RHS of the predicted rule are pushed onto the stack in reverse order, i.e. the first symbol on the RHS is pushed last. The input is not affected in any way.

In (2), the predict decisions can be encoded into a table called a LL(1) parse table. The table rows are indexed by nonterminals and table columns are indexed by terminals. The number of the rule predicted for nonterminal N with lookahead t is found at the intersection of row N and column t. If no rule can be predicted, then the table entry is left blank, signalling an error.

Feedback: Please email any feedback to zdu@acm.org.

Up to Parsing Demos Main Page