retagged by
4,621 views

3 Answers

Best answer
5 votes
5 votes

Answer : Both shift reduce conflict and reduce reduce conflict

A shift-reduce parser scans and parses the input text in one forward pass over the text, without backing up.

selected by
1 votes
1 votes

Ans (C) 

A shift-reduce parser scans and parses the input text in one forward pass over the text, without backing up. (That forward direction is generally left-to-right within a line, and top-to-bottom for multi-line inputs.)

The shift-reduce parser's efficiency is from doing no backups or backtracking. Its total time scales up linearly with the length of the input and the size of the complete parse tree. Other parser methods that backtrack may take N2 or N3 time when they guess badly. (Citation required)

There are problems associated with methods of top-down parsing with full backup: 
1. Because of the many procedure calls or the excessive amount of backtracking required in some cases, they can be exceedingly slow. In some cases, the number of possible paths through all potential syntax trees can become so large that the construction of a parse for certain sentences becomes prohibitively expensive.

2. Error recovery can be very poor. One does not really find out that the input string is syntactically erroneous until all combinations have been tried, and by that time one cannot tell the first point at which an error was detected and why there is an error because the pointer into the input has been reset.

3. If code has been emitted as the parse has progressed, then every time we have to backtrack, we are forced to erase this code. This requires additional bookkeeping to associate blocks of code with states of the parse so that the required erasing can be performed correctly.

Solution:
Minimize the amount of backup performed. How much backup can be eliminated depends, of course, on the grammar, but empirically it has been found that most (if not all!) of the features deemed desirable in a programming language can be described by context-free grammars that can be parsed with no backup or limited backup. 

Reference link 1

Reference link 2

edited by
1 votes
1 votes

Ans is C

A shift-reduce parser scans and parses the input text in one forward pass over the text, without backing up.
A shift/reduce parser has two different actions it can take SHIFTING and REDUCING.
Shift:
the shift action is when the parser takes the first unanalysed word from the sentence, looks up its dictionary rule, and puts a token of category of the word onto the stack.
Reduce:
the reduce action is when the parser tries to match the topmost category tokens on the stack to the right hand side of the rule. If this succeeds, the tokens are removed and a token for the category on the left hand side of the rule is put on the stack instead.
the shift-reduce parser faces four types of conflicts:
1. shift vs. shift;
2. shift vs. reduce left;
3. shift vs. reduce right;
4. reduce left vs. reduce right

Answer:

Related questions

2 votes
2 votes
1 answer
1
makhdoom ghaya asked Jun 8, 2016
1,288 views
Which of the following suffices to convert an arbitrary $CFG$ to an $LL(1)$ grammar ? Removing left recursion aloneRemoving the grammar alone Removing left recursion and ...
0 votes
0 votes
2 answers
3
makhdoom ghaya asked Jul 1, 2016
3,365 views
Match the following $:$$\begin{array} {cIcI} & \textbf{List – I} && \textbf{List – II} \\ \text{a.} & \text{DDL} & \text{i.} & \text{LOCK TABLE} \\ \text{b.} & \tex...
2 votes
2 votes
3 answers
4
makhdoom ghaya asked Jul 1, 2016
19,955 views
Let $R =\{A, B, C, D, E, F\}$ be a relation schema with the following dependencies $C \rightarrow F$, $E \rightarrow A$, $EC \rightarrow D$, $A \rightarrow B$. Which of t...