Solution

Dynamic memory allocation is done during run time and rest all are performed in compilation.

Solution

None of the regular expressions generate the string “aba” hence no one is correct. The correct regular expression which generates language containing all strings with even number of a’s and exactly one “b” is:

(aa)*b(aa)* + (aa)*aba(aa)*

Solution

Please note any valid C operator is considered as one token. For example: ++, +=, /= all are one token only.

int₁ x_2,3 a₄ = ₅2_6;7

x₈ = ₉a₁₀++_11;12

x₁₃ += ₁₄a_15;16

x₁₇ /= ₁₈3_19;20

Hence total 20 tokens.

Solution

Since SDT count the number of zeros, hence the correct SDT is:

N→L {N.c=L.c}

L→L₁ B {L.c=L₁.c+B.c}

L→B {L.c=B.c}

B→0 { B.c =1}

B→1 { B.c =0}

Solution

All of the mentioned operations are performed during semantic analysis.

Solution

Consider expression “a*b*c”, if precedence is “<” then b*c will be evaluated first, hence it is right associative.

Solution

Solution

Follow(S) = {$}U {First(A) because of S→SA}U {Follow(A) because of A→AS}

So Follow(S) = {$}U {b}U {Follow(A) = First(S)}

Follow(S) = {$}U {b}U {a} = {a,b,$}

Similarly, Follow(A) = {First(S) because of A-&gt; →AS}U {Follow(S) because of S→SA}

Follow(A) = {a} U {a,b,$} = {a,b,$}

Solution

A context free grammar is ambiguous if atleast one string generated by the grammar must have more than one parse tree.

So if a grammar generates a string which has two or more parse trees then grammar is ambiguous.

Solution

First(S) = FIRST(AS) U FIRST(b)

= FIRST(AS) U {b}

Now, FIRST(AS) = FIRST(SAS) U FIRST(aS) // Since A → SA and A → a

Since S is calling A (by S → AS ) and A is again calling S (by A → SA)

Hence it will be terminated only when we replace S by b (by using S → b)

So FIRST(AS) ⇒ FIRST(SAS) ∪ FIRST(aS)

⇒ FIRST(bAS) ∪ FIRST(aS)

⇒ {b} U {a}

So First(S) = {a,b}

Similarly FIRST(A) = FIRST(SA) ∪ FIRST(a)

= FIRST(S) ∪ a

= {a,b} ∪ {a} = {a,b}

So FIRST(A) = {a,b}

Follow(S) = {$}U {First(A)} // because of A → SA

Follow(S) = {a,b,$}

Follow(A) = First(S) = {a,b}

Solution

S→AB will go in FIRST(AB) & FIRST(AB)= {a,b,ϵ}

When A & B both are ϵ then S→AB will go in follow(S)={$}

Hence S→AB will go in FIRST(AB)= {a,b,$}

A->ϵ entry will be in follow(A)

Follow(A)= First(B) ∪ Follow(S) {when B→ϵ} ∪ {b} (because of B->Ab)

Follow(A)= {a,b,$}

B->ϵ entry will be in follow(B)

Follow(B)= {a} {because of A->Ba} ∪ Follow(S) { because of S->AB }

Follow(B)= {a,$}

LL(1) Parsing Table:

Solution

The grammar is not LL(1) because P→aQ and P→ϵ will go under the same cell {a}.

Follow(P) = {a,b}

The grammar is not linear (Because of production S → PQ)

Solution

G1 is wrong as it does not generate the string “ababab” which is generated by the grammar. G2 is wrong as it does not generate any string, because S will never terminate. G3 is equivalent to G but G3 is also ambiguous. G3 generate two parse tree for string “ϵ”.

Tree 1: S→ϵ

Tree 2: S→AS →ϵS →ϵ ϵ→ϵ

G4 is an unambiguous version of G.

Solution

The productions not allowed in operator grammar are:

1. Null productions for ex: A→ϵ

2. If two non-terminals are together, for ex: S→AB

Hence both G1 and G2 are not operator grammars.

Solution

S1 is true, as every LL(1) grammar need not be LALR(1), so there are some LL(1) grammars which are not LALR(1).

S2 is false, since every unambiguous grammar need not be LALR(1). For example grammar A→aAa | bAb | ϵ is unambiguous but not LALR(1) (even not CLR(1)).

Solution

S1 is true, Symbol table is the data structure in the compiler, which is used for managing information about variables and their attributes.

S2 is false, since a regular grammar can be ambiguous also, hence every regular grammar need not be parsed by CLR(1) parser. Consider a regular grammar which is ambiguous

S → aS | a | ϵ

It generate two parse tree for string “a”

Tree 1: S → a

Tree 2: S → aS → a ϵ → a

Solution

R1 generates all strings which begin with “a” and R2 generates all strings which end with “b”. So the intersection of R1 and R2 is all strings which begin with “a” and end with “b”. Also concatenation of R1 and R2 is also the same, i.e, L(R1).L(R2) all strings begin with “a” and end with “b”.

Hence L(R1) ∩ L(R2)= L(R1). L(R2)= a(a+b)*b

L(R1) U L(R2) ≠(a+b)(a+b)*, as (a+b)(a+b)* generate string “ba” which is not present in L(R1) U L(R2).

Complement(L(R1)) ≠ L(R2) is true, as complement of L(R1) will have string “ba” but it is not present in L(R2), hence both cannot be equal.

Solution

r₁ : (a*b*)* = (a+b)*

r₂ : (a*+b*)* = (a+b)* , both are a well-known equality.

So r₁ = r₂ = (a+b)* and their intersection is also equal to (a+b)* .

Now, (a*b+ b*a)* = (a+b)* , as we can assume a* and b* as epsilon, which will give (a+b)* and since (a+b)* is superset of all possible language over {a,b} hence

(a*b + b*a)* == (a+b)* .

Hence (a*b+ b*a)* is the correct answer.

Solution

The grammar is ambiguous, so it cannot be LL(1), LR(0), and CLR(1). The grammar generates two parse tree for string “abab”.

Solution

Solution

Grammar G1: A → bA | ϵ

A → bA (r₁)

A → ϵ (r₂)

LR(0) Parsing Table:

Grammar G2: A → Ab | ϵ

LR(0) Parsing Table:

A → Ab (r₁)

A → ϵ (r₂)

No SR conflict in LR(0) parsing table. Hence grammar G2 is LR(0) grammar. Please note state I₀ is not having SR conflict. Here, entry of non-terminal (A) is done in GOTO part of table (and not in ACTION part as done in case of grammar G1).

Solution

The grammar G1 is ambiguous as it has two parse trees for string “xxyyy”.

Hence it is not LR(k) for any value of k.

The grammar G2 has reduce-reduce conflict in LR(0) parser and LR(1) parser, hence not LR(0) as well as LR(1).

Hence this grammar is not LR(0).

Hence this grammar is not LR(1).

Solution

Grammar G is ambiguous as for string “ϵ” it generates two parse tree. Hence it cannot be LL(1) or CLR(1).

Solution

G2 is LL(1) hence it cannot be ambiguous

LL(1) parsing table for G2

Follow(Q) = Follow(P) = {x,$}

G1 is not LL(1) grammar as it has left factoring.

Solution

The grammar is LALR(1) but not SLR(1).

Canonical collections of LR(0) items.

LR(0) canonical collection of items for Grammar

A → t (r5)

Follow(A) = {x,z}

In state I₃, A → t∙(r5)

entry will be in Follow(A)

SR conflict in state I 3 hence not SLR(1).

Canonical collections of LR(1) items.

No, S-R or RR conflict, hence grammar is CLR(1).

Also, no two states only differ by look-ahead symbols, hence this grammar is LALR(1).

Hence this grammar is CLR(1) as well as LALR(1) but not SLR(1).

Solution

G1 is not an operator grammar since two non-terminals came together. G2 is an operator grammar. G1 is unambiguous grammar (It is an LR(0) grammar and hence it is unambiguous).

AAAr (r1)

At (r2)

No SR conflict, hence this grammar is LR(0).

Hence this is an unambiguous grammar.

G2 is an ambiguous grammar, as it generates more than one parse tree for string “ttr”.

Solution

A context free unambiguous grammar need not always generate DCFL. For example: Grammar S c 0S0 | 1S1| ϵ is unambiguous but the language is even length palindromes which is CFL but not DCFL.

A context free grammar corresponding to DCFL need not be always unambiguous. For example : Below grammar for a DCFL language L = {a^nb^n | n>=0} is ambiguous.

S→ aSb | ab | ϵ

It generate two parse tree for string “ab”

Tree 1: S → ab

Tree 2: S→aSb → a ϵ b → ab

Please note for a DCFL it is necessary that there exist one grammar which is unambiguous, but it is not necessary that every existing grammar is unambiguous.

The corresponding unambiguous grammar for L = {a^nb^n | n>=0}is:

S→ aSb | ϵ

Solution

In rule 2 for production S → LR the attribute “i” of L is calculated from the “s” attribute of right sibling R of L, in L.i = S.i + R.s which is violating the L attribute definition. Since in L attributed definition, calculation of attribute value from RHS sibling is not allowed.

Solution

Solution

t1=y+x

t2= – (y+x)

t3=z*(y+x)

t4= –(y+x)+z* (y+x)

Solution

The first two lines compute the value of a[i] and assigns in temporary t₂ . Lines 3 and 4 compute the value of a[j] and assigns in temporary t₄ .

Line 5 and 6 make t₂ and t₄ actual parameters for the call of function f on line 2 and 3. Line 7 calls the function “f” where “2” means number of parameters (here parameter is a[i] and a[j]) and line 8 assigns the value returned by f(a[i],a[j]) in “n”.

Hence, it is n=f(a[i],a[j])

Solution

Solution

If # is * (multiplication operator) then after evaluating (a*b) we need to save this value into memory and then evaluate c*d before performing the + operation. Hence in case of #=* we need to save a*b value into memory and then perform c*d and then fetch back a*b from memory and add into (c*d) value in register. But if #= + or – then we can perform

Step 1: t₁ = a*b

Step 2: t₂ = t₁+c

Step 3: t₃ = t₂ (+ or −) d

Hence in case of (+ or −) no need to save any intermediate value into memory.