Predictive Parsing-Compilers-Professor Alex Aiken

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.

PRINCIPLES OF COMPILER DESIGN,TWO MARKS ,UNIT II

1. Define CFG.

The context free grammar consists of terminals, non terminals, a start symbol, and productions.

            G = (V, T, P, S)

            V-> variables or non terminals (uppercase letters)

            T-> terminals (lowercase letters, operator symbols, digits)

S-> start symbol

P-> productions.

                        Ex:

                                    E->E+E / id

2. What is an ambiguous grammar? Give an example.

·         A grammar that produces more than one parse tree for the same sentence.

·         An ambiguous grammar produces more than one leftmost or more than one rightmost derivation for the same sentence.

Ex:

            E->E+E / E*E / E-E / id

            Input string is id + id * id

3.    What is handle pruning?

->A rightmost derivation in reverse can be obtained by “handle-pruning.”

->The process of discovering a handle & reducing it to the appropriate    left-hand side is called handle pruning.

->Handle pruning forms the basis for a bottom-up parsing method.

Ex:

S ® aABe

A ® Abc | b

B ® d

abbcde

Find the handle = b at loc. 2

aAbcde

b at loc. 3 is not a handle:

aAAcde

... blocked.

4. Define left factoring.

Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing. Two alternative productions to use to expand a nonterminal A.

            A-> αβ₁ / αβ₂

 After applying left factoring

            A-> α A^’

                A-> β₁ / β₂

                        For example consider the following grammar: –

                        S-> iEtS  |  iEtSeS  |  a

                        E -> b

The left factored grammar becomes

S->iEtSS’ | a

S ‘->eS | ε

E ->b

5. What are the properties of operator precedence parsing?

The operator precedence grammar, no production rule can have:

àe at the right side

     àTwo adjacent non-terminals at the right side.

Ex:

      E®AB                                   E®E+E |

                  A®a                                 E*E |

                  B®b                                 E/E | id

       not operator grammar       operator grammar 

6. Define viable prefixes.

The set of prefixes of right sentential forms that can be appearing on the stack of a shift reduce parser. It is a prefix of right sentential form that does not continue past the right end of the rightmost handle of that sentential form.

7. List out the actions involved in shift-reduce parsing.

                                                              i.      Shift -> The next input symbol is shifted onto the top of the stack.

                                                            ii.      Reduce-> It must locate the left end of the handle within the stack and decide with non terminals to replace the handle.

                                                          iii.      Accept-> The parser announces successful completion of parsing.

                                                          iv.      Error-> The parser discovers that a syntax error has occurred and calls an error recovery routine.

8. What are the different types of conflicts occurs in shift reduce parsing?

                                                              i.      shift/reduce conflict -> parser cannot decide whether to shift or to reduce

                                                            ii.      reduce/reduce conflictàparser cannot decide which of several reductions to make

9. What are the recovery strategies in a parser?

                                                              i.      Panic mode recovery

                                                            ii.      Phrase level.

                                                          iii.      Error productions.

                                                          iv.      Global correction

10. Eliminate the left recursion for the given grammar:

E->E+T/T

T->T*F/F

F->(E) / id.

After eliminating the left recursion

            E->TE’

            E’->+TE’ / ε

            T->FT’

            T’->*FT’ / ε

            F->(E) / id

11. Write a rule to construct precedence function table.

Ø  For each production A-> α of the grammar do step 2 and 3.

Ø  For each terminal a in FIRST (α), add A-> α to M [A, a].

Ø  If ε is in FIRST (α), add A-> α to M [A, b] for each terminal b in FOLLOW (A). If ε is in FIRST (α) and $ is in FOLLOW (A), add A-> α to M[A, $].

Ø  All the remaining entries in table M are marked as SYNTAX ERROR

12. Write down the rules for left recursion.

                                    To eliminate left recursion we need to modify the grammar having

a production rule with left recursion.

                              A        Aα  / β

Then we eliminate left recursion by re-writing the production rule as:

                        A         βA ‘

                        A’         αA ‘  /  ε

13. What are the goals of error handler in a parser?

1.      It should report the presence of errors clearly and accurately.

2.      It should recover from each error quickly enough to be able to detect subsequent errors.

3.      It should not significantly slow down the processing of correct programs.

14. Differentiate Top down and bottom up approach with an example.

Sl.No	Top down parsing (LL(1), recursive descent)	Bottom up parsing (LR(k), operator precedence and shift reduce parsing)
1	Start at the root of the parse tree from the start symbol and grow toward leaves (similar to a derivation)	Start at the leaves and grow towards the root.
2	Pick a production and try to match the input	We can think of the process as reducing the input string to the start symbol
3	Bad “pick” Þ may need to backtrack	At each reduction step a particular substring matching the right-side of a production is replaced by the symbol on the left-side of the production
4	Some grammars are backtrack-free  (predictive parsing)	Bottom-up parsers handle a large class of grammars
5.	Ex: E->E+E /E * E / id Top down: E=>E+E E=>E+E*E E=>id+E*E E=>id+id*E E=>id+id*id	E->E+E / E* E / id Bottom up: =>id+id*id =>E+id*id =>E+E*id =>E+E*E =>E+E =>E

15. Eliminate the left recursion from the following grammar

A->Ac / Aad / bd / c

After eliminating the left recursion

A->bdA’ / A’

A’->cA’ / adA’ / ε

16. Differentiate SLR, CLR, and LALR parser.

S.NO	SLR	CLR	LALR
	Small in parser size	Larger than SLR	Same as SLR in Size
	Less powerful than CLR	More powerful than SLR	Less powerful than CLR.But the Syntactic features can be expressed in the grammar of LALR.
	Time and space complexity is less	More time and space complexity	Intermediate time and space complexity.
	Error detection is not immediate in SLR	Error detection is immediate in LR	Error detection is not immediate in LALR
	Its not applicable in all Ambiguous grammar	Its applicable to ambiguous grammar than SLR	Its Applicable to all ambiguous grammar.

17. What are kernel and non-kernel items?

Kernel items:

            It is the collection of item S’-> .S and all the items whose dots are at the leftmost end of RHS of the rule.

Non – Kernel items:

            It is the collection of all the items   in which ‘ . ‘ are at the leftmost and  RHS of the rule.

18. What are the disadvantages of operator precedence parsing?
1. It cannot handle the unary minus (the lexical analyzer should handle   the unary minus).
2. Small class of grammars.
3. Difficult to decide which language is recognized by the grammar.

19. Define LR (k).

A grammar that can be parsed by an LR parser examining to up k input symbols on each move is called LR (k) grammar. We must be able to recognize the occurrence of the right side with k input symbols. We must be able to recognize the use of a production seeing only the first k symbols of what its right side derives.

            L-> denotes that input sequence is processed from left to right.

            R-> denotes that the right most derivation is performed.

            k-> denotes that at most k symbols of the sequence are used to make a decision.

20. Define SLR.

SLR-> Simple LR (LR (0))

            The idea is construction of a DFA from the grammar.

A grammar for which an SLR parser can be constructed is said to be SLR grammar.

            An LR (0) of a grammar G is a production of G with a dot operator at some position of the right side.

            Ex: A->XYZ yields four items.

                        A->.XYZ

                        A->X.YZ

                        A->XY.Z

                        A->XYZ.