Test: Parsing- 2 - Computer Science Engineering (CSE) MCQ

Background yacc conflict resolution is done using following rules: shift is preferred over reduce while shift/reduce conflict. first reduce is preferred over others while reduce/reduce conflict.   You can answer to this question straightforward by constructing LALR(1) parse table, though its a time taking process. To answer it faster, one can see intuitively that this grammar will have a shift-reduce conflict for sure. In that case, given this is a single choice question, (C) option will be the right answer. Fool-proof explanation would be to generate LALR(1) parse table, which is a lengthy process. Once we have the parse table with us, we can clearly see that i. reduce/reduce conflict will not arise in the above given grammar ii. shift/reduce conflict will be resolved by giving preference to shift, hence making the expression calculator right associative. According to the above conclusions, only correct option seems to be (C).

Answer is B as the productions belong to the same non-terminal and since YACC resolves by shift over reduce, the associativity will be right associative.

Removing left recursion and factoring the grammar do not suffice to convert an arbitrary CFG to LL(1) grammar.

A Syntax Directed Definition (SDD) is called S Attributed if it has only synthesized attributes. L-Attributed Definitions contain both synthesized and inherited attributes but do not need to build a dependency graph to evaluate them.

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 Non-Terminal S', hence we only need to consider its productions to get the answer. For S' → eS, according to rule 1, this production rule should be placed at the entry M[ S', FIRST(eS)], and from the given grammar, FIRST(eS) ={e}, hence S'->eS is placed in the parsing table at entry M[S' , e]. Similarly, For S'->ε, as FIRST(ε) = {ε}, hence rule 2 should be applied, therefore, this production rule should be placed in the parsing table at entry M[S',FOLLOW(S')], and FOLLOW(S') = FOLLOW(S) = {e, $}, hence R->ε is placed at entry M[S', e] and M[S' , $]. Therefore Answer is option D. Visit the Following links to Learn how to find First and Follow sets.

Since there is no conflict, the grammar is LL(1). We can construct a predictive parse table with no conflicts. This grammar also LR(0), SLR(1), CLR(1) and LALR(1).

Let us make the parse tree for 9+5+2 in top down manner, left first derivation.

Steps:
1) Exapnd S->TR
2) apply T->Num...
3) apply R -> +T...
4) appy T->Num...
5) apply R-> +T..
6) apply T-> Num..
7) apply R-> epsilon

After printing through the print statement in the parse tree formed you will get the answer as 95+2+

It must be B. The production E --> E + E is used only one time and hence only one temporary variable is generated.

1. A grammar is ambiguous if there exists a string s such that the grammar has more than one leftmost derivations for s. We could also come up with more than one rightmost derivations for a string to prove the above proposition, but not both of right and leftmost. An unambiguous grammar can have different rightmost and leftmost derivations.
2. LL parser is top-down by nature. Leftmost derivation is, intuitively, expanding or top-down in fashion, hence such convention. Rightmost derivation, on the other hand, seems like a compressing or bottom-up thing.
3. LALR is more powerful than SLR, even when both have the same LR(0) states, due to the fact that SLR checks for lookaheads by looking at FIRST and FOLLOW from the grammar after constructing its parse table and on the other hand, LALR computes lookaheads from the LR(0) states while constructing the parse table, which is a better method.
4. An ambiguous grammar can never be LR(k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is

Let say i/p is 3*4-5 when we draw parse tree according to grammar

As we can see first '- ' will be evaluated then ' * ' is evaluated so ' - ' has higher precedence then *. So correct choice is B See question 1 of 

The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes. By definition, a viable prefix is a prefix of a right sentential form that does not continue past the right end of the rightmost handle of that sentential form. 

(A) is false, In CFG (Control Flow Graph), code of N2 may be present before N1 when there is a loop or goto.
(B) is false, CFG (Control Flow Graph) contains cycle when input program has loop.
(C) is true, successors in AST and CFG depedend on input program
(D) is false, a single statement may belong to a block of statements.

Register allocation is a variation of Graph Coloring problem.
Lexical Analysis uses DFA.
Parsing makes production tree Expression evaluation is done using tree traversal

SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm. Canonical LR parser or LR(1) parser is an LR(k) parser for k=1, i.e. with a single lookahead terminal. It can handle all deterministic context-free languages.LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser,

The given grammar is ambiguous as there are two possible leftmost derivations for string "c".

First Leftmost Derivation
S → F
F → c

Second Leftmost Derivation
S → H
H → c

An Ambiguous grammar can neither be LL(1) nor LR(1)

Bottom up parser builds the parse tree from bottom to up, i.e from the given string to the starting symbol. The given string is aab and starting symbol is S. so the process is to start from aab and reach S. =>aab ( given string) =>aSb (after reduction by S->a, and hence print 2) =>aA (after reduction by A->Sb, and hence print 3) =>S (after reduction by S->aA, and hence print 1) As we reach the starting symbol from the string, the string belongs to the language of the grammar. Another way to do the same thing is :- bottom up parser does the parsing by RMD in reverse. RMD is as follows: =>S => aA (hence, print 1) => aSb (hence, print 3) => aab (hence, print 2) If we take in Reverse it will print : 231