What is the maximum number of reduce moves that can be taken by a bottomup parser for a grammar with no epsilon and unitproduction (i.e., of type A > є and A > a) to parse a string with n tokens?
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, $
Q. 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 SR conflict.
3. Can be merged but will result in RR conflict.
4. Cannot be merged since goto on c will lead to two different sets.
The given two LR(1) set of items are :
X > c.X, c/d
X > .cX, c/d
X > .d, c/d
and
X > c.X, $
X > .cX, $
X > .d, $
The symbols/terminals after the comma are LookAhead symbols. These are the sets of LR(1) (LR(1) is also called CLR(1)) items. The LALR(1) parser combines those set of LR(1) items which are identical with respect to their 1st component but different with respect to their 2nd component. In a production rule of a LR(1) set of items, (A > B , c) , A>B is the 1st component , and the LookAhead set of symbols, which is c here, is the second component. Now we can see that in the sets given, 1st component of the corresponding production rule is identical in both sets, and they only differ in 2nd component (i.e. their lookahead symbols) hence we can combine these sets to make a a single set which would be :
X > c.X, c/d/$
X > .cX, c/d/$
X > .d, c/d/$
This is done to reduce the total number of parser states. Now we can check the statements given. Statement 1 : The statement is false, as merging has been done because 2nd components i.e. lookahead were different. Statement 2 : In the merged set, we can't see any ShiftReduce conflict ( because no reduction even possible, reduction would be possible when a production of form P > q. is present) Statement 3 : In the merged set, we can't see any ReduceReduce conflict ( same reason as above, no reduction even possible, so no chances of RR conflict ) Statement 4: This statement is also wrong, because goto is carried on NonTerminals symbols, not on terminal symbols, and c is a terminal symbol. Thus, all statements are wrong, hence option D.
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.
First(X)  It is the set of terminals that begin the strings derivable from X.
Follow(X)  It is the set of terminals that can appear immediately to the right of X in some sentential form.
Now in the above question,
FIRST(S) = {a, b, epsilon} FIRST(A) = FIRST(S) = {a, b, epsilon} FIRST(B) = FIRST(S) = {a, b, epsilon}
FOLLOW (A) = {b , a}
FOLLOW (S) = {$} U FOLLOW (A) = {b , a , $}
FOLLOW (B) = FOLLOW (S) = {b ,a , $}
epsilon corresponds to empty string.
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.
Q.
The appropriate entries for E1, E2, and E3 are
As we need to find entries E1, E2 and E3 which are against Non terminals S and B, so we will deal with only those productions which have S and B on LHS. Here representing the parsing table as M[X , Y], where X represents rows( Non terminals) and Y represents columns(terminals).
Rule 1: if P > Q is a production, for each terminal 't' in FIRST(Q) add P>Q to M [ P , t ]
Rule 2 : if epsilon is in FIRST(Q), add P > Q to M [P , f] for each f in FOLLOW(P).
For the production rule S> aAbB, it will be added to parsing table at the position M[ S , FIRST(aAbB)], Now FIRST(aAbB) = {a}, hence add S> aAbB to M[S , a] which is E1. For the production rule S> bAaB, it will be added to parsing table at the position M[ S , FIRST(bAaB)], Now FIRST(bAaB) = {b}, hence add S> bAaB to M[ S , b] which is E2 For the production rule S> epsilon , it will be added to parsing table at the position M[ S , FOLLOW(S)], Now FOLLOW(S) = {a , b , $}, hence add S > epsilon to M[ S , a] and M[ S , b] which are again E1 and E2 respectively. For the production rule B > S, it will be added to parsing table at the position M[ B , FIRST(S)], Now FIRST(S) also contains epsilon, hence add B > S to M[ S , FOLLOW(B)], and FOLLOW(B) contains {$}, i.e. M[S , $] which is E3. epsilon corresponds to empty string.
The grammar S → aSa  bS  c is
First(aSa) = a
First(bS) = b
First(c) = c
All are mutually disjoint i.e no common terminal between them, the given grammar is LL(1).
As the grammar is LL(1) so it will also be LR(1) as LR parsers are more powerful then LL(1) parsers. and all LL(1) grammar are also LR(1) So option C is correct.
Below are more details. A grammar is LL(1) if it is possible to choose the next production by looking at only the next token in the input string.
Formally, grammar G is LL(1) if and only if
For all productions A → α1  α2  ...  αn,
First(αi) ∩ First(αj) = ∅, 1 ≤ i,j ≤ n, i ≠ j.
For every nonterminal A such that First(A) contains ε,
First(A) ∩ Follow(A) = ∅
Match all items in Group 1 with correct options from those given in Group 2.
Regular expressions are used in syntax analysis. Pushdown automata is related to context free grammar which is related to syntax analysis. Dataflow analysis is done in code optimization. Register allocation is done in code generation.
Which of the following statements are TRUE?
I. There exist parsing algorithms for some programming languages whose complexities are less than O(n^{3}).
II. A programming language which allows recursion can be implemented with static storage allocation.
III. No Lattributed definition can be evaluated in The framework of bottomup parsing.
IV. Code improving transformations can be performed at both source language and intermediate code level.
II is false, in recursion, compiler cannot determine the space needed for recursive calls. III is false.
Which of the following describes a handle (as applicable to LRparsing) appropriately?
Let's first understand the terminology used here. LR Parsing  Here 'L' stands for Left to Right screening of input string, and 'R' stands for Right Most Derivation in Reverse (because it is about bottomup parsing). Sentential Form  Suppose For a given Context Free Grammar G, we have a start symbol S, then to define Language generated by Grammar G, i.e. L(G), we start the derivation starting from S using the production rules of the grammar. After one complete derivation we get a string w which consists of only terminal symbols, i.e. w belongs to L(G). Then we can say that w is a sentence of the Grammar G. Now, while the derivation process, if it gets some form q, where q may contain some Nonterminal then we say that q is a sentential form of the Grammar G. Even the start symbol S is also the sentential form of the Grammar G (because it also contains Nonterminal S).
For Ex :
Grammar is :
S> aAcBe
A>Abb
B>d
Input string : abbcde
Derivation : (TopDown, Right Most Derivation)
S>aAcBe
>aAcde
>aAbcde
>abbcde
Here {abbcde} is the sentence of the Grammar(because it contains only terminal symbols), and {S, aAcBe, aAcde, aAbcde} are the sentential forms of the G (because these forms contain nonterminals during the derivation process) Now, let's look at the question. The question is related to LR parsing which is a bottomup parsing. Let's take the same grammar above, as it is a bottom up parsing we need to start from the string "abbcde" and try to get S using production rules.
: abbcde
>aAbcde (using A> b)
>aAcde (using A> Ab)
>aAcBe (using B > d)
>S (using S> aAcBe)
The above process is called reduction. The RHS of the Production which is being replaced by their LHS is called Handle, So , { b, Ab, d, aAcBe} are handles, and replacing it with its LHS is called HandlePruning. Hence option D suits best.
An LALR(1) parser for a grammar G can have shiftreduce (SR) conflicts if and only if
Both LALR(1) and LR(1) parser uses LR(1) set of items to form their parsing tables. And LALR(1) states can be find by merging LR(1) states of LR(1) parser that have the same set of first components of their items. i.e. if LR(1) parser has 2 states I and J with items A>a.bP,x and A>a.bP,y respectively, where x and y are look ahead symbols, then as these items are same with respect to their first component, they can be merged together and form one single state, let's say K. Here we have to take union of look ahead symbols. After merging, State K will have one single item as A>a.bP,x,y . This way LALR(1) states are formed (i.e. after merging the states of LR(1)). Now, SR conflict in LR(1) items can be there whenever a state has items of the form :
A> a.bB , p
C> d. , b
i.e. it is getting both shift and reduce at symbol b, hence a conflict.
Now, as LALR(1) have items similar to LR(1) in terms of their first component, shiftreduce form will only take place if it is already there in LR(1) states. If there is no SR conflict in LR(1) state it will never be reflected in the LALR(1) state obtained by combining LR(1) states. Note: But this process of merging may introduce RR conflict, and then the Grammar won't be LALR(1).
Which one of the following is a topdown parser?
Recursive Descent parsing is LL(1) parsing which is top down parsing.
Consider the grammar with nonterminals N = {S,C,S1},terminals T={a,b,i,t,e}, with S as the start symbol, and the following set of rules:
S > iCtSS_{1}a
S_{1} > eSϵ
C > b
The grammar is NOT LL(1) because:
A LL(1) grammar doesn't give to multiple entries in a single cell of its parsing table. It has only single entry in a single cell, hence it should be unambiguous.
Option A is wrong. Grammar is not left recursive. For a grammar to be left recursive a production should be of form A>Ab, where A is a single NonTerminal and b is any string of grammar symbols.
Option B is wrong. Because a right recursive grammar has nothing to do with LL(1).
Option D is wrong. Because the given grammar is clearly a Context Free Grammar. A grammar is CFG if it has productions of the form A>(V∪T)* , where A is a single nonterminal and V is a set of Nonterminals and T is a set of Terminals.
Hence Option C should be the correct one. i.e. the grammar is ambiguous.
But let's see how the grammar is ambiguous.
If the grammar is ambiguous then it should give multiple entry in a cell while making its parsing table. And Parse table is made with the aid of two functions : FIRST and FOLLOW.
A parsing table of a grammar will not have multiple entries in a cell( i.e. will be a LL(1) grammar) if and only if the following conditions hold for each production of the form A>αβ 1) FIRST(α) ∩ FIRST(β) = Φ2) if FIRST(α) contains ' ε ' then FIRST(α) ∩ FOLLOW (A) = Φ and viceversa.
Now,
Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar
Q. Which of the following is TRUE?
A regular grammar can also be ambiguous also For example, consider the following grammar,
S → aA/a
A → aA/ε
In above grammar, string 'a' has two leftmost derivations.
(1) S → aA
(2) S → a
S>a (using A>ε)
And LL(1) parses only unambiguous grammar, so statement P is False. Statement Q is true is for every regular set, we can have a regular grammar which is unambiguous so it can be parse by LR parser.
So option C is correct choice
Consider the following grammar.
S > S * E
S > E
E > F + E
E > F
F > id
Consider the following LR(0) items corresponding to the grammar above.
(i) S > S * .E
(ii) E > F. + E
(iii) E > F + .E
Q. Given the items above, which two of them will appear in the same set in the canonical setsofitems for the grammar?
Let's make the LR(0) set of items. First we need to augment the grammar with the production rule S' > .S , then we need to find closure of items in a set to complete a set. Below are the LR(0) sets of items.
A canonical set of items is given below
S > L. > R
Q > R.
On input symbol < the set has
The question is asked with respect to the symbol ' < ' which is not present in the given canonical set of items. Hence it is neither a shiftreduce conflict nor a reducereduce conflict on symbol '<'. Hence D is the correct option. But if the question would have asked with respect to the symbol ' > ' then it would have been a shiftreduce conflict.
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
Q. Which one of the following is TRUE?
From the grammar we can find out associative by looking at grammar.
Let us consider the 2nd production T > T * U
T is generating T*U recursively (left recursive) so * is left associative.
Similarly
P > Q + P
Right recursion so + is right associative. So option B is correct.
NOTE: Above is the shortcut trick that can be observed after drawing few parse trees. One can also find out correct answer by drawing the parse tree.
Consider the following grammar:
S → FR
R → S  ε
F → id
In the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively.
Here representing the parsing table as M[X , Y], where X represents rows(Non terminals) and Y represents columns(terminals). Here are the rules to fill the parsing table. For each distinct production rule A>α, of the grammar, we need to apply the given rules:
Rule 1: if A > α is a production, for each terminal 'a' in FIRST(α), add A>α to M[ A , a]
Rule 2 : if ' ε ' is in FIRST(α), add A > α to M [A , b] for each 'b' in FOLLOW(A). As Entries have been asked corresponding to NonTerminal S and R, hence we only need to consider their productions to get the answer. For S → FR, according to rule 1, this production rule should be placed at the entry M[ S, FIRST(FR)], and from the given grammar, FIRST(FR) ={id}, hence S>FR is placed in the parsing table at entry M[S , id]. Similarly, For R → S, this production rule should be placed at entry M[ R, FIRST(S)], and as FIRST(S) = FIRST(F) = {id} hence, R>S is placed at entry M[R,id] and For R>ε, as FIRST(ε) = {ε}, hence rule 2 should be applied, therefore, this production rule should be placed in the parsing table at entry M[R,FOLLOW(R)], and FOLLOW(R) = FOLLOW(S) = {$}, hence R>ε is placed at entry M[R, $]. Therefore Answer is option A. Visit the Following links to Learn how to find First and Follow sets.
Consider the following translation scheme. S → ER R → *E{print("*");}R  ε E → F + E {print("+");}  F F → (S)  id {print(id.value);} Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints
Background Required to solve the question  Syntax Directed Translation and Parse Tree Construction.
xplanation : We are given LAttributed Syntax Directed Translation as semantic actions like printf statements are inserted anywhere on the RHS of production (R → *E{print(“*”);}R). After constructing the parse tree as shown below from the given grammar, we will follow depth first order left to right evaluation in order to generate the final output.
Parse Tree:
Just follow the arrows in the picture (This is actually Depth first left to right evaluation) and the moment we take exit from any child which is printf statement in this question, we print that symbol which can be a integer value or ‘*’ or ‘+’.
Evaluation :
The grammar A → AA  (A)  ε is not suitable for predictiveparsing because the grammar is
nswer (B) is correct because grammar is left recursive, hence the parser may fall into a loop. Answer A is not correct because ambiguity can occur from both left or right recursion.
Consider the grammar
E → E + n  E × n  n
For a sentence n + n × n, the handles in the rightsentential form of the reduction are
E → E + n {Applying E → E + n}
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
Consider the grammar
S → (S)  a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n_{1}, n_{2} and n_{3} respectively. The following relationship holds good
LALR(1) is formed by merging states of LR(1) (also called CLR(1)), hence no of states in LALR(1) is less than no of states in LR(1), therefore n_{3} < n_{2}. And SLR(1) and LALR(1) have same no of states, i.e (n1 = n3).
Hence n1 = n3 < n2
Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 







