Compiler design miscellaneous Easy Questions and Answers | Page - 10

Compiler design miscellaneous

Consider the syntax directed translation scheme (SDTS) given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.
E → E₁ * T {E.val = E₁ .val * T. val}
E → T {E.val = T. val}
T → F – T₁ {T.val = F.val – T₁. val}
T → F {T.val = F. val}
F → 2 {F.val = 2}
F → 4 {F.val = 4}
(a) Using this SDTS, construct a parse tree for the expression 4 – 2 – 4 * 2 and also compute its E.val.
(b) It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find E.red, the number of reductions performed while reducing an input to E.

1. E.val = 12 ; E.red = T.red + 1
1. E.val = 2 ; E.red = T.red + 1
1. E.val = 10 ; E.red = T.red - 1
1. All of these

View Hint View Answer Discuss in Forum

(a) E.val = 12
(b) E → E₁ * T {E.red = E₁ .red + T. red + 1}
E → T {E.red = T.red + 1}
T → F – T₁ {T.red = F.red + T₁ .red + 1}
T → F {T.red = F.red + 1}
F → 2 {F.red = 1}
F → 4 {F.red = 1}

Correct Option: A

(a) E.val = 12
(b) E → E₁ * T {E.red = E₁ .red + T. red + 1}
E → T {E.red = T.red + 1}
T → F – T₁ {T.red = F.red + T₁ .red + 1}
T → F {T.red = F.red + 1}
F → 2 {F.red = 1}
F → 4 {F.red = 1}

Which of the following derivations does a top-down parser use while parsing an input string? The input is assumed to be scanned in left to right order.

1. Leftmost derivation
1. Leftmost derivation traced out in reverse
1. Rightmost derivation
1. Rightmost derivation traced out in reverse

View Hint View Answer Discuss in Forum

In top down parsing, we just start with the start symbol and compare the RHS of the different productions against the first piece of input to see which of the productions should be used. A topdown parser is called LL parser because it parses the input from Left to right. eg:
S → Ax
A → a
For an input ax Top down parser will do parsing as

Correct Option: A

In top down parsing, we just start with the start symbol and compare the RHS of the different productions against the first piece of input to see which of the productions should be used. A topdown parser is called LL parser because it parses the input from Left to right. eg:
S → Ax
A → a
For an input ax Top down parser will do parsing as

Given the following expression grammar
E → E * F | F + E | F
E → F – | id
Which of the following is true?

1. * has higher precedence than +
1. – has higher precedence than *
1. + and – have same precedence
1. + has higher precedence than *

View Hint View Answer Discuss in Forum

‘–’ has higher precedence than ‘*’ as ‘–’ is a leaf node in the tree formed using this whereas ‘*’ is not.

Correct Option: B

‘–’ has higher precedence than ‘*’ as ‘–’ is a leaf node in the tree formed using this whereas ‘*’ is not.

Consider the following C code segment :
for (i = 0, i < n; i ++) {
for (j = 0, j < n; j ++) {
if (i % 2){
x + = (4 * j + 5 * i);
Y + = (7 + 4 * j);}}}
Which one of the following is false?

1. The code contains loop invariant computation.
1. There is scope of common sub-expression elimination in this code
1. There is scope of strength reduction in this code
1. There is scope of dead code elimination in this code

View Hint View Answer Discuss in Forum

The expression (4*j) is used at two places- so common sub-expression elimination is possible i% 2 is loop invariant for the inner loop
5*i is also loop invariant for inner loop x + = 5*i can be replaced by x + = p;
p + = 5; (p must be initialized to 0 before the loop).
Thus replacing * with + gives strength reduction. So, only (d) is false here.

Correct Option: D

The expression (4*j) is used at two places- so common sub-expression elimination is possible i% 2 is loop invariant for the inner loop
5*i is also loop invariant for inner loop x + = 5*i can be replaced by x + = p;
p + = 5; (p must be initialized to 0 before the loop).
Thus replacing * with + gives strength reduction. So, only (d) is false here.

Consider the grammar shonws below :
S → CC
C → cc/ d
This grammar is

1. LL (1)
1. SLR (1) but not LL (1)
1. LALR (1) but not SLR (1)
1. LR (1) but not LALR (1)

View Hint View Answer Discuss in Forum

First (S) = First (C) = {c,d} there are no multiple in single row of parsing table hence grammar is LL₁
Note : if we have A → B/C for grammar to be LL(1) first(B) intersection First(C) should be null otherwise grammar is not LL₁. If First(B) contains epsilon then Follow(A) intersection First(C) should be null. Using this we can say grammar is LL(1) or not without constructing parsing table.
An ∈ ∈ free LL(1) grammar is also SLR(1) and hence LALR(1) and LR(1) too.
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).

Correct Option: A

First (S) = First (C) = {c,d} there are no multiple in single row of parsing table hence grammar is LL₁
Note : if we have A → B/C for grammar to be LL(1) first(B) intersection First(C) should be null otherwise grammar is not LL₁. If First(B) contains epsilon then Follow(A) intersection First(C) should be null. Using this we can say grammar is LL(1) or not without constructing parsing table.
An ∈ ∈ free LL(1) grammar is also SLR(1) and hence LALR(1) and LR(1) too.
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).