GATE CSE 2009 | Question: 42

Question

Which of the following statements are TRUE?

1. There exist parsing algorithms for some programming languages whose complexities are less than $\Theta(n^3)$

2. A programming language which allows recursion can be implemented with static storage allocation.

3. No L-attributed definition can be evaluated in the framework of bottom-up parsing.

4. Code improving transformations can be performed at both source language and intermediate code level.

• A. I and II
• B. I and IV
• C. III and IV
• D. I, III and IV

Comments

For point 2 we can refer to  question https://gateoverflow.in/477/gate2008-54  (point 3)

---

L- attributed → top-down parsing

S-attributed → bottom-up parsing and top-down parsing

Every S attributed is L attributed grammar.

---

https://cse.iitkgp.ac.in/~bivasm/notes/SDD.pdf

refer this one.

---

Kuch parsing algorithms jo ( theta(n^3) ) se kam samay mein kaam karte hain :

1. LR(k) Parsers: Ye parsers bottom-up parsing ka istemal karte hain aur kuch cases mein inka complexity ( O(n) ) ya ( O(n^2) ) tak ho sakta hai.

2. Earley Parser: Ye algorithm context-free grammars (CFGs) ke liye kaam karta hai aur iska worst-case time complexity ( O(n^3) ) hai, lekin ye deterministic grammars ke liye ( O(n^2) ) tak kaam kar sakta hai. Iska special advantage ye hai ki ye ambiguous grammars ko bhi parse kar sakta hai.

3. CYK (Cocke-Younger-Kasami) Algorithm: Ye algorithm bhi context-free grammars ke liye hai aur iska time complexity ( O(n^3) ) hai, lekin kuch optimized versions ( O(n^2) ) ya isse bhi kam achieve kar sakte hain.

4. Packrat Parsing: Ye parsing technique recursive descent parsing ka istemal karti hai jo backtracking ko optimize karti hai aur kisiki input pe linear time complexity achieve kar sakti hai agar grammar LL(k) ho.

Answer 1

Answer is B.

• A. Yes there does exist parsing algorithms (e.g. CYK algorithm) which run in $\Theta(n^3)$.
• B. It cannot be implemented with static storage allocation. It needs dynamic memory allocation.
• C. Every S-attributed definition is also an L-attributed definition and can be evaluated in the framework of bottom up parsing.
• D. True.

Comments

A programming language which allows recursion can be implemented with static storage allocation.FALSE

 It needs Stack storage allocation instead of dynamic storage allocation.

---

recursion requires stack and not heap(used for dynamic memory allocation)

---

Can you please, state an example.

Answer 2

LL(1) and LR parsers are linear time parsers. ie, $O(n)$

I is True.

PS: Recursive descent parser runs in $O(2^n)$ time.

---

Recursion needs stack

II is False

---

L-attributed definitions have both inherited and synthesized attributes. Can be evaluated with top-down-left-to-right style.

S-attributed definitions have only synthesized attributes. Can be evaluated with bottom-up style.

 

So, in case a definition only has synthesized attributes, we can call it both L and S attributed. Such an L-attributed definition can be evaluated with bottom-up style.

So, III is False.

---

Code improvement can obviously be done at the user-level by not writing stupid code. And compiler also improves (optimises) the code. Hence,

IV is True.

Comments

Every S attributed grammer is L attributed too and S-attributed SDTs are evaluated in bottom-up parsing, as the values of the parent nodes depend upon the values of the child nodes. This means some L attributd SDT are also solved in bottom up fashion , which prooves 3rd statement is FALSE

---

Correct! :)

---

@JashanArora Sir can you please clear one doubt from this question https://gateoverflow.in/908/gate2003-18?

I am not able to understand why option B is correct? Is it because L-attributed contains both inherited and synthesized attribute, and inherited one can be solved using bottom up? Is my understanding correct?

Thanks in advance.

Answer 3

1. There exist parsing algorithms for some programming languages whose complexities are less than (O(n3):

   • True. There are parsing algorithms, such as LL(k) and LR(k), whose complexities are less than O(n3).

2. A programming language which allows recursion can be implemented with static storage allocation:

   • False. Recursion generally requires dynamic storage allocation, as static allocation may not handle arbitrary levels of recursion.

3. No L-attributed definition can be evaluated in the framework of bottom-up parsing:

   • True. L-attributed definitions require a top-down parsing approach, as they involve attributes associated with the leftmost derivations.

4. Code improving transformations can be performed at both source language and intermediate code level:

   • True. Code optimizations can be applied at both the source language level (before compilation) and the intermediate code level (during compilation).

Therefore, the correct answer is:

I and IV