Out: 9/14, due by 11:59pm 9/20 (Wed.)

Describing Syntax

You should prepare your assignment electronically as a single pdf file and submit it as hw2.pdf using the submit system. If you do not have easy access to a docment preparation system that can produce pdf output you might try the free web-based google docs applications.

(1) Recognizing simple languages (30 points)

For each of the following grammars, briefly describe the language it defines in a sentence or two. Assume that the start symbol is S for each and that any symbol found only on the right hand side of a production is a terminal symbol. We've done the first one for you as an example. Hint: if it's not obvious by inspection, try writing down sentences in the language until you can see the patterns emerging. If it is obvious by inspection, write down some sentences generated by the grammar to verify that they match your expectations and fit your english description. Please be as precise as possible in describing the language.

(example) 0 points.

S -> a S a
S -> b

Answer: This grammar defines the language consisting of strings N a's (where N >= 0) followed by one b followed by N a's

(1a) 10 points.

S -> Q a
Q -> b S
Q -> c

(1b) 10 points.

S -> A B C
A -> a
A -> Aa
B -> bB
B -> bc
C -> cCc
C -> cc

(1c) 10 points.

S -> A B C D
A -> a | aA
B -> Bb | b
C -> bC
C -> b
D -> a
D -> aD

(2) Derivation and parse tree (55 points)

prog -> assign | expr

assign -> id = expr

expr -> expr + term | expr - term | term

term -> factor | factor * term

factor -> ( expr )

factor -> id | num

id -> A | B | C

num -> 0 | 1 | 2 | 3

The questions in this section are based on the grammar given in the colored box at right

(a) what is the associativity of the * operator? (5 points)

(b) What is the associativity of the + operator? (5 points)

(c) For the * and + operators, do they have the same precedence, does the * operator have greater precedence than +, or does + have greater precedence than * ? (5 points)

(d) Using this grammar show a leftmost derivation and a parse tree for the strings in d.1 and d.2. (20 points)
Show the parse tree as either a graphical tree or a text-based "indented tree".
We've done the first one for you as an example of the desired output format.

(d.0) 1 + 2

prog => expr
=> expr + term
=> term + term
=> factor + term
=> 1 + term
=> 1 + factor
=> 1 + 2
        prog
        ..expr
        ....expr
        ......term
        ........factor
        ..........1
        ....+
        ....term
        ......factor
        ........2
	
OR:

(d.1) A * 3 - B

(d.2) C = (1 + A) * B

(e) Modify the grammar to add two new operators as follows. (20 points)

A unary minus operator (-) that has precedence higher than any of *, +, or binary minus.
A binary exponentiation operator (**) that has precedence higher than unary minus and is right associative.

For example, the string "1 - 4 * - 3 ** - 2" would be interpreted as 1 - (4 * (-(3 ** (-2)))) which would evaluate to 1.44444444...

(3) EBNF to BNF (15 points)

The following EBNF grammar defines a language of signed decimal numbers. In this notation, inline alternatives can be delimited by parentheses and separated by vertical bars, optional elements are in square brackets and a sequence in curly braces can be repeated any number of times or, if immediately followed by a + symbol, one or more times.

S -> [(-|+)] {D}+ [ . {D}+ ] 

D -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Give a regular BNF grammar for this language, i.e., one that does not use the extra notation for inline alternatives, optional elements, or repetitions.