CFG
Question 1 |
Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?
5 | |
4 | |
3 | |
2 |
Question 1 Explanation:
Total 5 parse trees possible (solved in previous question).
Question 2 |
Which of the following features cannot be captured by context-free grammars?
Syntax of if-then-else statements | |
Syntax of recursive procedures | |
Whether a variable has been declared before its use | |
Variable names of arbitrary length |
Question 2 Explanation:
Context free grammars are used to represent syntactic rules while designing a compiler.
Syntactic rules not checking the meaningful things such as if a variable is declared before it use (or) not.
Like this, things are handled by semantic analysis phase.
Syntactic rules not checking the meaningful things such as if a variable is declared before it use (or) not.
Like this, things are handled by semantic analysis phase.
Question 3 |
If G is a context-free grammar and w is a string of length l in L(G), how long is a derivation of w in G, if G is Chomsky normal form?
2l | |
2l + 1 | |
2l - 1 | |
l |
Question 3 Explanation:
For CNF, it is
2l - 1
For GNF, it is
l
2l - 1
For GNF, it is
l
There are 3 questions to complete.