MindStudy - MindStudy

Question:

Published on: 23 February, 2025

What do you mean by a Handle? Give example. When a grammar is called ambiguous? Is there any technique to remove ambiguity? Explain with an example. What is the reduce-reduce conflict in LR parser? What are various data structures used for symbol table construction?

Answer:

Handle: A handle of a string is a substring that matches the right side of a production, and whose reduction to the non-terminal on the left side of the production represents one step along the reverse of a rightmost derivation.
Ex.- A handle of a right – sentential form γ is a production A → β and a position of γ where the string β may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of γ. That is, if S →αAw →αβw, then A → β in the position following α is a handle of αβw.
Ambiguous grammar: A grammar G is said to be ambiguous if it generates more than one parse tree for some sentence of language L (G). i.e. both leftmost and rightmost derivations are same for the given sentence.
Techniques to remove ambiguity of a grammar:

- Elimination of Left Recursion:A grammar is left recursive if it has a non-terminal A, such that there is a derivation A → Aα for some string α.

A left-recursion production of the form A → Aα | β could be replaced by the non-left-recursive productions as follows:

Without changing the set of strings derivable from A.

- Left Factoring:

The basic idea is that when it is not clear which of two alternative productions to use to expand a non-terminal A, then rewrite the A-productions to defer the decision until the input to make the right choice.

In general, a production is of the form A → αβ1 | αβ₂ then it is left factored as:

Reduce-reduce conflict in LR parser:

One problem may generate in case of producing Canonical collections for LR (0) parsing table. Assume that there is a state like as follows:

I₅

A→α.

B→β

So the transition table will be:

	Action
	a	b
I₅	r1/r2	r1/r2
	…	…

We can notice that there are 2 final states, so two reduce functions in each action. It is called reduce-reduce conflict. In SLR (1), it will conflict only when FOLLOW(α)∩FOLLOW(β)≠Ø.

If a compiler is to handle a small amount of data, then the symbol table can be implemented as an unordered list, which is easy to code, but it is only suitable for small tables only. A symbol table can be implemented in one of the following ways:
- Linear (sorted or unsorted) list
- Binary Search Tree
- Hash table

Among all, symbol tables are mostly implemented as hash tables, where the source code symbol itself is treated as a key for the hash function and the return value is the information about the symbol.

Subjects

Design and Analysis of Algorithm Data Structures & Algorithm Computer Graphics and Multimedia C Programming and Practices Compiler Design Software Engineering

Trending

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

Describe various actions of a shift reduce parsers.

23 February, 2025

For the input expression (4*7+1)*2, construct an annotated parse tree.

23 February, 2025

Eliminate left recursion from the following grammar:

23 February, 2025

Write short notes on:

LEX

YACC

23 February, 2025