Homework #2 - Individual
Due Date: February 7th
Points: 55

1.(30 points) Construct a grammar for while statements of each of the following languages:
JavaScript
C++
Prolog
Lisp
COBOL
Eiffel

Prolog is a logic language and does not have a while statement, however it is possible to emulate it if needed.

 <WhileStmt> ::= while (<Expr>) <statements>

http://www.javascript.com/

 <WhileStmt> ::= while ( <Expr> ) <statements>

In order to keep language simple Eiffel provides single loop construct

http://cs.anu.edu.au/student/eiffel/SyntaxGram/index.html#Features

Loop

    Initialization

        [Invariant]

        [Variant]

        Loop_body

    End

LISP has a general iteration macro loop which is defined in the standard:

http://www.xanalys.com/software_tools/reference/HyperSpec/Body/mac_loop.html

The ``simple'' loop form:

loop compound-form* => result*

The ``extended'' loop form:

loop [name-clause] {variable-clause}* {main-clause}* => result*

Macro while is not standard but could be defined as:

http://www.paulgraham.com/lib/onlisp.lisp

(defmacro while (test &body body) 

    `(do () 

             ((not ,test)) 

         ,@body))

Cobol uses PERFORM statement for tasks similar to while :

http://cis01.bloomu.edu/courses/92252/html/cobol/perform.html

PERFORM [ procedure-name-1 [ { THROUGH or THRU } procedure-name-2 ] ] [ imperative-statement-1 END-PERFORM ]

2. (10 points) Given the following English language grammar for constructing sentences:

<sentence>::<subject><verb><object>.

Introduce a new start symbol <paragraph> that will allow you to generate any number of sentences. Show how the grammar has to be modified to accomplish this.

<paragraph>::<sentence>|<paragraph><sentence>

                    <sentence>::<subject><verb><object>

3.(15 points) Give a BNF definition (do not use EBNF) of a language of balanced parentheses. The only two tokens in the language are ( and ). For example, ()() and ((()))()((()())) are in this language, while (((() is not.

1. S->()

2. S->(S)

3. S->S(S)

4. S->S()

Examples:

Rule     Result                            Rule        Result

3        S(S)                                 4            S()        

4        S()(S)                               1            ()()

2        (S)()(S)

2        ((S))()(S)

1        ((()))()(S)

2        ((()))()((S))

4        ((()))()((S()))

1        ((()))()((()()))

Write to Your Representative