Theory of Computation and Compilers MCQ - Syntax Analysis

11 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
Which one of the following is TRUE?

2nd production is
T → T * U (left recursive) so * is left associative.
Similarly
P → Q + P (Right recursion) so + is right associative.

12 Match the following:

List-I		List-II
A.	Lexical analysis	1.	Graph coloring
B.	Parsing	2.	DFA minimization
C.	Register allocation	3.	Post-order traversal
D.	Expression evaluation	4.	Production tree

Codes:

	A	B	C	D
(a)	2	3	1	4
(b)	2	1	4	3
(c)	2	4	1	3
(d)	2	3	4	1

The match are as follows
Lexical analysis – DFA minimization
Parsing – Production Tree
Register allocation – Graph coloring
expression evaluation – Post order traversal

13 Consider the following grammar :
• P → xQRx
• Q → yz|z
• R → w|ε
• S → y
What is FOLLOW (Q)?

FOLLOW(Q) = {w, y}

14 Consider the following expression grammar G:
E → E – T|T
T → T + F|F
F → (E)|id
Which of the following grammars is not left recursive, but is equivalent to G?

left recursion: A → Aα/β
After removing left recursion it can be written as
A → βA’
A' → αA'/ε
So apply above rule for Variable E and T resultant grammar is
E → TX
X → – TX|ε
T → FY
Y → +FY|ε
F → (E) → id

15 Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → numberE.val = number.val
| E '+' EE⁽¹⁾.val = E⁽²⁾.val + E⁽³⁾.val
| E '×' EE⁽¹⁾.val = E(2).val × E⁽³⁾.val;
Assume the conflicts in Part (a) of this question are resolved and an LALR (1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 x 2 + 1. What precedence and associativity properties does the generated parser realize?

With look ahead, we would prefer to shift because the look ahead has higher precedence than X over + and both operation are left associative. So expression 3 x 2 + 1 = 6 + 1 = 7 will be evaluated.