Project ForgeWhich of the following statements are TRUE? I. There exist parsing algorithms for some programming languages whose complexities are less than Θ(n³). 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.
- AI and II
- I and IV
- CIII and IV
- DI, III and IV
Explanation
I is true: LL/LR parsing algorithms run in linear O(n) time for their respective grammar classes, well below Θ(n³) (the general CYK bound). II is false: recursion fundamentally requires dynamic (stack-based) allocation to support multiple simultaneous activations. III is false: L-attributed definitions CAN be evaluated during bottom-up (LR) parsing with appropriate semantic action placement. IV is true: optimizing transformations are applied at both the source level (source-to-source optimization) and the intermediate-code level.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.