Parsing Interview Questions

Fundamentals of Parsing

Q1: What is parsing and what role does it play in compilation?

Parsing (syntax analysis) is the second major phase of compilation. It receives a stream of tokens from the lexer and determines whether they form a valid sentence according to the language's grammar. The output is a parse tree (or abstract syntax tree) that represents the hierarchical structure of the program. Think of parsing like diagramming a sentence in English — you identify the subject, verb, and object, revealing the underlying structure. Without parsing, the compiler would have a flat list of tokens with no way to understand that 3 + 4 * 5 means "add 3 to the product of 4 and 5" rather than "multiply the sum of 3 and 4 by 5."

Q2: Explain context-free grammars and why they are used for parsing.

A context-free grammar (CFG) consists of four components: a set of terminal symbols (tokens), a set of nonterminal symbols (syntactic categories), a start symbol, and a set of production rules. Each rule has the form A → α, where A is a single nonterminal and α is a sequence of terminals and nonterminals. CFGs are "context-free" because A can be replaced by α regardless of the surrounding symbols. CFGs are the perfect match for programming language syntax — powerful enough to express nesting (parentheses, blocks), recursion (nested if-else), and hierarchical structure, yet restricted enough that efficient parsing algorithms (LL, LR) exist.

Q3: What makes a grammar ambiguous and why does it matter?

A grammar is ambiguous if there exists at least one string that has two or more distinct parse trees (leftmost derivations). For example, the grammar E → E + E | E * E | id is ambiguous because id + id * id can be parsed as either (id + id) * id or id + (id * id). Ambiguity matters because different parse trees imply different evaluation orders and therefore different results. Compilers resolve ambiguity either by rewriting the grammar to enforce precedence through the rule hierarchy, or by adding precedence and associativity declarations (like %left and %right in Bison).

Q4: How do you eliminate left recursion from a grammar?

Left recursion (a rule like A → Aα | β) causes infinite recursion in top-down parsers because the parser keeps expanding A without consuming any input. The elimination algorithm transforms A → Aα | β into two rules: A → βA' and A' → αA' | ε. This converts left recursion into right recursion, which top-down parsers handle correctly. For example, E → E + T | T becomes E → TE' and E' → +TE' | ε. The language generated is identical, but the parsing behavior is safe.

Q5: What is left factorization and when do you need it?

Left factorization is needed when two productions for the same nonterminal begin with the same prefix, making it impossible for a predictive parser to decide which rule to apply with one lookahead token. For A → αβ | αγ, factoring produces A → αA' and A' → β | γ. Now the parser can consume α first, then use the next token to choose between β and γ. Example: S → if E then S else S | if E then S becomes S → if E then S S' and S' → else S | ε.

Top-Down Parsing

Q6: How does LL(1) parsing work?

LL(1) parsing is a predictive, table-driven, top-down method. "LL" means left-to-right scan with leftmost derivation; "(1)" means one token of lookahead. The parser maintains a stack initialized with the start symbol. At each step, if the top of the stack is a terminal, it must match the current input token (shift). If the top is a nonterminal A and the current token is a, the parser consults the parsing table at entry [A, a] to determine which production to apply. The table is built using FIRST and FOLLOW sets. If any table entry has multiple productions, the grammar is not LL(1).

Q7: How does recursive descent parsing work?

Recursive descent implements one function per nonterminal in the grammar. Each function examines the current token to decide which production to apply, then calls other functions (or matches terminals) according to the right-hand side of the chosen production. It is essentially a manual implementation of LL(1) parsing. The advantage is simplicity and flexibility — you can add error recovery, semantic actions, and lookahead heuristics directly in the code. Most production compilers (GCC, Clang, Go) use hand-written recursive descent parsers.

Bottom-Up Parsing

Q8: Explain the shift-reduce parsing strategy.

Bottom-up parsers work by building the parse tree from the leaves up to the root. The parser maintains a stack and repeatedly performs one of two actions: shift (push the next input token onto the stack) or reduce (replace a sequence of symbols on top of the stack with a nonterminal, according to a grammar rule). The key challenge is deciding when to shift and when to reduce — this is determined by the parser's state machine, encoded in ACTION and GOTO tables.

Q9: What is an LR item and how is it used?

An LR item is a grammar production with a dot (•) indicating how much of the right-hand side has been seen so far. For example, for A → XYZ, the items are: A → •XYZ (nothing seen), A → X•YZ (X seen), A → XY•Z (XY seen), A → XYZ• (complete — ready to reduce). Collections of items form the states of the LR parser's automaton. Each state represents a set of possible positions in various productions, and transitions between states are triggered by shifting symbols.

Q10: Compare SLR, LALR, and CLR parsers.

All three are LR parsing variants, differing in how they compute lookahead for reduce decisions. SLR uses FOLLOW sets — it reduces A → α when the next token is in FOLLOW(A). This is simple but sometimes causes false conflicts. CLR (LR(1)) computes per-item lookahead — each item carries the exact set of tokens that can follow this specific reduction. This eliminates all false conflicts but produces very large tables. LALR merges CLR states that have the same core items (ignoring lookahead), producing compact tables with almost no conflicts. LALR is the practical sweet spot and is used by Bison/YACC.

Q11: What are shift-reduce and reduce-reduce conflicts?

A shift-reduce conflict occurs when the parser, in a given state with a given lookahead, could either shift the token or reduce by some production — it does not know which is correct. A reduce-reduce conflict occurs when the parser could reduce by two different productions. Shift-reduce conflicts often arise from ambiguous constructs like the dangling else; they can be resolved by declaring precedence. Reduce-reduce conflicts usually indicate a more serious grammar design problem that requires rewriting the grammar.

Practical Parsing Topics

Q12: How do operator precedence and associativity work in parsers?

Precedence determines which operator binds tighter (multiplication before addition). Associativity determines how operators of equal precedence group (left-associative means a+b+c = (a+b)+c). In hand-written parsers, precedence is encoded by the grammar structure — separate nonterminals for each precedence level. In Bison, you declare %left '+' '-' and %left '*' '/' (later declarations have higher precedence), and the parser generator uses these to resolve conflicts automatically.

Q13: Explain the dangling else problem and its resolution.

Given if a then if b then s1 else s2, the grammar is ambiguous — the else could associate with either if. Most languages resolve this by associating the else with the nearest unmatched if. In LR parsing, this manifests as a shift-reduce conflict: when the parser sees else, it could reduce if b then s1 to a statement, or shift else to continue matching the inner if. The standard resolution is to prefer shift, which naturally associates else with the nearest if.

Q14: What is error recovery in parsing?

Error recovery allows the parser to continue after detecting a syntax error, finding additional errors in a single pass. Panic mode discards tokens until a synchronizing token (like ; or }) is found. Phrase-level recovery makes local corrections (insert a missing semicolon, delete an extra token). Error productions add rules like stmt → error ';' that match erroneous input and allow parsing to continue from the next statement.

Q15: How do Flex and Bison work together?

Flex generates the lexer function yylex() from regular expression patterns. Bison generates the parser function yyparse() from grammar rules. The parser calls yylex() whenever it needs the next token. They share token type definitions through the header file y.tab.h generated by Bison. Semantic actions in Bison rules access token values through $1, $2, etc. The complete workflow is: write .y and .l files, run Bison (produces parser), run Flex (produces lexer), compile and link both with a main program.

Q16: Can all programming languages be parsed by context-free grammars?

Not exactly. Most programming languages have context-sensitive features that CFGs cannot express — for example, the requirement that variables be declared before use, or that function calls have the right number of arguments. These are handled by the semantic analysis phase, not the parser. The parser uses a CFG to check syntactic structure, and semantic analysis checks the additional context-dependent constraints. Some languages (like C, where T * x could be a declaration or multiplication depending on whether T is a type) require limited feedback from the symbol table to the parser.

Q17: What is an Abstract Syntax Tree and how does it differ from a parse tree?

A parse tree includes every grammar symbol — even intermediate nonterminals that exist only for parsing convenience (like expr' from left-recursion elimination). An AST is a simplified tree that retains only the semantically meaningful structure: operators as internal nodes, operands as leaves, and grouping encoded by tree shape. For 3 + 4 * 5, the parse tree has many intermediate nodes for term, factor, etc., while the AST simply has + with children 3 and * (which itself has children 4 and 5). The AST is the standard representation used by subsequent compiler phases.