COSC4307                                                      Test-1                                                 6/19/2008

 

 

NAME (Please PRINT)____________________________________________________

 

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.                                                                                                                (84 points)

 

Answer 28 questions in this PART-A by clearly crossing out those you select not to ANSWER..

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 you select to answer.

 

1.  Which is for compiling a source program?

                   L       P                                       S     P 

      a.    M  ---     --                b.    N  ---   --                                          c. both.                    d. neither

                 M.M   L                                     N.N  N

 

                     L        S

2.          M   ----     ----

                  M.M   L.N

   

      a.       Above may represent converting a compiler into another.

b.          Above may produce a compiler that can be run by the same computer being used.             

c.          both.                                       d. neither.

 

3.  Identifier scope rule is for binding

      a.       local names

      b.       non-local names and parameters.                      c. both.                   d. neither.

 

4.  The Static Scope rule is more suitable than the Dynamic Scope rule when

      a.       subprograms or blocks can be nested.

      b.       only non-local names need to be bound.         c. both.       d. neither.

 

5.  Which is true about lex?

      a.       it is an automatic parser generator supported by UNIX.

b.          it produces a C program as functions that the wanted scanner needs are provided as a part

of inputs.                                                               c. both.       d. neither.

 

6.  Which is true of an ambiguous grammar?

      a.       at least one sentence of the language being defined by the grammar is ambiguous.

b.          at least one grammar may define the same language that the grammar defines.                     

c.          both.                                                                       d. neither.

 

7.  The stack used in Program-2 (Scanner Generator)

      a.       is to be pushed onto each time a block starts in the source program being compiled.

      b.       is to be popped off each time a block ends in the source program.

c.       both.                                                                       d.    neither.

 

8. Which is true of Automatic Scanner Generators?

      a.       regular expressions are used in their inputs.

      b.       they essentially convert regular expressions into Finite State Acceptors.

      c.       both.                                                                       d. neither.

 

9. A parse tree of a given sentence may show

      a.       only one leftmost derivation sequence.

      b.       two different derivation sequences, not leftmost nor rightmost.

      c.       both.                                                                       d. neither.

 

10. Two different leftmost derivation sequences of a given sentence may imply

      a.       two different parse trees of the same sentence.

      b.       two different meanings of the same sentence.

      c.       both.                d. neither.

 

11. Which makes the task of a scanner design easier and simpler?

     a.        when blanks are totally ignored.

     b.        when keywords are strictly reserved.

     c.        both.                                                                       d.   neither.

 

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

                a.             LL(1) Parsers.

                b.             Recursive Descent Parsers

                c.             both.                                       d.             neither.

 

 

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

                a.             a left recursive rule, not necessarily direct.

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

                c.             a non-terminal whose two  production rules have a Common Prefix.

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

 

 

14.           Which is true about a “Viable” Prefix?

a.                    it is about  rightmost sentential forms.

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.

 

A =  alpha  B               // alpha is a string of grammar symbols

B =   beta    A             // beta is a string of grammar symbols

15.           If a grammar has above two production rules,

a.                    Follow set of A and Follow set of B are the same.

b.                   Both non-terminals have left recursions.

c.                    Both.                                                      d.  neither.

 

Next 10 questions are about the following CFG where each character is a grammar symbol.

 

                S  ->  a  S  b                           // Rule-1

                S  ->  R  b                               // Rule-2

                R  ->  c  S  c                           // Rule-3

                R  ->  (    )                               // Rule-4

                R  ->  S  d  R                          // Rule-5

                R  ->  l                                    // Rule-6

 

 

16.           The OPR “<” applies to

                a.             a    c

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

 

17.           The OPR “>” applies to

                a.             b    b

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

 

18.           The OPR “=” applies to

                a.             (    )

                b.             a    b                                        c.             both.                                       d.             neither.

 

19.           The nonterminal S leftmost derives (in one or more steps)

                a.             a

                b.             c

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

 

20.           The nonterminal R leftmost derives (in one or more steps)

                a.             a

                b.             c

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

 

21.           Which is a NEXT pair?

                a.             c   a

                b.             b   c

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

 

22.           Which is a  S. F.?

                a.             S  d  R  b

                b.             S  d  (    )   b

                c.             R  b  d  R  b

 

23.           Which is a  R. S. F.?

                a.             S  d  R  b

                b.             S  d  (    )   b

                c.             R  b  d  R  b

 

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

                a.             rule-1

                b.             rule-5

                c.             rule-6

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

 

25.           The FOLLOW set of the nonterminal R includes, among others,

                a.             b

                b.             c

                c.             a

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

 

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

 

 

 

27.           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 as they are kind of underestimates.

                c.             Both.                                      d.             Neither.

 

28.           Leftmost derivation sequences are for

a.                    LL(1) parsers and Recursive Descent parsers.

b.                   Precedence-based parsers

c.                    Both.                                      d.             neither

 

29.           In general (that is, most of the times), the contents of a syntax stack used by LL(1)  parsers are

                a.             a suffix of the leftmost S.F.

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

                c.             both.                                       d.             neither. 

 

30.           Which computes   R+ nt       

                a.             R* nn     R nt       

                b.             R+ nn     R nt           

                c.             neither.

 

31.           Which is for the bottom-up parsers?

                a.             the rightmost derivation sequence.

                b.             the rightmost derivation sequence in reverse.

                c.             Both.                                                                      d.   neither.

 

32.           Which is a compiler design issue beyond the basic issues of source language and the target

language requirements?

a.                    number of passes.

b.                   Bootstrapping and error processing.

c.                    Subprogram handling.

d.                   All above.                                              e.   two above.

 

33.           Which is true of bootstrapping?

a.                    it is a shortcut in compiler design by taking advantage of  hardware architectures.

b.                   It enables us to avoid translating the intended source language at all.

c.                    Both.                                                      d.   neither.

 

34.           Which can represent a class of tokens?

a.                    context-free grammars

b.                   regular expressions

c.                    both.                                                       d.   neither.

 

35.           Which is a sub-task of a scanner?

a.                    memory allocation even when the exact memory size is not known.

b.                   symbol table creation and maintenance.

c.                    Both.                                                      d.   neither.

 

 

PART-B.               Other problems                                                                                                   (16 points)

 

Do two  problems in this PART-B.

 

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

                A   ->      A  +  B

                A   ->      B   a   B

                B   ->       (    D    )  

                B   ->       D   D              

                D   ->      D   b

                D   ->      a                                              // 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.          Calculate and clearly show the NEXT matrix for the grammar. It must be 5-5.

 

 

D.               What is the condition for LL(1) grammars???

 

 

E.                Describe some issues of complier design beyond the basic issues of source and target languages in no more than 12 lines.