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.
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.
Copyright (C) 1997 Zerksis D. Umrigar
Feedback: Please email any feedback to zdu@acm.org.