Parsing Techniques

Definition

A parsing technique is a concrete algorithm/strategy for building a parser from a grammar.

Key Points

• Recursive Descent: one recursive procedure per non-terminal; simple but needs no left recursion, may need backtracking for ambiguous choices.
• Predictive (Table-Driven LL) Parsing: uses a parsing table built from FIRST/FOLLOW sets; no backtracking; O(n) time.
• Operator-Precedence Parsing: a simple bottom-up method for expression grammars using precedence relations (<·, ·>, =) between terminal pairs.
• Shift-Reduce Parsing: general bottom-up strategy — repeatedly shift tokens onto a stack, then reduce a handle (right side of a production) to its non-terminal.
• LR Parsing (SLR/CLR/LALR): table-driven shift-reduce parsing using item sets (states); most powerful and used by real compiler tools.

Example

Operator precedence parsing on id + id * id: precedence table gives * higher binding than +, so the parser shifts through * before reducing, correctly grouping id * id first.

📌 CSS Frequency: Moderate — usually tested via a specific technique (e.g., "parse using operator precedence") rather than a generic listing question.

Model Answer (short)

"Parsing techniques range from simple recursive-descent and table-driven predictive (LL) parsing for top-down analysis, to operator-precedence, shift-reduce, and LR parsing (SLR/CLR/LALR) for bottom-up analysis. The choice depends on grammar complexity: LL techniques suit simple, non-left-recursive grammars, while LR techniques handle the broader class of grammars found in real programming languages."