Language BNF. Answer this question by editing hw10.txt. Here is a simple grammar:

A ::= A A + | A A * | b

The terminal symbols are +, *, and b. A is the only non-terminal symbol. All the productions for A are shown on one line to save space.

a. (Y/N) Can the string "bb+" be generated from this grammar?

b. (Y/N) Can the string "bb**" be generated?

c. (Y/N) Can the string "bb*b+" be generated?

d. (Y/N) In any string generated from the grammar, is it true that the number of b's will be greater than the number of + and * symbols combined?

Here's a slightly-more complicated grammar:

A ::= 0 B | 1 C | "" ( "" means the empty string)

B ::= 0 A | 1 C

C ::= 0 A | 1 B

A, B, and C are non-terminals (obviously), and 0 and 1 are terminals. A is the start symbol. The empty string isn't a terminal symbol -- it is a string containing no terminals or non-terminals.

e. (Y/N) Can the string "111" be generated?

f. (Y/N) Can the string "001" be generated from this grammar?

g. (Y/N) Can the string "010" be generated?

Let's try a grammar related to programming languages.

func-def ::= function id ( id-list ) { stmts }

stmts ::= stmts stmt | stmt

stmt ::= print expr | id ( expr ) | id = expr | return expr

id-list ::= "" | id id-list1

id-list1 ::= "" | , id id-list1

expr ::= id | num | expr + expr | id ( expr )

It should be clear which symbols are terminals and non-terminals. Non-terminal func-def is the start symbol.

h. (Y/N) Can the following function definition be generated from this grammar?

function bar() {

print 5

}

i. (Y/N) Can the following function definition be generated?

function baz(x,y) {

z = foo(x,y)

return z

}

j. (Y/N) Can the following function definition be generated?

function g(x,y) {

baz(x)

print y

}