Predictive Top Down Parsing - Computer Science Engineering (CSE) MCQ

Explanation: Since there is no conflict, the grammar is LL (1) hence a predictive parse table with no conflicts can be constructed.

Concept:

Option 1: The LALR(1) parser for a grammar G cannot have a reduce-reduce conflict if the LR(1) parser for G does not have a reduce-reduce conflict. 

False, If there is no S-R conflict in LR(1) state, it will never be reflected in the LALR(1) state obtained by combining LR(1) states; but, this merging method may create R-R conflict, and the Grammar will not be LALR (1).

Option 2: Symbol table is accessed only during the lexical analysis phase

False, The information in the symbol table is provided during the lexical and syntax analysis phases, but it is needed in subsequent stages of the compiler (semantic analysis, intermediate code generation, code optimization, and code generation).

Option 3:Data flow analysis is necessary for run-time memory management.

False, Data flow analysis is used in control flow graphs for code optimization. It is the analysis of data flow in a control flow graph, that is, the analysis that determines information about data definition and usage in a program. Optimization can be achieved with the use of this analysis.

Option 4: LR(1) parsing is sufficient for deterministic context-free languages

True, LR(k) grammars (also known as deterministic context-free grammars) allow parsing (string recognition) with deterministic pushdown automata (PDA), they can only define deterministic context-free languages.

Hence the correct answer is LR(1) parsing is sufficient for deterministic context-free languages.

Explanation: Left to right constructing leftmost derivation of the sentence.

CONCEPT:

Consider the expession "id-id+id*id" :

Option 1: False

'+' has higher precedence than '⋆ ', since '+' will execute before '*'.

Option 3: False

'-' has higher precedence than '+ ', since '-' will execute before '+'.

Option 4: False

'*' & '+' have same precedence.

Explanation: The prefixes on the stack of a shift-reduce parser are called viable prefixes.

Explanation: Successors depends on input .

Explanation: The entire column an items matches the Column B items in a certain way.

Concept:

Statement A: SLR parser is more powerful than LALR parser.

False, LALR(1) parser is more powerful than SLR(1) and LR(0) parser. LALR offers a good solution, because LALR(1) grammars are more powerful than SLR(1), and can parse most practical LL(1) grammars. LR(1) grammars are more powerful than LALR(1).


Statement B: Canonical LR parser is more powerful than LALR parser.

True, Canonical LR parser is more powerful than LALR parser. The number of states in the parsing automaton differs between the CLR and LALR algorithms. CLR parsers have a much larger number of states than LALR parsers.

Statement C: LALR parser is more powerful than Canonical LR parser.

False, Canonical LR parser is more powerful than LALR parser. Canonical (CLR) is the most powerful Parsers among all the LR(k) Parsers or SLR.

Hence the correct answer is Only B.

Explanation: There is ambiguity as the string can be derived in 2 possible ways.
First Leftmost Derivation
S → F
F → c
Second Leftmost Derivation
S → H
H → c 

Explanation: the moves are n-1.