Autometa & Compiler design (CY-603 (C)) - Important Questions

Define a context-free grammar (CFG). Explain the terms terminal, non-terminal, start symbol and production with suitable examples. Give two simple CFGs: one generating balanced parentheses and another generating arithmetic expressions with $+$ and $\times$ operators.

For the grammar:

$S \rightarrow A\,b\mid C\,d$

$A \rightarrow a\mid \varepsilon$

$C \rightarrow c\,S\mid \varepsilon$

compute the $FIRST$ and $FOLLOW$ sets for all non-terminals. Show all steps.

Given the grammar:

$E \rightarrow T\;E'$

$E' \rightarrow +\;T\;E'\mid \varepsilon$

$T \rightarrow F\;T'$

$T' \rightarrow \times\;F\;T'\mid \varepsilon$

$F \rightarrow (\;E\;)\mid id$

(a) Compute $FIRST$ and $FOLLOW$ sets for all non-terminals.

(b) Construct the LL(1) parsing table.

(c) Use the table to show the steps of parsing the input $id\;+\;id\;\times\;id$.

Explain the elimination of left recursion and left factoring with examples. Transform the grammar:

$A \rightarrow A\alpha \mid \beta \mid \gamma\;$

into an equivalent grammar suitable for predictive parsing by eliminating left recursion and applying left factoring where necessary.

For the grammar:

$S' \rightarrow S$

$S \rightarrow C\;C$

$C \rightarrow c\;C\mid d$

(a) Construct the canonical collection of LR(0) items (states).

(b) Build the SLR parsing table using $FOLLOW$ sets.

(c) Show the parsing actions for the input $c\;c\;d\;d$ and identify any shift-reduce or reduce-reduce conflicts (if present).

Explain the differences between SLR, LALR and CLR (canonical LR(1)) parsers. Illustrate with an example grammar where SLR fails but LALR or CLR succeeds, and explain why.

For the grammar:

$S' \rightarrow S$

$S \rightarrow L\;=\;R\mid R$

$L \rightarrow *\;R\mid id$

$R \rightarrow L$

(a) Construct the canonical collection of LR(1) items.

(b) Build the LR(1) parsing table.

(c) Use the table to parse the input $id\;=\;id$ and show stack configurations and actions.

Demonstrate shift-reduce parsing (using a shift-reduce parser) for the grammar:

$S \rightarrow a\;S\;b\mid a\;b$

on the input $a\;a\;b\;b$. Show the stack contents, the remaining input, and the action (shift or reduce) at each step. Draw the final parse tree.

Define shift-reduce and reduce-reduce conflicts in bottom-up parsers. For the expression grammar:

$E \rightarrow E\;+\;E\mid E\;*\;E\mid (\;E\; )\mid id$

(a) Show how shift-reduce conflicts arise in an LR(0) or SLR table.

(b) Explain how operator precedence and associativity can be used to resolve these conflicts with an example.

What is an ambiguous grammar? Provide an example of an ambiguous grammar for arithmetic expressions and show two different parse trees for the same string. Then present an unambiguous grammar that generates the same language (respecting operator precedence and associativity).