What is 'Left Factoring' used for in syntax analyzer design?
Left factoring factors out common prefixes: A -> $\alpha A'$ and A' -> beta1 | beta2, enabling predictive parsers to pick the right choice with 1 lookahead token.
What is the computational complexity of parsing arbitrary context-free grammars using general algorithms like Earley's algorithm or CYK algorithm?
General CFG parsers (Earley, CYK) run in O($n^3)$ time for arbitrary CFGs, whereas deterministic parsers (LL, LR) operate in O(n) linear time.
In SLR(1) parsing table construction, when is a Reduce action A -> alpha placed in the ACTION table for state $I_{i}$?
SLR(1) reduces items [A -> alpha.] under lookahead column 'a' only if 'a' is in FOLLOW(A).
Which statement correctly describes the relationship between grammar hierarchy parser inclusion sets?
The expressive power subset inclusion order is LL(1) strictly contained in SLR(1) strictly contained in LALR(1) strictly contained in CLR(1).
Which of the following grammar transformations changes the language defined by the Context-Free Grammar?
Modifying production symbols alters generated strings and changes L(G), whereas removing useless or unreachable non-terminals preserves language equivalence.