GATE CSE
Compiler Design
Parsing
Previous Years Questions

## Marks 1

Which one of the following statements is TRUE?
Consider the augmented grammar with {+, *, (, ), id} as the set of terminals. S' $$\to$$ S S $$\to$$ S + R | R R $$\to$$ R * P | P P $$\to$$ (S) | id ...
Consider the following grammar. S $$\to$$ aSB| d B $$\to$$ b The number of reduction steps taken by a bottom-up parser while accepting the string ...
Consider the grammar given below: S → Aa A → BD B → b | ε D → d | ε Let a, b, d, and be indexed as follows: Compute the FOLLOW set of the non-termi... Which one of the following kinds of derivation is used by LR parsers? Match the following: .tg {border-collapse:collapse;border-spacing:0;} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-s... Among simple $$LR (SLR) ,$$ canonical $$LR,$$ and look-ahead $$LR$$ $$(LALR),$$ which of the following pairs identify the method that is very easy to ... Match the following: .tg {border-collapse:collapse;border-spacing:0;border-color:#999;} .tg td{font-family:Arial, sans-serif;font-size:14px;padding... Which one of the following is TRUE at any valid state in shift-reduce parsing? Consider the grammar defined by the following production rules, with two operators * and + \eqalign{ & S \to T*P \cr & T \to U\,|\,T*U... 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 ... Given the language L= { ab, aa, baa }, which of the following strings are in L* ? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa ... Which of the following describes a handle (as applicable to LR-parsing) appropriately? Which one of the following is a top-down parser? Consider the following grammar.\eqalign{ & S \to S*E \cr & S \to E \cr & E \to F + E \cr & E \to F \cr & F \t... The grammar $$A \to AA\,|\,\left( A \right)\,|\,\varepsilon$$ is not suitable for predictive-parsing because the grammar is Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is... In a bottom-up evaluation of a syntax directed definition, inherited attributes can Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar? The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned add... Which of the following statements is false? Which of the following statements is true? The pass numbers for each of the following activities (i) object code generation (ii) literals added to literal table (iii) listing printed (iv) ad... ## Marks 2 Consider the following statements. S1 : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S2 : For... Consider the productions A $$\to$$ PQ and A $$\to$$ XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized at... Consider the augmented grammar given below : S' → S S → 〈L〉 | id L → L,S | S Let I0 = CLOSURE ({[S' → ●S]}). The number of items in the set G... Consider the following parse tree for the expression $$a \ne b\ c\ d \ne e \ne f,$$ involving two binary operators $$\$$ and $$\ne$$. Which... A student wrote two context-free grammars G1 and G2 for generating a single $$C$$-like array declaration. The dimension of the array is at least one. ... The attributes of three arithmetic operators in some programming language are given below. .tg {border-collapse:collapse;border-spacing:0;} .tg td{... Consider the following grammar $$G$$ \eqalign{ & \,\,\,\,\,\,\,S \to \,\,\,\,\,\,\,F|H \cr & \,\,\,\,\,\,F \to \,\,\,\,\,\,\,p|c \cr... A canonical set of items is given below\eqalign{ & S \to L. > R \cr & Q \to R. \cr} $$On input symbol < the set has... Consider the following two sets of LR(1) items of an LR(1) grammar.$$\eqalign{ & X \to c.X,\,c/d\,\,\,\,\,\,\,\,X \to c.X,\ \cr & X \...
The grammar $$S \to aSa\,|\,\,bS\,|\,\,c$$ is
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
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 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:...
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of prod...
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of prod...
Which one of the following grammars generates the following language? $$L = \left( {{a^i}{b^j}|i \ne j} \right)$$
In the correct grammar of the previous question, what is the length of the derivation (number of steps starring from S) to generate the string $${a^l}... Consider the following grammar:$$\eqalign{ & S \to FR \cr & R \to *S\,|\,\varepsilon \cr & F \to id \cr} $$In the predictive ... Consider the grammar$$S \to \left( S \right)\,|\,a$$Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 r... Consider the grammar$$E \to E + n\,|\,E \times n\,|\,n$$For a sentence n + n × n, the handles in the right-sentential form of the reduction are ... Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production.$$\eqalign{ &a...
Consider the following expression grammar. The seman­tic rules for expression calculation are stated next to each grammar production. \eqalign{ &a... Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s, t are terminals.\eqalign{...
Consider the grammar with the following translation rules and E as the start symbol. \eqalign{ & E \to {E_1}\# T\,\,\left\{ {E.value = {E_1}.v... Consider the grammar shown below\eqalign{ & S \to iEtSS'\,|\,\,a \cr & S' \to eS\,|\,\,\varepsilon \cr & E \to b \cr} $$In ... Consider the translation scheme shown below$$\eqalign{ & S \to TR \cr & R \to + T\left\{ {pr{\mathop{\rm int}} (' + ');} \right\}\,R\,...
Consider the grammar shown below. \eqalign{ & S \to CC \cr & C \to cC\,|\,d \cr} This grammar is
A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar. \eqalign{ ... Consider the SLR(1) and LALR (1) parsing tables for a context-free grammar. Which of the following statements is/are true? ## Marks 5 Consider the following grammar:\eqalign{ & S \to S \cr & S \to SS\,|\,a\,|\,\varepsilon \cr}  (a) Construct the collection of sets...
EXAM MAP
Joint Entrance Examination