1 Definition and purpose
A parsing table is a structured lookup aid used in syntactic analysis to help a parser choose among possible actions while reading an input string. It encodes information derived from a formal grammar so that the parser can determine how to proceed without repeatedly reanalyzing the grammar from scratch. In practice, this makes parsing faster, more systematic, and easier to automate.
Parsing tables are central to many compiler and language-processing techniques. They are especially important in deterministic parsing methods, where the next action can be selected by consulting a table rather than relying on extensive backtracking or trial-and-error.
1.1 Role in syntactic analysis
In syntactic analysis, the parser checks whether a sequence of tokens conforms to the rules of a grammar. A parsing table supplies the parser with a precomputed guide for this task. Depending on the parsing strategy, the table may tell the parser which production to expand, which symbol to shift, which reduction to perform, or when to report an error.
This guidance reduces the need for ad hoc decision making. It also allows a parser to process input in a predictable way, which is useful for both compiler construction and formal language study.
1.2 Relationship to formal grammars
Parsing tables are built from formal grammars, especially context-free grammars. The grammar defines the language, while the table translates grammatical structure into operational instructions for a parser. As a result, the table is not an independent artifact; it is a derived representation of grammar behavior.
Different grammar forms lead to different table styles. For example, top-down parsers use tables that reflect what production should be chosen for a nonterminal and lookahead token, while bottom-up parsers use tables that reflect parser states and input symbols.
1.3 Parser decision making
A parser often must decide among several possible actions at a given point in the input. The parsing table simplifies this by associating each relevant condition with a single prescribed step when the grammar is suitable for deterministic parsing. If the table entry is empty or inconsistent, the parser can conclude that the input does not match the expected grammar.
In this way, the table serves both as a control mechanism and as a compact representation of parsing logic. It helps enforce consistency in the parser’s behavior and supports reliable error reporting.
2 Types of parsing tables
Parsing tables vary according to the parsing method they support. The most common families are LL tables, LR tables, and operator precedence tables. Each type reflects a different way of organizing the parsing process and emphasizes different grammar properties.
2.1 LL parsing tables
LL parsing tables are used in predictive, top-down parsing. The parser reads input from left to right and constructs a leftmost derivation. The table typically maps a nonterminal and a lookahead token to the production that should be applied.
These tables are especially associated with grammars that are easy to predict without backtracking. Their structure makes them compact and intuitive for grammar-driven expansion.
2.1.1 FIRST and FOLLOW sets
FIRST and FOLLOW sets are foundational tools in the construction of LL tables. FIRST describes which terminals may begin strings derived from a grammar symbol, while FOLLOW describes which terminals may appear immediately after a nonterminal in some sentential form.
These sets help determine where each production belongs in the table. They are also used to handle empty, or epsilon, productions in a controlled way.
2.1.2 Predictive parsing entries
Each entry in an LL parsing table typically corresponds to a pair consisting of a nonterminal and a lookahead terminal. If the lookahead token belongs to the FIRST set of a production’s right-hand side, that production is placed in the relevant table entry. If the production can derive the empty string, FOLLOW information is also considered.
Well-formed LL tables have at most one production in each entry. Multiple candidates in the same cell indicate that the grammar is not suitable for simple predictive parsing without modification.
2.2 LR parsing tables
LR parsing tables support bottom-up parsing, where the parser reads input left to right and constructs a rightmost derivation in reverse. These tables are more powerful than LL tables and can handle a broader class of grammars.
An LR table usually contains two parts: one for actions and one for transitions between states. Its structure is tied to an automaton built from grammar items.
2.2.1 ACTION table
The ACTION table tells the parser what to do when it is in a given state and sees a particular input token. Possible actions include shift, reduce, accept, or error. Shift moves the parser forward by reading a token, while reduce replaces a recognized sequence of symbols with a nonterminal according to a production.
The ACTION table is the main decision table in LR parsing. Its entries reflect the parser’s current state of partial recognition.
2.2.2 GOTO table
The GOTO table records how the parser transitions after completing a reduction and exposing a nonterminal. It maps a parser state and a nonterminal to the next state. This table is essential for maintaining the state machine that underlies LR parsing.
Together, ACTION and GOTO form a coordinated control system. ACTION handles terminal-driven behavior, while GOTO manages nonterminal transitions.
2.2.3 Canonical collection of items
The canonical collection of items is the set of grammar item states from which an LR table is derived. Each item represents a production together with a marker showing how much of the production has already been recognized. These items are assembled into states of an automaton.
This collection determines the parser’s state space. The transitions among these states are translated into table entries that guide the parser’s moves.
2.3 Operator precedence tables
Operator precedence tables are used for grammars in which binary or unary operators follow precedence and associativity rules. They encode relationships such as whether one operator should bind more tightly than another or whether two operators may be compared at all.
These tables are especially useful for expression parsing. They provide a compact way to handle arithmetic-like structures where precedence and associativity are the main concerns.
3 Construction methods
Parsing tables are not usually written by hand for complex grammars. Instead, they are generated from grammar rules using systematic procedures. The construction method depends on the parsing family and the shape of the grammar.
3.1 Building LL tables
Constructing an LL table begins by analyzing the grammar’s productions and identifying the terminals that can appear at each decision point. The process aims to ensure that each table entry contains at most one applicable production.
Because LL parsing depends on immediate prediction, the grammar often must be rewritten into a more suitable form before table generation.
3.1.1 Eliminating left recursion
Left recursion occurs when a nonterminal can derive a string beginning with itself. This is problematic for many top-down parsers because it can lead to infinite recursion during prediction.
To build an LL table, left-recursive rules are often transformed into equivalent right-recursive or iterative forms. This rewrite preserves the language while making the grammar more compatible with predictive parsing.
3.1.2 Left factoring
Left factoring is a grammar transformation used when multiple productions share a common prefix. By factoring out the shared portion, the parser can delay its choice until enough input has been examined.
This transformation simplifies table filling because it reduces ambiguity in early decision points. It is especially useful when two or more productions would otherwise compete for the same table entry.
3.2 Building LR tables
LR table construction is based on state machines derived from grammar items. The parser generator computes item sets, transitions between them, and the actions associated with each state and input token.
Although the resulting tables can be large, they are often robust and able to handle a wide range of grammars.
3.2.1 Item sets and automata
The first step in LR table construction is forming item sets. Each set represents a parser state, and transitions between sets correspond to shifting grammar symbols. The collection of these states can be viewed as a deterministic automaton.
This automaton captures the progress of parsing in a compact form. The table entries are then filled according to the transitions and completed items found in each state.
3.2.2 Shift and reduce rules
Shift and reduce rules are used to populate the ACTION table. A shift action is entered when the automaton can consume the next input token and move to a new state. A reduce action is entered when a production has been fully matched and the parser should replace the recognized sequence with its left-hand-side nonterminal.
The balance between shift and reduce actions determines the parser’s behavior at many points. Correct table construction ensures that these actions reflect the intended grammar structure.
3.2.3 Conflict detection
Conflicts arise when a table entry would require more than one action. In LR parsing, the most common are shift-reduce conflicts and reduce-reduce conflicts. These indicate that the grammar or the chosen LR method does not fully determine a unique action for that state and token.
Conflict detection is an important part of table generation. It helps parser designers identify ambiguous or unsuitable grammar constructions and decide whether to revise the grammar or use a stronger parsing technique.
4 Use in parsing algorithms
Parsing tables are the operational core of table-driven parsers. They tell the parser how to proceed at each step, whether by expanding a nonterminal, shifting a token, or reducing a recognized phrase.
4.1 Top-down parsing
In top-down parsing, the parser begins with the start symbol and attempts to derive the input string by expanding grammar rules. The parsing table directs these expansions based on the current nonterminal and the next input symbol.
This method is often associated with recursive-descent style logic, though the table provides a nonrecursive alternative. Predictive parsing is a common table-driven top-down approach.
4.2 Bottom-up parsing
In bottom-up parsing, the parser starts with the input and works toward the start symbol by recognizing patterns and reducing them to higher-level constructs. The parsing table controls when the parser shifts input symbols and when it reduces them according to grammar productions.
LR parsing is the best-known table-driven bottom-up method. Its tables allow the parser to recognize handles efficiently and build a structured interpretation of the input.
4.3 Error detection and recovery
Parsing tables help detect errors when no valid action is available for the current state and lookahead token. In such cases, the parser can report that the input does not match the grammar at that point.
Some systems also use recovery strategies, such as synchronizing on selected tokens or skipping invalid input until parsing can resume. Table-based parsing can support these methods because error conditions are often localized to specific states and symbols.
5 Table properties and limitations
Parsing tables are useful, but they are not universally applicable. Their effectiveness depends on grammar structure, table size, and the determinism of the parsing method.
5.1 Determinism and ambiguity
A well-formed parsing table usually assumes deterministic behavior. If a grammar is ambiguous, or if the parsing method is too weak for the grammar, the table may contain conflicts or multiple possible actions in the same entry.
Ambiguity does not always make parsing impossible, but it often prevents clean table construction. In such cases, the grammar may need rewriting or a different parsing strategy may be required.
5.2 Table size and efficiency
Parsing tables can become large, particularly for LR-based methods with many states. Larger tables may increase memory use, though they often provide fast lookup during parsing.
There is therefore a trade-off between power and compactness. More expressive parsing techniques usually require more elaborate tables, while simpler methods produce smaller but less flexible ones.
5.3 Grammar constraints
Not every grammar is suitable for every parsing table type. LL parsing commonly requires elimination of left recursion and careful factoring, while LR parsing tolerates a broader range of grammars but can still encounter conflicts.
These constraints influence how a language is specified. Grammar authors often adapt rules to fit the intended parser rather than relying on the parser to handle arbitrary structure.
6 Examples
Examples help illustrate how parsing tables encode grammar decisions. Even small grammars can show the essential logic behind table-driven parsing.
6.1 Simple grammar example
Consider a simple expression grammar with rules for expressions, terms, and factors. Such a grammar might distinguish addition from multiplication and allow identifiers or parenthesized expressions as factors.
This kind of grammar is frequently used because it demonstrates nesting, precedence, and recursive structure in a compact form. It is also suitable for showing how a parser selects productions based on the current input symbol.
6.2 Sample LL parsing table
In an LL parsing table for a simple expression grammar, the parser might use the lookahead token to decide whether an expression should begin with a term, an identifier, or an opening parenthesis. Each nonterminal and terminal pair points to the production that matches the expected form.
If the lookahead does not fit any production, the table entry remains empty. This signals an error or a mismatch between the input and the grammar.
6.3 Sample LR parsing table
A sample LR parsing table for the same grammar would contain states representing partial recognition of expressions and operators. The ACTION portion would specify when to shift an identifier or operator and when to reduce a completed subexpression.
The GOTO portion would show which state follows after reducing to a nonterminal such as expression or term. Together, these tables guide the parser through a sequence of shifts and reductions until the input is accepted.
7 Applications
Parsing tables are widely used wherever structured language input must be analyzed reliably. Their role extends beyond compilers into broader language-processing tools.
7.1 Compiler front ends
In compiler front ends, parsing tables support syntax analysis after lexical scanning. They help convert token streams into parse trees or abstract syntax trees, which are then used in later compilation stages.
Their deterministic nature makes them a practical foundation for automated parser generators. This is one reason table-driven parsing has long been a standard part of compiler design.
7.2 Language processors
Language processors include interpreters, code analyzers, formatters, and documentation tools that need to understand structured input. Parsing tables provide a disciplined way to process such languages consistently.
They are useful whenever the input follows a formal grammar and predictable parsing behavior is desirable. Their use can improve maintainability by separating grammar specification from parsing control logic.
7.3 Syntax-directed translation
Syntax-directed translation associates parsing with semantic actions such as building intermediate representations or generating output. Parsing tables support this by identifying exactly when each grammar rule should be recognized and applied.
Because table-driven parsers expose clear points of reduction or expansion, they integrate well with translation schemes. This makes them valuable in systems that attach meaning or computation to grammatical structure.