Compiler Design

Choose the correct answer of the following:
A bottom-up parser generates
(i) right-most derivation
(ii) right-most derivation in reverse
(iii) left-most derivation
(iv) left-most derivation in reverse

Choose the correct answer of the following:
Which one of the following statements is true?
(i) Canonical LR parser is more powerful than LALR parser.
(ii) SLR parser is more powerful than LALR.
(iii) LALR parser is more powerful than canonical LR parser.
(iv) SLR parser, canonical LR parser and LALR parser all have the same power.

Choose the correct answer of the following:
Which of the following statement is true?
(i) Every left recursive grammar can be LL(1)
(ii) LL(1) grammar can be ambiguous
(iii) both (i) and (ii)
(iv) None of these

Choose the correct option / answer the following:
Which grammar type is recognized by a push-down automaton?
(i) Regular
(ii) Context-free
(iii) Context-sensitive
(iv) Unrestricted

Choose the correct answer of the following:
A grammar that produces more than one parse tree for some sentence is said to be
(i) Ambiguous
(ii) context free
(iii) disambiguous
(iv) regular

Choose the correct answer of the following:
A bottom-up parser generates
(i) right most derivation
(ii) right most derivation in reverse
(iii) right most derivation
(iv) left most derivation in reverse

Choose the correct option / answer the following:
Which of the following parsers uses a stack and rightmost derivation in reverse?
(i) LL Parser
(ii) Top-down parser
(iii) LR Parser
(iv) Operator parser

Which parser uses leftmost derivation?

(i) LL parser
(ii) Bottom-up parser
(iii) LR parser
(iv) Operator precedence parser

Choose the correct answer of the following:
For a grammar G, shift reduce (S-R) conflicts are present in LALR(1) parser, if and only if
(i) the LR(1) parser for G has S-R conflicts
(ii) the LR(0) parser for G has S-R conflicts
(iii) the SLR(1) parser for G has S-R conflicts
(iv) the SLR(0) parser for G has S-R conflicts

Choose the correct answer of the following:
Consider the following grammar:
$S \rightarrow cAd$
$A \rightarrow ab | ac | a.$
For input string cad, how many times the recursive descent parser will backtrack?
(i) 2
(ii) 3
(iii) 4
(iv) 5

Choose the correct answer of the following:
Grammar of the programming is checked in ......... phase of compiler.
(i) semantic analysis
(ii) code generation
(iii) syntax analysis
(iv) code optimization

LR parsing is a

(i) Top-down parsing
(ii) Bottom-up parsing
(iii) Recursive parsing
(iv) Predictive parsing

Choose the correct answer of the following:
________ is a top-down parser.
(i) Operator precedence parser
(ii) An LALR (k) parser
(iii) An LR (k) parser
(iv) Recursive descent parser

Choose the correct answer of the following:
Arrange the following parser according to their power (low to high): SLR, CLR, LALR.
(i) LALR, CLR, SLR
(ii) LALR, SLR, CLR
(iii) CLR, LALR, SLR
(iv) CLR, SLR, LALR

Which parsing technique is most powerful?

(i) LL(1)
(ii) Recursive descent
(iii) LR(1)
(iv) Operator precedence

Choose the correct answer of the following:
What is the similarity between LR, LALR and SLR?
(i) Use of same algorithm, but different parsing table
(ii) Same parsing table, but different algorithm
(iii) Their parsing tables and algorithms are similar but use top-down approach
(iv) Both parsing tables and algorithms are different.

Choose the correct answer of the following:
After removing left recursion from $A \rightarrow A\alpha / \beta$ , the resulting grammar will be
(i) $A \rightarrow \beta A'$
(ii) $A \rightarrow \alpha A'$
(iii) $A \rightarrow \alpha \beta A''$
(iv) $A \rightarrow \beta \alpha A'$

Choose the correct answer of the following:
Handle pruning forms the basis of ...........?
(i) Bottom up parsing
(ii) Top down parsing
(iii) Predictive parsing
(iv) Recursive descent parsing

Choose the correct answer of the following:
To convert an arbitrary CFG to an LL(1) grammar
(i) factor the grammar alone
(ii) remove left recursion alone
(iii) remove left recursion and factor the grammar
(iv) None of the above

Choose the correct answer of the following:
If x is a terminal then FIRST(x) is
(i) $\epsilon$
(ii) {x}
(iii) x*
(iv) xx*

Choose the correct answer of the following:
Left factoring guarantees?
(i) Not occurring of backtracking
(ii) Cycle free parse tree
(iii) Error free target code
(iv) Correct LL(1) parsing table

Choose the correct answer of the following:
If a grammar is LALR(1), then it is necessarily
(i) SLR(1)
(ii) LR(1)
(iii) LL(1)
(iv) None of the above

Choose the correct option / answer the following:
Which of the following parsers can parse ambiguous grammars?
(i) LL(1)
(ii) Operator Precedence
(iii) CLR(1)
(iv) None of the above

What is bottom-up parsing? Discuss shift reduce parsing technique in brief. What is a handle?

Consider the following grammar:
$S \rightarrow 0S0 | 1S1 | 10$
(a) Find LR(0) collection of items for the above grammar.
(b) Construct SLR parsing table.
(c) Trace whether the string "01100" is accepted or not.

What is left recursion? Eliminate the left recursion from the following grammar :
$E \rightarrow E+T|T$
$T \rightarrow T*F|F$
$F \rightarrow (E)|id$

Consider the following grammar:
$S \rightarrow S(S)S/\epsilon$
(i) Left factor this grammar.
(ii) Eliminate left recursion from original grammar.
(iii) Is the resulting grammar suitable for top-down parsing?

Prove that the following grammar is ambiguous on string 'aab':

$$S \rightarrow aS \mid aSbS \mid \varepsilon$$

Given a context-free grammar (CFG), compute FIRST and FOLLOW sets for all non-terminals, and construct the LL(1) parsing table. Also, determine whether the grammar is LL(1) or not.
Grammar:
$S \rightarrow A B$
$A \rightarrow a A | \epsilon$
$B \rightarrow b B | \epsilon$

Explain top-down and bottom-up parsing techniques.

Construct LALR(1) parsing table for the following grammar. Also prove that this is not SLR(1).
$S \rightarrow Aa | bAc | dc | bda$
$A \rightarrow d$

Show that the following grammar is LL(1) but not SLR(1).
$S \rightarrow AaAb/BbBa$
$A \rightarrow \epsilon$
$B \rightarrow \epsilon$

Consider the following grammar:
$E \rightarrow E + T | T$
$T \rightarrow T * F | F$
$F \rightarrow (E) | id$

Construct the canonical collection of LR(0) items.

Describe the working of LL(1) parser. Draw the LL(1) parsing table for the given grammar:

$$S \rightarrow aA \mid bB$$
$$A \rightarrow a$$
$$B \rightarrow b$$

Explain architecture and algorithm for the non-recursive predictive parser.

What is shift-Reduce conflict?

Consider the following grammar:
$E \rightarrow E + T | T$
$T \rightarrow T * F | F$
$F \rightarrow (E) | id$

Build the SLR(1) parsing table using the above items.

Consider the following grammar:
$E \rightarrow E + T | T$
$T \rightarrow T * F | F$
$F \rightarrow (E) | id$

Determine whether the grammar is SLR(1), clearly stating any shift-reduce or reduce-reduce conflicts.

Consider the following grammar:
$E \rightarrow E + T | T$
$T \rightarrow T * F | F$
$F \rightarrow (E) | id$

Parse the string id + id * id using the constructed SLR(1) table and show the parser actions step-by-step.

Consider the following grammar:
$E \rightarrow E + T | T$
$T \rightarrow T * F | F$
$F \rightarrow (E) | id$

Is the grammar ambiguous? Justify your answer with proper reasoning.

Check whether the following grammar is CLR or not :
$S \rightarrow Aa | bBa | Ba | bAc$
$A \rightarrow c$
$B \rightarrow d$

Consider the following grammar:
$S \rightarrow CC$
$C \rightarrow cC/d$
Construct CLR(1) and LALR(1) parsing table.

When a grammar is called ambiguous? Is there any technique to remove ambiguity? Justify whether the following grammar is ambiguous or not?
$S \rightarrow aS/Sa/a$

Consider the context free grammar: $S \rightarrow SS + | SS * | a$; eliminate left factoring and left recursion from the grammar. Does these removals make the grammar suitable for top-down parsing? Justify.

Consider the following grammar:
$E \rightarrow E+T/T$
$T \rightarrow T*F/F$
$F \rightarrow (E)/id$

Obtain FIRST and FOLLOW sets of the above grammar.

Compute FIRST and FOLLOW for the given grammar. Also derive the LL(1) parsing table.
$E \rightarrow TE'$
$E' \rightarrow + TE' / \epsilon$
$T \rightarrow FT'$
$T' \rightarrow * FT' / \epsilon$
$F \rightarrow (E) / id$

Consider the following grammar:
$E \rightarrow E+T/T$
$T \rightarrow T*F/F$
$F \rightarrow (E)/id$

Construct Predictive Parsing Table of the above grammar.

Describe the role of shift-reduce parsing with an example.

Draw the syntax tree for the following arithmetic expression:
$a * -(b + c/d)$

Check whether the following grammar is LL(1) grammar or not :
$S \rightarrow iEtSA | a$
$A \rightarrow eS | \epsilon$
$E \rightarrow b$