MindStudy - MindStudy

Question:

Published on: 23 February, 2025

Describe various actions of a shift reduce parsers.

Answer:

Actions of shift-reduce parsers:

A shift-reduce parser works by doing some combination of Shift steps and Reduce steps, hence the name.

A shift step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree.
A Reduce step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol.

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 N² or N³ time when they guess badly.

To avoid guessing, the shift-reduce parser often looks ahead (rightwards) at the next scanned symbol, before deciding what to do with previously scanned symbols. The lexical scanner works one symbol ahead of the rest of the parser. The lookahead symbol is the 'right-hand context' for each parsing decision. (Rarely, two or more lookahead symbols may be utilized, although most practical grammars can be designed to use one lookahead symbol.)

Let a grammar is:

Assign ← id = Sums

Sums ← Sums + Products

Sums ← Products

Products ← Products * Value

Products ← Value

Value ← int

Value ← id

Parse Steps for Example A = B + C*2

Step	Parse Stack	Look Ahead	Unscanned	Parser Action
0	empty	id	= B + C*2	Shift
1	id	=	B + C*2	Shift
2	id =	id	+ C*2	Shift
3	id = id	+	C*2	Reduce by Value ← id
4	id = Value	+	C*2	Reduce by Products ← Value
5	id = Products	+	C*2	Reduce by Sums ← Products
6	id = Sums	+	C*2	Shift
7	id = Sums +	id	*2	Shift
8	id = Sums + id	*	2	Reduce by Value ← id
9	id = Sums + Value	*	2	Reduce by Products ← Value
10	id = Sums + Products	*	2	Shift
11	id = Sums + Products *	int	eof	Shift
12	id = Sums + Products * int	eof		Reduce by Value ← int
13	id = Sums + Products * Value	eof		Reduce by Products ← Products * Value
14	id = Sums + Products	eof		Reduce by Sums ← Sums + Products
15	id = Sums	eof		Reduce by Assign ← id = Sums
16	Assign	eof		Done

A shift-reduce parser waits until it has scanned and parsed all parts of some construct before committing to what the combined construct is. The parser then acts immediately on the combination instead of waiting any further. In the parse tree example above, the phrase B gets reduced to Value and then to Products and Sums in steps 3-6 as soon as lookahead + is seen, rather than waiting any later to organize those parts of the parse tree. The decisions for how to handle B are based only on what the parser and scanner have already seen, without considering things that appear much later to the right.

Reductions reorganize the most recently parsed things, immediately to the left of the lookahead symbol. So the list of already-parsed things acts like a stack. This parse stack grows rightwards. The base or bottom of the stack is on the left and holds the leftmost, oldest parse fragment. Every reduction step acts only on the rightmost, newest parse fragments. (This accumulative parse stack is very unlike the predictive, leftward-growing parse stack used by top-down parsers.)

When a grammar rule like

Products ← Products * Value

is applied, the stack top holds the parse trees "... Products * Value". This found instance of the rule's right hand side is called the handle. The reduce step replaces the handle "Products * Value" by the left hand side nonterminal, here a larger Products. If the parser builds complete parse trees, the three trees for inner Products, *, and Value are combined by a new tree root for Products. Otherwise, semantic details from the inner Products and Value are output to some later compiler pass, or are combined and saved in the new Products symbol.

The parser keeps applying reductions to the top of the parse stack for as long as it keeps finding newly completed examples of grammar rules there. When no more rules can be applied, the parser then shifts the lookahead symbol onto the parse stack, scans a new lookahead symbol, and tries again.

Subjects

Data Structures & Algorithm Computer Graphics and Multimedia Design and Analysis of Algorithm Compiler Design C Programming and Practices Mobile computing

Trending

Explain left factoring with suitable example.

23 February, 2025

Convert the Regular Expression into e-NFA and then corresponding DFA.

23 February, 2025

Eliminate left recursion from the following grammar:

23 February, 2025

Generate the three address code for the following code segment.

main()

{

       int a=1, z=0;

       int b[10];

       while (a<=10)

             b[a]=2*a;

       z=b[a]+a;

}

23 February, 2025

Consider the grammar:

S → aSbS | bSaS | 𝜖

Show that this grammar is ambiguous by constructing two different left most derivations for the sentence abab.

Construct the corresponding right most derivations for abab.

Construct the corresponding parse tree for abab.

What language does this grammar generate?

23 February, 2025