COSC4307                              TEST-2                                                           11/27/2007

 

Keys Used

          1-5:              BACDC

          6-10:            CDDDD

          11-15:           ABCCA

          16-20:           ABCCA

          21-25:           EDAEB

 

NAME____________________________________________________

 

NOTE:    1.             Alpha:                    A string of grammar symbols, possibly empty.

                2.             l:                             The empty-string.

                3.             A -> Alpha:           A production rule of a CFG.

                4.             RHS:                       Right-hand side

                5.             S.F:                         Sentential Form.

                6.             R.S.F:                      Rightmost sentential form

7.             CFG:                       Context-Free Grammar.

                8.             OPR:                       Operator Precedence Relation

                9.             SPR:                        Simple Precedence Relation

 

PART-A.               Multiple Choices.                                                                                                (75 points)

 

Answer all 25 questions in this PART-A. Each question is 3 points worth.

Mark your BEST choice by writing down a big A or B or C or D or E or F in Capital by each question number.

 

The first 12 questions are about the following CFG where each character is a grammar symbol.

 

                S  ->  a  S  a                            // Rule-1

                S  ->  R b  R                           // Rule-2

                R  ->  c  S  c                           // Rule-3

                R  ->  (  S  )                             // Rule-4

                R  ->  b  R                               // Rule-5

                R  ->  d                                   // Rule-6

 

1.             The OPR “<” applies to

                a.             b  a

                b.             b (                                           c.             both.                                       d.             neither.

2.             The OPR “>” applies to

                a.             )  b

                b.           R  b                                           c.             both.                                       d.             neither.

 

3.             The SPR “<” applies to

                a.             b  c

                b.             (   c                                          c.             both.                                       d.             neither.

 

4.             The SPR “>” applies to

                a.             )   a

                b.             )   b

                c.             c  a                                         

d.             all above.                               e.             two above.                            f.              none above.

 

5.             The SPR “=” applies to

                a.             R  S

                b.             (    )

                c.             c   S

                d.             all above.                               e.             two above.                            f.              none above.

 

****End-of-production-rule replacement supposition****

 

6.             The grammar is

                a.             LL(1)

                b.             an Operator grammar.

                c.             both.                                       d.             neither.

7.             Which rule has the same PREDICT set as its FIRST set?

                a.             rule-1

                b.             rule-2

                c.             rule-3

                d.             all above.                               e.             two above.                            f.              none above.

 

8.             The FOLLOW set of the nonterminal S includes, among others,

                a.             )

                b.             c

                c.             a

                d.             all above.                               e.             two above.                            f.              none above.

9.             The Initial state (I0) of the SLR(1) parser includes

                a.             R -> . ( S )                              

                b.             S -> . a  S  a

                c.             R -> . b  R

                d.             all above.                               e.             two above.                            f.              none above.

10.           How many next states does the Initial state of the SLR(1) parser have?

                a.             2

                b.             3

                c.             4                                              d.             none.

11.           Which is a R.S.F?

                a.             a a R b  ( S ) a a

                b.             ( S ) b b b R

                c.             both.                                       d.             neither.

12.           Which is a S.F?

                a.             a ( S ) R a

                b.             (  S ) b b b d

                c.             both.                                       d.             neither.

13.           The PREDICT set of a production rule must be the same as its FIRST set if 

                a.             the grammar has no Empty-production-rule.

b.                   the production rule cannot derive the Empty-String even when the grammar

has an Empty-production-rule.

                c.             Both.                                      d.             Neither.

14.           FOLLOW sets are used

                a.             in calculating PREDICT sets when the grammar has an Empty-Production rule.

                b.             as a basis for reductions in SLR(1) parsers.   

                c.             Both.                                      d.             Neither.

 

15.           In general, given a grammar, the LR(1) parser 

                a.             has more number of states than the LALR(1) parser does.

                b.             may have a conflict where the LALR(1) parser does not.

                c.             Both.                                      d.             Neither.

16.           Leftmost derivation sequences are for

a.                    Top-down parsers

b.                   Precedence-based parsers

c.                    Both.                                      d.             neither

 

17.           The syntax stack contents of LL(1) parsers are

                a.             the entire leftmost S.F. at any time.

                b.             a proper suffix of a Leftmost S.F most of the time.

                c.             Both.                                      d.             Neither.

 

18.           A conflict in SLR(1) parsers can occur between

                a.             two Reductions.

                b.             one Reduction and one Shift only in a state that is inadequate.

                c.             both.                                       d.             neither.                                  

19.           Which parse table's empty (blank) entry represents a syntax error?

                a.             LL(1) Parsers.

                b.             SLR(1) Parsers

                c.             both.                                       d.             neither.

 

20.           Which class represents the broadest class of deterministic parsers?

                a.             LR(1) parsers.

                b.             SLR(1) parsers.

                c.             LL(1) parsers.       

21.           Which prevents a grammar from being LL(1)?

                a.             a left recursive rule, not necessarily direct.

                b.             a non-terminal with two non-disjoint PREDICT sets.

                c.             a terminal which is a member in two or more different FOLLOW sets.

                d.             all above.                               e.             two above.                            f.              none above.

22.           In general (that is, most of the times), the contents of a syntax stack used by Operator Precedence-based

parsers are

                a.             a suffix of the R.S.F.

                b.             a prefix of the S.F., not necessarily rightmost.

                c.             both.                                       d.             neither. 

23.           Which is true about LALR(1) parsers?

a.                    they are compromise between SLR(1) parsers and LR(1) parsers.

b.                   they use LR(1) items as a basis for reductions just as SLR(1) parsers.

c.                    They have the same number of states as LR(1)  parsers.

d.                   All above.                              e.             two above.                            f.              none above.

24.           Which is true about  Inadequate” states?

a.                    they are the only possible states where a conflict can occur.

b.                   they may contain no “Included” item.

c.                    they may contain no “Completed” item.

d.                   All above.                              e.             two above.                            f.              none above.

25.           Which is true about “Viable” Prefix?

a.                    it is about any sentential form, not necessarily rightmost ones.

b.                   it must be recognized by a state of SLR(1) parsers.

c.                   It may not be recognized by any state of an SLR(1) parser.

d.                   All above.                              e.             two above.                            f.              none above.

 

 

PART-B.         Other problems                                                                      (25 points)

 

Do three problems in this PART-B.

 

For first four problems in this PART-B, consider the following CFG:
 

                A ->        A  +  B

                A ->        B   A   B

                A ->        a   B

                B ->         (  A  )   A

                B ->         b                       // where each character is a grammar symbol.

 

A.            Calculate and clearly show FOLLOW set of each non-terminal of above grammar.

Do not forget using the end-marker, $.

 

 

  B.          Give the description of each function of a Recursive descent parser for the above grammar.

 

  C.         Give all pairs of two grammar symbols to each of which the SPR “>” applies.

 

  D.          Eliminate the (direct) left recursive rule(s) of the non-terminal ‘A’ and

clearly show the resulting new grammar.

 

E.          Give the condition(s) for LL(1) grammars?

              And, give a reason of why they are desirable.