MindStudy - MindStudy

Question:

Published on: 25 April, 2024

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

Mobile computing Design and Analysis of Algorithm Computer Graphics and Multimedia Compiler Design Software Engineering Database Management System

Trending

Consider the following grammar:

Prove the above grammar is LL (1). Draw the parsing table. Now check whether the string “ab” and “acbd” are the languages of the above grammar. (Derive each step with the help of a stack.)

25 April, 2024

Write short notes on:

Back patching
Thompson’s construction
Constant folding and copy propagation

25 April, 2024

Explain different stages of compiler with a suitable example. What is token, Patterns and Lexeme?

25 April, 2024

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;

}

25 April, 2024

Describe various actions of a shift reduce parsers.

25 April, 2024

Reflection

Compression of GIF images