What is not true about cookies?

Page 2

Improve Article

Save Article

Like Article

Improve Article

Save Article

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is True?
(A) In both AST and CFG, let node N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding to N1
(B) For any input program, neither AST nor CFG will contain a cycle
(C) The maximum number of successors of a node in an AST and a CFG depends on the input program
(D) Each node in AST and CFG corresponds to at most one statement in the input program

Answer: (C)

Explanation:

Quiz of this Question

Page 3

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Consider the intermediate code given below:

1. i = 1 2. j = 1 3. t1 = 5 * i 4. t2 = t1 + j 5. t3 = 4 * t2 6. t4 = t3 7. a[t4] = –1 8. j = j + 1 9. if j <=>

The number of nodes and edges in the control-flow-graph constructed for the above code, respectively, are

(A) 5 and 7
(B) 6 and 7
(C) 5 and 5
(D) 7 and 8

Answer: (B)

Explanation: Below is control flow graph of above code.

Quiz of this Question

Page 4

Improve Article

Save Article

Like Article

Improve Article

Save Article

Consider the following code segment.

The minimum number of total variables required to convert the above code segment to static single assignment form is

 Note : This question was asked as Numerical Answer Type.

(A) 6

Answer: (D)

Explanation: Static Single Assignment is used for intermediate code in compiler design. In Static Single Assignment form(SSA) each assignment to a variable should be specified with distinct names. We use subscripts to distinguish each definition of variables.

In the given code segment, there are two assignments of the variable x

and three assignments of the variable y.

So we use two variables x1, x2 for specifying distinct assignments of x and y1, y2 and y3 each assignment of y. So, total number of variables is 10 (x1, x2, y1, y2, y3, t, u, v, w, z).
Static Single Assignment form(SSA) of the given code segment is:

Please refer below link for details
https://www.cs.cmu.edu/~fp/courses/15411-f08/lectures/09-ssa.pdf

Quiz of this Question

Page 5

Improve Article

Save Article

Consider the following two sets of LR(1) items of an LR(1) grammar.

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.

(A) 1 only
(B) 2 only
(C) 1 and 4 only
(D) 1, 2, 3, and 4

Answer: (D)

Explanation: The given two LR(1) set of items are :

The symbols/terminals after the comma are Look-Ahead 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 Look-Ahead 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 look-ahead symbols) hence we can combine these sets to make a a single set which would be :

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. look-ahead were different.

Statement 2 : In the merged set, we can’t see any Shift-Reduce 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 Reduce-Reduce conflict ( same reason as above, no reduction even possible, so no chances of R-R conflict )

Statement 4: This statement is also wrong, because goto is carried on Non-Terminals symbols, not on terminal symbols, and c is a terminal symbol.

Thus, all statements are wrong, hence option D.

Quiz of this Question

Page 6

Page 7

Improve Article

Save Article

Like Article

Improve Article

Save Article

The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is
(A) ambiguous
(B) left-recursive
(C) right-recursive
(D) an operator-grammar

Answer: (A)

Explanation: Since given grammar can have infinite parse trees for string ‘ε’, so grammar is ambiguous, and also A → AA has left recusion.

For predictive-parsing, grammar should be:

• Free from ambiguity
• Free from left recursion
• Free from left factoring

Given grammar contains both ambiguity and left factoring, so it can not have predictive parser.We always expect first grammar free from ambiguity for parsing. Option (A) is more strong option than option (B) here.

Quiz of this Question

Page 8

Improve Article

Save Article

Like Article

Improve Article

Save Article

Given the following expression grammar:

which of the following is true?
(A) * has higher precedence than +
(B) – has higher precedence than *
(C) + and — have same precedence
(D) + has higher precedence than *

Answer: (B)

Explanation: 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 https://www.geeksforgeeks.org/compilers-set-2/

Quiz of this Question

Page 9

Page 10

Page 11

Page 12

Page 13

Improve Article

Save Article

Like Article

Improve Article

Save Article

Which of the following statements is false?
(A) An unambiguous grammar has same leftmost and rightmost derivation
(B) An LL(1) parser is a top-down parser
(C) LALR is more powerful than SLR
(D) An ambiguous grammar can never be LR(k) for any k

Answer: (A)

Explanation: 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.

Reference: http://stackoverflow.com/questions/2676144/what-is-the-difference-between-lr-slr-and-lalr-parsers/16575211#16575211
See question 3 of https://www.geeksforgeeks.org/compilers-set-1/

This solution is contributed by Vineet Purswani.

Quiz of this Question

Page 14

Improve Article

Save Article

Like Article

Improve Article

Save Article

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?

(A) SLR, LALR
(B) Canonical LR, LALR
(C) SLR, canonical LR
(D) LALR, canonical LR

Answer: (C)

Explanation: 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,

Quiz of this Question

Page 15

Improve Article

Save Article

Consider the grammar shown below

In the predictive parse table. M, of this grammar, the entries M[S’, e] and M[S’, $] respectively are
(A) {S’ → e S} and {S’ → e}
(B) {S’ → e S} and {}
(C) {S’ → ε} and {S’ → ε}
(D) {S’ → e S, S’→ ε} and {S’ → ε}

Answer: (D)

Explanation: 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.

http://geeksquiz.com/compiler-design-first-in-syntax-analysis/
http://geeksquiz.com/compiler-design-follow-set-in-syntax-analysis/

Quiz of this Question

Page 16

Improve Article

Save Article

Consider the following grammar:

In the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $] respectively.
(A) {S → FR} and {R → ε }
(B) {S → FR} and { }
(C) {S → FR} and {R → *S}
(D) {F → id} and {R → ε}

Answer: (A)

Explanation: 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 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.

http://geeksquiz.com/compiler-design-first-in-syntax-analysis/
http://geeksquiz.com/compiler-design-follow-set-in-syntax-analysis/

Quiz of this Question

Page 17

Improve Article

Save Article

Like Article

Improve Article

Save Article

Consider the following translation scheme.S → ERR → *E{print(“*”);}R | εE → F + E {print(“+”);} | FF → (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

(A) 2 * 3 + 4

Answer: (D)

Explanation: Background Required to solve the question – Syntax Directed Translation and

Parse Tree:

Evaluation :

This explanation has been contributed by Pranjul Ahuja.

Quiz of this Question

Page 18

Improve Article

Save Article

Like Article

Improve Article

Save Article

Consider the grammar

For a sentence n + n × n, the handles in the right-sentential form of the reduction are
(A) n, E + n and E + n × n
(B) n, E + n and E + E × n
(C) n, n + n and n + n × n
(D) n, E + n and E × n

Answer: (D)

Explanation:

Hence, the handles in right sentential form is n, E + n and E × n.

Quiz of this Question

Page 19

Improve Article

Save Article

Like Article

Improve Article

Save Article

Consider the grammar

Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good
(A) n1 < n2 < n3
(B) n1 = n3 < n2
(C) n1 = n2 = n3
(D) n1 ≥ n3 ≥ n2

Answer: (B)

Explanation: 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 n3 < n2. And SLR(1) and LALR(1) have same no of states, i.e ( n1 = n3).

Hence n1 = n3 < n2

Quiz of this Question

Page 20

Improve Article

Save Article

Like Article

Improve Article

Save Article

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
(A) the SLR(1) parser for G has S-R conflicts
(B) the LR(1) parser for G has S-R conflicts
(C) the LR(0) parser for G has S-R conflicts
(D) the LALR(1) parser for G has reduce-reduce conflicts

Answer: (B)

Explanation:

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, S-R conflict in LR(1) items can be there whenever a state has items of the form :

Now, as LALR(1) have items similar to LR(1) in terms of their first component, shift-reduce form will only take place if it is already there in LR(1) states. If there is no S-R 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 R-R conflict, and then the Grammar won’t be LALR(1).

Quiz of this Question

Page 21