the following grammar generates all regular expressions over

the following grammar generates all regular expressions over the alphabet of letters (we have used quotes to surround operators, since the vertical bar is an operator as well as a metasymbol):

rexp->rexp “|” rexp

| rexp rexp

| rexp “*”

| “(” rexp “)”

| letter

a. give a derivation for the regular expression (ab|b)* using this grammar.

b. show this grammar is ambiguous

c. Rewrite this grammar to establish the correct precendences for the operators.

d. What associativity does your answer in part (c) give to the binary operators? Why?

Solution

rexp--> rexp*

--> (rexp)*

-->(rexp | rexp)*

-->(rexp rexp | b)*

--> (ab | b)*

b) this grammar is ambiguous because it generates 2 different parse trees for the expression ab|c

c)

rexp--> rexp” |” rterm | rterm

rterm--> rterm rend | rend

rend--> rend “*” | (rexp) | letter

d) left associativity because a series of operators with same precedence will be evaluated from left to right