Solution

Symbol table is also accessed by other phases such as semantic analysis phase and code optimization phases. Errors “a variable is used before its declaration” are detected in semantic analysis phase.

Solution

Lexical analyser requires regular grammar and syntax analyser requires context free grammar. Since every regular grammar is also context free, so we can use context free grammar for both lexical analyser and syntax analyser.

Type checking is done in semantic analysis phase (i.e., after parsing phase).

Solution

Character stream is input to lexical analyzer which produces tokens as output. So R → (iv).

Token stream is forwarded as input to Syntax analyzer which produces syntax tree as output. So, P → (ii).

Syntax tree is the input for the semantic analyzer, So Q → (i).

Intermediate representation is input for Code generator. So S → (iii).

Solution

Regular expressions are used in lexical analysis and PDA is used in context free grammar hence PDA is related to syntax analysis. Data flow analysis is done in code optimization and register allocation is related to code generation.

Solution

The lexical analyser scans the source program and produces as output a stream of tokens.

Solution

In production A→A*C since A is left recursive so * is left associative and in production B→D%B since B is right recursive so % is right associative.

Solution

Solution

Given grammar A→Ax | yA | y

After eliminating left recursion the grammar is:

A→ yAB | yB

B→ ϵ | xB

After eliminating left recursion still grammar is ambiguous (two parse tree for string “yyx”)

The grammar is A→Ax | yA | y

After eliminating left factoring the grammar is:

A→ Ax | yC

C→ A | ϵ

After eliminating left factoring still grammar is ambiguous (two parse tree for string “yyx”)

Elimination left recursion and left factoring both

Please note we can eliminate in any order, i.e, first eliminate left recursion and then left factoring OR first eliminate left factoring then left recursion.

Eliminating left recursion first and then eliminating left factoring

After eliminating left recursion the grammar is:

A→ yAB | yB

B→ ϵ | xB

Now eliminate left factoring:

A→ yC

C→AB| B

B→ ϵ | xB

Still the grammar is ambiguous as we have two parse tree for string “yyx”

Now eliminating left factoring first and then left recursion

After eliminating left factoring the grammar is:

A→ Ax | yC

C→ A | ϵ

Now eliminate left recursion:

A→ yCB

B→ ϵ| xB

C→ A | ϵ

Still the grammar is ambiguous as we have two parse tree for string “yyx”

Hence after removing left recursion and left factoring, still the grammar is ambiguous.

Eliminating ambiguity from the grammar:

The language generated by the grammar is : yy*x*

The given grammar is ambiguous because we can use first production to generate “x” also, while the language is every string starts with “y” so to fix ambiguity we should start with the production generating “y”.

S→ yA

A→ yA | xB | ϵ

B→ xB | ϵ

Now the above grammar is LL(1). Hence eliminating ambiguity is correct answer.

The LL(1) parsing table is

Solution

(p*q*p*)* =(p+q)* , so it will consider whole string as one token, hence wrong. The regular expression (pq)*p*(qp)*q* will not generate string “pqppqppqpqpqqpppqppq”. Hence it cannot be true.

The correct flex rule is : (pq)*pp* + q*p +p +q

Token 1: $ pqpp $ is generated by (pq)*pp*

Token 2: $ qp $ is generated by q*p

Token 3: $ pqpqp $ is generated by (pq)*pp*

Token 4: $ qqp $ is generated by q*p

Token 5: $ pp $ is generated by (pq)*pp*

Token 6: $ qp $ is generated by q*p

Token 7: $ p$ is generated by p

Token 8: $ q $ is generated by q

Solution

Since + has highest precedence

41-4-(2+4)*47 = 41-4-6*47

Next – has highest precedence and right associativity

(41-(4-6))*47= (41-(-2))*47

43*47= 2021

Solution

Line 3 will not cause any compilation error. The reason is compiler will assume it as a user defined function “fro”. Please note inside “fro” we have comma and not the semicolon. If it is semicolon then it will be syntax error.

Solution

Void main() /* Void lexical error as “V” is in capital */

{

int final-value; /* Lexical error as hyphen is not allowed in variable */

int Val=2;

int total=5;

int 1var=2; /* Lexical error as a variable cannot begin with digit */

5=Val; /* Semantic error we cannot reassign value to a constant */

total=val*1; /* Semantic error val is undeclared variable, val and Val are different */

if(total=5)

{

total=total+1 /* syntax error missing semicolon*/

}

}

Solution

S → Aw | x ........(i)

A → Ay | Sz | y ........(ii)

A-> Ay (it has direct left recursion)

S-> Aw and A-> Sz (it has indirect left recursion)

Lets replace S-> Aw and S-> x from (i) into (ii) in place of S

The productions will be

S-> Aw | x

A-> Ay | Awz | xz| y // Now it has only direct left recursion

Remove direct left recursion

S-> Aw | x

A-> xzA' | yA'

A' -> ε | yA' | wzA'

Hence C is correct option.

Solution

The grammar is ambiguous so it cannot be parsed by any LL(k) and LR(k) parser for any value of k.

The grammar is not operator grammar as it has null production, so the statement “grammar is ambiguous but it can be parse by operator parser” is not correct.

Solution