Parsing Practice Questions

Error detection in a compiler identifies locations where the source program violates the rules of the language - whether lexical (invalid characters), syntactic (malformed structure), semantic (type mismatches), or logical (undefined variables). The compiler reports these violations with meaningful messages (line number, error type) so the programmer can fix them. Error detection does NOT automatically fix errors (that is error recovery's role), and it spans multiple phases - lexical analysis, parsing, and semantic analysis - not only code generation.

A shift-reduce conflict occurs in state s with input symbol a when: (1) There is a complete item in state s (A → α •) indicating a reduce is possible, AND (2) There is also a non-complete item (B → β • a γ) in state s indicating a shift on a is also possible. The parser cannot decide whether to reduce A → α or shift a. Example: the dangling else problem causes a shift-reduce conflict. Resolution: usually prefer shift over reduce (which correctly resolves the dangling else by associating else with the nearest if). A reduce-reduce conflict occurs when two different complete items exist in the same state.

LALR(1) merges CLR(1) states with the same LR(0) core (same items ignoring lookaheads). Merging can introduce reduce-reduce conflicts: if state s1 has [A→α•, a] and [B→β•, b] and state s2 has [A→α•, b] and [B→β•, a], after merging into one state s: both A→α• and B→β• have lookaheads {a,b} - reduce-reduce conflict on both a and b, which didn't exist in CLR(1). Crucially, merging CANNOT introduce new shift-reduce conflicts - because the LR(0) cores are identical, the shift actions are the same in both states being merged. This is why LALR(1) can have reduce-reduce conflicts that CLR(1) does not have.

SLR(1) reduce action construction: place reduce by A → α (say production number r) in ACTION[s, a] for all a ∈ FOLLOW(A), when state s contains the complete LR(0) item A → α •. FOLLOW(A) is used as the lookahead approximation - we reduce only when the next input symbol could legally follow A. This is less precise than CLR(1) which uses exact lookaheads from LR(1) items. If a ∉ FOLLOW(A), no reduce action is placed in ACTION[s, a], reducing but not eliminating conflicts compared to LR(0).

(A) TRUE - This is the fundamental distinction. Compile-time errors are caught before execution (by the compiler/linker). Runtime errors occur during execution and are not detectable beforehand in the general case. (B) TRUE - Syntax errors (grammar violations) are always caught at compile time by the parser. Divide-by-zero (unless the divisor is a literal constant caught by constant folding) is a runtime error since the divisor's value is generally not known until execution. (C) FALSE - This is precisely the halting problem: it is undecidable in general to determine all runtime errors statically. A compiler can catch some (constant folding, data flow analysis) but not all. (D) TRUE - Semantic errors span both compile time (type checking) and runtime (bounds checking, null dereference).

Panic mode is the simplest and most widely used error recovery strategy. On detecting an error, the parser discards input symbols one at a time until it finds a token belonging to a designated set of synchronising tokens - typically statement terminators like ; or block delimiters like } or end. Parsing then resumes from that point. Advantages: simple to implement, guarantees the parser never loops. Disadvantage: it may skip a large portion of input, missing several errors. It does NOT insert tokens (that is phrase-level recovery) or backtrack (that is backtracking parsers).

In LL(1) panic mode recovery with synchronising sets: if token a ∈ FIRST(A), use the appropriate production. If a ∈ FOLLOW(A), pop A (treat as if A derived ε). If a is in neither set, it is an unexpected token - discard a (advance the input) and try again with the next token. The parser keeps discarding tokens until it finds one in FIRST(A) ∪ FOLLOW(A). This strategy - discard input when the token is in neither set - avoids popping the stack prematurely and gives the best chance of resynchronising with the actual intent of the program.

In LL(1) panic mode recovery, the synchronising set for non-terminal A is chosen as FIRST(A) ∪ FOLLOW(A). FIRST(A) tokens can begin a valid derivation of A - if the current token is in FIRST(A), the parser can attempt to parse A normally. FOLLOW(A) tokens appear after A in the grammar - if the current token is in FOLLOW(A), A is popped from the stack (treated as having been parsed as ε) and parsing continues. This two-set approach handles both 'missing A' and 'extra tokens within A' scenarios, minimising cascaded errors.

(A) TRUE - Recursive descent parsers are hand-written, so each procedure for a non-terminal can implement its own tailored error recovery. This modularity is an advantage over table-driven parsers. (B) FALSE - Recursive descent parsers can absolutely implement panic mode recovery - each procedure discards tokens until a synchronising token is found before returning. (C) TRUE - FOLLOW sets indicate what comes after a non-terminal, so tokens in FOLLOW(A) serve as natural synchronisation points when parsing A fails. (D) TRUE - Since the parser is hand-written, the programmer can insert a token by calling the procedure for the expected terminal without consuming input, or delete a token by advancing past it - implementing phrase-level recovery directly.

Bottom-up parsing begins with the input string (leaves of the parse tree) and works upward by repeatedly applying grammar productions in reverse (reducing) until the start symbol is reached. This is the reverse of a rightmost derivation. The parser reads input left-to-right and builds the parse tree from leaves to root. Contrast with top-down parsing which starts from the start symbol and works down to the input.

(A) TRUE - Clear, precise error messages with file, line, and column information are essential for programmer productivity. Vague messages like 'syntax error' are insufficient. (B) TRUE - The ability to continue parsing after an error (error recovery) and find multiple errors in one pass is a key quality metric of a compiler. (C) TRUE - Error handling code runs on all programs including correct ones (e.g., FIRST/FOLLOW table lookups). It must be fast enough not to degrade performance for error-free programs. (D) FALSE - Automatically fixing all errors is neither feasible nor desirable. The compiler cannot know the programmer's intent. Attempting to 'fix' errors may produce a semantically different program. Compilers should report errors, not silently correct them.

Compile-time semantic errors are violations of the language's semantic rules detectable by static analysis - without running the program. A type mismatch (assigning an int to a float variable in a strictly typed language) is detected during semantic analysis (type checking phase) at compile time. Option A (division by zero) may be detectable by a smart compiler through constant folding, but is typically a runtime error. Options C and D are classic runtime errors - array bounds and recursion depth depend on runtime values not known at compile time.

GOTO(I, X) computes the set of items reachable from state I after seeing grammar symbol X (terminal or non-terminal). It takes all items in I that have the dot immediately before X (A → α • X β), moves the dot past X (A → α X • β), and then computes the CLOSURE of this new set. GOTO represents transitions in the LR automaton (canonical collection of LR(0) item sets) - each state is a set of LR items, and transitions are labeled by grammar symbols.

Lexical errors occur when the scanner cannot form a valid token from the input characters. An illegal character such as @ in an identifier (if the language does not allow it) is a lexical error - it does not match any token pattern in the language. Option A (undeclared variable) is a semantic error. Option B (missing expression) is a syntactic error detected by the parser. Option D (wrong argument count) is a semantic error. Lexical errors are the simplest class and are detected earliest in compilation.

The token y is lexically valid (a legal identifier) and syntactically valid (an identifier can appear in an expression). The error is semantic: y has not been declared in any enclosing scope. During semantic analysis, the compiler looks up each identifier in the symbol table. Finding no entry for y, it reports an 'undeclared identifier' or 'undefined variable' error. This is a classic compile-time semantic error. It is NOT a lexical error (y is a valid identifier pattern) and NOT a syntactic error (the statement x = y + 2; is grammatically correct).

Yacc/Bison characteristics: A: TRUE - default conflict resolution: shift-reduce conflict → prefer shift (handles dangling else correctly). B: TRUE - reduce-reduce conflict → choose the production that appears first in the yacc grammar file. Both resolutions generate a warning but not an error. C: TRUE - yacc generates an LALR(1) parser; it takes a BNF-like grammar specification and produces C code implementing the parser. D: FALSE - yacc CAN handle ambiguous grammars using conflict resolution rules (precedence and associativity declarations: %left, %right, %nonassoc, %prec). Many practical grammars used with yacc are technically ambiguous but disambiguated using these declarations.

Viable prefixes: A: TRUE - a viable prefix of a right-sentential form γ = αβw is any prefix of αβ (where β is the handle). It does not extend past the right end of the handle. B: TRUE - the set of all viable prefixes of all right-sentential forms of a grammar is a regular language. This is a fundamental theorem: the LR(0) automaton exactly recognizes this regular language of viable prefixes. C: TRUE - an LR parser maintains the invariant that the stack always contains a viable prefix; if the stack ever contains something that is not a viable prefix, it is an error state. D: FALSE - a viable prefix can consist entirely of non-terminals (e.g., after several reductions).

(A) TRUE - Error productions augment the grammar with rules like expr → expr + + expr to recognise a doubled operator. When such a rule fires, the parser knows exactly what mistake occurred. (B) TRUE - Since the error production explicitly matches a known mistake, the parser can emit a precise, helpful message such as 'duplicate operator +' rather than a generic syntax error. (C) TRUE - Adding error productions increases the grammar size and therefore the parser table size, but the benefit is graceful, informative recovery for common mistakes. (D) FALSE - Error productions handle syntactic errors (grammar-level mistakes), not semantic errors (type mismatches, undeclared variables, etc.). Semantic errors are caught during semantic analysis.