Principles of Compiler Design,UNIT III,2 Marks Q&A

Define parser.

  Hierarchical analysis is one in which the tokens are grouped hierarchically into nested collections with collective meaning. Also termed as Parsing.

Mention the basic issues in parsing.

 There are two important issues in parsing.

   

   Specification of syntax

   Representation of input after parsing.

Why lexical and syntax analyzers are separated out?

 Reasons for separating the analysis phase into lexical and syntax analyzers:

         Simpler design.

         Compiler efficiency is improved. 

         Compiler portability is enhanced. 

  Define 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.

What is a operator precedence parser?

 A grammar is said to be operator precedence if it possess the following properties:

1. No production on the right side is ε.

2. There should not be any production rule possessing two adjacent non terminals at the right hand side.

 List the properties of LR parser.

 1.   LR parsers can be constructed to recognize most of the programming languages for which the context free grammar can be written.

2.  The class of grammar that can be parsed by LR parser is a superset of class of grammars that can be parsed using predictive parsers.

3.  LR parsers work using non backtracking shift reduce technique yet it is efficient one.

Mention the types of LR parser.

 SLR parser- simple LR parser

LALR parser- lookahead LR parser

Canonical LR parser

What are the problems with top down parsing?

 The following are the problems associated with top down parsing:

·         Backtracking

·         Left recursion

·         Left factoring

·         Ambiguity

Write the algorithm for FIRST and FOLLOW.

 FIRST

1. If X is terminal, then FIRST(X) IS {X}.

2. If X → ε is a production, then add ε to FIRST(X).

3. If X is non terminal and X → Y1,Y2..Yk is a production, then place a in FIRST(X) if for some i , a is in FIRST(Yi) , and ε is in all of FIRST(Y1),…FIRST(Yi-1);

FOLLOW

1. Place $ in FOLLOW(S),where S is the start symbol and $ is the input right endmarker.

2. If there is a production A → αBβ, then everything in FIRST(β) except for ε is placed in FOLLOW(B).

3. If there is a production A → αB, or a production A→ αBβ where FIRST(β) contains ε , then everything in FOLLOW(A) is in FOLLOW(B).

List the advantages and disadvantages of operator precedence parsing.

 Advantages

This typeof parsing is simple to implement.

Disadvantages

1.      The operator like minus has two different precedence(unary and binary).Hence it is hard to handle tokens like minus sign.

                  This kind of parsing is applicable to only small class of grammars.

What is dangling else problem?

 Ambiguity can be eliminated by means of dangling-else grammar which is show below:

stmt → if expr then stmt

| if expr then stmt else stmt

| other

Write short notes on YACC.

 YACC is an automatic tool for generating the parser program.

YACC stands for Yet Another Compiler Compiler which is basically the utility available from UNIX.

Basically YACC is LALR parser generator.

It can report conflict or ambiguities in the form of error messages.

Define LR(0) items.

 An LR(0) item of a grammar G is a production of G with a dot at some position of the right side. Thus, production A → XYZ yields the four items

A→.XYZ

A→X.YZ

A→XY.Z

A→XYZ.

What is phrase level error recovery?

 Phrase level error recovery is implemented by filling in the blank entries in the predictive parsing table with pointers to error routines. These routines may change, insert, or delete symbols on the input and issue appropriate error messages. They may also pop from the stack.

Compare production with reduction.

 The rules that define the ways in which the syntactic categories can be built are productions whereas the replacement of the string by an non-terminal according to a grammar production is called reduction.

When will you call a grammar as the left recursive one?

 A grammar is a left recursive if it has a nonterminal A such that there is a derivation AÞAa for some stringa.

Define left factoring.

 Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing. The basic idea is that when it is not clear which of two alternative productions to use to expand a nonterminal “A”, we may be able to rewrite the “A” productions to refer the decision until we have seen enough of the input to make the right choice.

Left factor the following grammar:

S → iEtS | iEtSeS |a

E → b.

            Ans:

            The left factored grammar is,

                        S → iEtSS′ | a

                        S′ → eS | ε

                        E → b

What do you mean by Recursive Descent Parsing?

 Recursive Descent Parsing is top down method of syntax analysis in which we execute a set of recursive procedures to process the input. A procedure is associated with each nonterminal of a grammar.

What is meant by Predictive parsing? Nov/Dec 2007

 A special form of Recursive Descent parsing, in which the look-ahead symbol unambiguously determines the procedure selected for each nonterminal, where no backtracking is required.