Which of the following statements are TRUE? I. There exist parsing algorithms…
2009
Which of the following statements are TRUE?
I. There exist parsing algorithms for some programming languages whose complexities are less than O(n3).
II. A programming language which allows recursion can be implemented with static storage allocation.
III. No L-attributed definition can be evaluated in The framework of bottom-up parsing.
IV. 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
Attempted by 33 students.
Show answer & explanation
Correct answer: B
Final answer: Statements I and IV are true; II and III are false.
I. True — There exist parsing algorithms with complexity better than O(n^3). For many practical grammars, deterministic parsers such as LL and LR run in linear time O(n), and other optimized algorithms achieve sub-cubic performance.
II. False — Languages that allow general recursion require dynamic storage allocation (e.g., activation records on a run-time stack) because multiple simultaneous activations of the same routine need separate storage. Static allocation cannot generally support arbitrary recursion.
III. False — L-attributed definitions are not inherently incompatible with bottom-up parsing. With appropriate use of the parser stack or by introducing marker productions, inherited and synthesized attributes for L-attributed grammars can be evaluated during bottom-up parsing.
IV. True — Code-improving transformations (optimizations) can be applied at the source-language level (source-to-source) and at intermediate-code levels in the compiler.
Therefore, the correct choice is the option that lists the true statements: I and IV.
A video solution is available for this question — log in and enroll to watch it.