Parsing Practice Questions

(A) TRUE - Panic mode: discard tokens until a synchronising token is found. Simple and widely used. (B) TRUE - Phrase-level recovery: make local corrections (insert/delete/replace token) to allow parsing to continue. (C) TRUE - Error productions: augment the grammar with productions that recognise common errors (e.g., a rule for int x = ;). When this production fires, a specific error message is generated. (D) TRUE - Global correction: find the minimum number of insertions/deletions/replacements to transform the erroneous input into a valid string. Theoretically optimal but computationally expensive (O(n³) DP) - rarely used in practice.

(A) FALSE - Cascaded (spurious) errors are NOT real errors. They are false positives: the compiler reports them because its error recovery from a prior genuine error left it in a confused state. (B) TRUE - This is the definition: a cascaded error is an artifact of error recovery, not a true fault in the source program. If the programmer fixes the original error, cascaded errors typically disappear. (C) TRUE - Minimising cascaded errors is a key design goal of error recovery. Strategies like using FOLLOW sets in LL(1) parsers are specifically designed to reduce spurious reports. (D) TRUE - Panic mode skips tokens until a sync point, which can leave semantic context incomplete and cause false errors when parsing resumes.

The standard expression grammar E→E+T|T, T→TF|F, F→(E)|id: A: TRUE - it is LR(1) (and more specifically LALR(1)). B: TRUE - it is LALR(1); most LR parser generators (yacc/bison) accept this grammar directly. C: TRUE - it is left-recursive (E→E+T), making it unsuitable for LL parsing without transformation. LL(1) requires no left recursion. D: TRUE - multiplication has higher precedence than addition because T is lower in the derivation tree (closer to leaves); T→TF is deeper than E→E+T, so * binds more tightly.

In the best case, the current top state s already has a valid action on the error token - i.e., ACTION[s, error] = shift. In this case, no states need to be popped: the parser immediately shifts error and proceeds with token discarding until a synchronising token is found. Zero pops occur when the grammar has been designed with error productions at a high-level rule that encompasses the current parsing context. In the worst case, the parser may pop all states down to the initial state, discarding a large portion of the parse stack.

Parser hierarchy: LR(0): no lookahead; reduces whenever a complete item is found. SLR(1): uses FOLLOW(A) to decide when to reduce A → α (reduce only if next input is in FOLLOW(A)). More powerful than LR(0). LALR(1): merges CLR(1) states with identical LR(0) cores (same items ignoring lookaheads), combining their lookahead sets. Same number of states as LR(0)/SLR(1), more powerful than SLR(1). CLR(1): uses precise LR(1) items [A → α • β, a] where a is the exact lookahead; most powerful but potentially many more states than LALR(1). Power: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1). B is wrong - CLR(1) has more states; LALR(1) merges CLR(1) states.

Grammars NOT parseable by LR(1): A: TRUE - ambiguous grammars always produce conflicts (shift-reduce or reduce-reduce) in ANY LR parser because multiple parse trees exist for some input. No LR parser can handle ambiguous grammars without conflict resolution rules. C: TRUE - inherently ambiguous context-free grammars cannot be parsed deterministically. D: FALSE - LR parsers CAN handle left-recursive grammars (unlike LL parsers). Left recursion is handled naturally in bottom-up parsing. B: FALSE - all LALR(1) grammars are also LR(1) (LALR(1) ⊆ LR(1)); a grammar parseable by LALR(1) is certainly LR(1).

Tracing the parse of 'abbcde': (1) Shift a, shift b. Reduce b → A (reduce action 1): stack has 'a A'. (2) Shift b, shift c. Reduce Abc → A (but wait - stack top is bc, need Abc). Actually: after reducing first b→A, stack = aA. Shift b → aAb. Shift c → aAbc. Reduce Abc → A (reduce action 2): stack = aA A → aAA. Wait, this is wrong - let me retrace. Productions: S→aABe, A→Abc|b, B→d. Input: abbcde. Shift a, shift b → reduce b→A (action 1). Stack: aA. Shift b → aAb. Shift c → aAbc. Reduce Abc→A (action 2). Stack: aAA? No - A→Abc means the RHS is 'Abc', handle is stack top 'Abc'. Stack: aA, then shift b gives aAb, shift c gives aAbc, reduce Abc→A gives aAA. Hmm - this seems off. Correct trace: a,b,b,c,d,e: reduce b→A (1), reduce Abc→A (2), reduce d→B (3), reduce aABe→S (4). Total = 4 reduce actions.

For S→aAd|bBd|aBe|bAe, A→c, B→c: FOLLOW(A) = {d, e} (from S→aAd and S→bAe). FOLLOW(B) = {d, e} (from S→bBd and S→aBe). Both A→c and B→c are complete in the same state (the state reached after seeing 'c' from initial positions). In SLR(1) we would add: reduce A→c for {d,e} and reduce B→c for {d,e}. Both reductions apply for the same lookahead - reduce-reduce conflict. This grammar is LR(1) but NOT SLR(1): in LR(1) the context (whether we started with 'a' or 'b') distinguishes which reduction is correct, but FOLLOW sets lose this context.

A good compiler does NOT stop at the first error. It uses error recovery strategies to resume parsing after each error, reporting as many errors as possible in a single compilation run. This is important because fixing one error at a time and recompiling is very inefficient - the programmer benefits from seeing all (or most) errors at once. However, compilers must avoid reporting cascaded/spurious errors caused by earlier recovery decisions. The goal is: maximise true errors reported, minimise false positives from error recovery.

Ambiguous grammars in LR parsing: Shift-reduce conflicts: occur when the parser cannot decide whether to shift the next input or reduce the current stack top. Classic example: dangling else (S→if E then S | if E then S else S). Reduce-reduce conflicts: occur when two different reductions are possible for the same state and lookahead. Both can occur simultaneously in the same table. C is FALSE - LR parsers do not loop; they always terminate because each step either shifts (consuming input) or reduces (strictly decreasing stack+input length). Conflicts cause ambiguity in parse tree selection but not infinite loops.

In C, array dimensions must be of integral (integer) type. The declaration int arr[x] where x is a float violates this semantic rule. The lexical analyser correctly tokenizes all symbols. The parser accepts int arr[x]; as syntactically valid (it matches the declaration grammar). It is the semantic analyser's type-checking phase that detects the type mismatch: the array size expression x has type float but must be an integer. This is therefore a compile-time semantic error, caught during semantic analysis.

A shift-reduce parser uses four operations: Shift - moves the next input symbol onto the parse stack. Reduce - when the top of the stack matches the right-hand side (handle) of some production A → α, it replaces α with A (reduces). Accept - declared when the input is exhausted and the stack contains only the start symbol (successful parse). Error - declared when no valid shift or reduce action exists for the current state and input symbol.

All five major front-end and middle-end phases of a compiler can detect errors: (1) Lexical analysis - lexical errors (invalid characters, malformed tokens). (2) Syntax analysis (parsing) - syntactic errors (grammar violations). (3) Semantic analysis - semantic errors (type errors, undeclared identifiers, scope violations). (4) Intermediate code generation - errors in expressions that are semantically inconsistent at the IR level. (5) Code optimisation - detects unreachable code, use of uninitialised variables, etc. The back-end (code generation) can also detect errors (e.g., register allocation failure), but the five listed phases are the canonical answer expected in GATE.

Operator precedence parsing: A: TRUE - requires an operator grammar: no production has ε on the right or two consecutive non-terminals. This ensures a clean relationship between operators. B: TRUE - three precedence relations defined between grammar symbols: a ⋖ b (a yields precedence to b - shift b), a ≐ b (a has same precedence as b), a ⋗ b (a takes precedence over b - reduce when b is next). These are derived from operator precedence and associativity rules. C: TRUE - it cannot handle all deterministic context-free languages (less powerful than LR) but is simpler to construct and understand; widely used in expression parsing. D: FALSE - operator precedence parsing is a bottom-up technique, unrelated to LL(1).

When the LR parser performs reduce by production k (Ak → αk): (1) Pop 2×|αk| elements from the stack (each symbol on stack is represented by state+symbol pair, or |αk| states depending on implementation). (2) Let t be the state now on top of the stack. (3) Push GOTO[t, Ak] - the state reached from t on non-terminal Ak. (4) The output is production k (for parse tree construction). No input is consumed during a reduce action - the lookahead symbol stays unchanged. This implements the reverse of a rightmost derivation step, effectively replacing the handle αk with Ak.

CLOSURE(I) for a set of LR(0) items I: for every item A → α • B β in I, for every production B → γ in the grammar, add the item B → • γ to I (if not already present). Repeat until no new items can be added. This represents the fact that if the parser expects to see B next (dot before B), it must also be prepared to recognize any production that B can derive. CLOSURE essentially computes all items that are reachable from the current parsing state without consuming any input.

Bottom-up parsing methods: A: TRUE - all LR variants (LR(0), SLR(1), LALR(1), CLR(1)) are bottom-up parsers that use a stack-based shift-reduce mechanism. B: TRUE - operator precedence parsing is a bottom-up method that uses precedence relations between operators to decide shift or reduce. D: TRUE - shift-reduce parsing is the general framework underlying all LR parsers; LR parsers are specific implementations of shift-reduce parsing with a finite automaton guiding decisions. C: FALSE - recursive descent parsing is a top-down parsing technique that starts from the start symbol and recursively applies productions, working from root to leaves.

For the grammar S→L=R|R, L→*R|id, R→L: in SLR(1) parsing, consider state containing [S→R•] and [R→L•]. The complete item R→L• would require reduce if the next symbol is in FOLLOW(R). FOLLOW(R) includes '=' (from S→L=R). The item S→L•=R would require shift on '='. So in the state containing both [S→L•=R] (shift on =) and [R→L•] (reduce on = since =∈FOLLOW(R)), there is a shift-reduce conflict on '='. This grammar is LR(1) but not SLR(1) - the conflict is resolved in CLR(1) because FOLLOW(R) in context is more precise.