# GATE Questions & Answers of Parsing

## What is the Weightage of Parsing in GATE Exam?

Total 21 Questions have been asked from Parsing topic of Compiler Design subject in previous GATE papers. Average marks 1.67.

Consider the following parse tree for the expression $\style{font-family:'Times New Roman'}{a\#b\$c\$d\#e\#f}$, involving two binary operators $and #. Which one of the following is correct for the given parse tree? ##### Show Answer Consider the following grammar: stmt$\style{font-family:'Times New Roman'}\rightarrow$if expr then expr else expr; stmt | 0 expr$\style{font-family:'Times New Roman'}\rightarrow$term relop term | term term$\style{font-family:'Times New Roman'}\rightarrow$id |number id$\style{font-family:'Times New Roman'}\rightarrow$a | b | c number$\style{font-family:'Times New Roman'}\rightarrow$[0-9] where relop is a rational operator (e.g.,<,>,...), O refers to the empty statement, and if, then, else are terminals. Consider a preogram P following the above grammar containing ten if terminals. The number of control flow paths in P is ________. For example, the program if e1 then e2 else e3 has 2 control flow paths,$\style{font-family:'Courier New'}{\begin{array}{l}{\mathrm e}_1\;\rightarrow\;{\mathrm e}_2\;\mathrm{and}\;{\mathrm e}_1\;\rightarrow\;{\mathrm e}_3\\\;\end{array}}$. ##### Show Answer Which of the following statements about parser is/are CORRECT? I. Canonical LR is more powerful than SLR II. SLR is more powerfull than LALR. III. SLR is more powerful than Canonical LR. ##### Show Answer Which one of the following is TRUE at any valid state in shift – reduce parsing? ##### Show Answer Among simple LR (SLR), canonical LR, and look – ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order? ##### Show Answer Consider the following grammar G SF | H Fp | c Hd | c Where S, F, and H are non – terminal symbols, p, d, and c are terminal symbols. Which of the following statements (s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all strings that are generated using grammar G ##### Show Answer A canonical set of items is given below S → L. > R Q → R. On input symbol < the set has ##### Show Answer Consider the grammar defined by the following production rules, with two operators * and + S → T ∗ P T → U | T ∗ U P → Q + P | Q Q → Id U → Id Which one of the following is TRUE? ##### Show Answer What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type $\mathrm{A}\to \mathrm{ϵ}$ and $\mathrm{A}\to \mathrm{a}$) to parse a string with n tokens? ##### Show Answer Consider the following two sets of LR(1) items of an LR(1) grammar.  X → c.X, c/d X → .cX, c/d X → .d, c/d X → c.X,$ X →.cX, $X →.d,$

Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE?
1. Cannot be merged since look aheads are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $\$$indicates end of input, and, | separates alternate right hand sides of productions. S $\to$ a A b B | b A a B | $\epsilon$ A $\to$ S B $\to$ S  a b S E1 E2 S→ε A A→S A→S error B B→S B→S E3 The FIRST and FOLLOW sets for the non-terminals A and B are ##### Show Answer For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, \$$ indicates end of input, and, | separates alternate right hand sides of productions. S $\to$ a A b B | b A a B | $\epsilon$ A $\to$ S B $\to$ S  a b$ S E1 E2 S→ε A A→S A→S error B B→S B→S E3

The appropriate entries for E1, E2, and E3 are

Consider two binary operators ‘↑’ and '↓ ’ with the precedence of operator ↓ being lower than that of the operator ↑ ; . Operator ↑ is right associative while operator↓ is left associative. Which one of the following represents the parse tree for expression (7↓3↑4↑3↓2)?

The grammar SaSa|bS|c is

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

Which one of the following is a top-down parser?

Consider the grammar with non-terminals N = {S,C,S1}, terminals T = {a, b, i, t, e}, with S as the start symbol, and the following set of rules:

S $\to$ iCtSS1 | a
S1 $\to$ eS | ε
C $\to$ b

The grammar is NOT LL(1) because:

Consider the following two statements:

P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar

Which of the following is TRUE?

Consider the CFG with {S, A, B} as the non-term , {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

 S$\to$aB S$\to$bA B$\to$b A$\to$a B$\to$bS A$\to$aS B$\to$aBB A$\to$bAA

Which of the following strings is generated by the grammar?

Consider the CFG with {S, A, B} as the non-term , {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules:

 S$\to$aB S$\to$bA B$\to$b A$\to$a B$\to$bS A$\to$aS B$\to$aBB A$\to$bAA

For the correct answer strings to Q.78, how many derivation trees are there?