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?
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
the following grammar generates all regular expressions over the alphabet of letters (we have used quotes...
1. Write a BNF description of the logical expressions and the relational expressions in C++. Make sure that the BNF reflects the order of precedence of the operators, as well as, the associativity rules. 2. Using the BNF rules in 1., give a rightmost derivation and show a parse tree for the expression below. 3. Prove that the following grammar is ambiguous and rewrite the grammar to remove ambiguity «newexp> → «newexp> @ <newexp> ulvl w I <other> <other> →
3. Create a CFG describing regular expressions over the alphabet {0, 1}. You will need to quote the regular expression operators and the template given you has them quoted as terminals. We expect the grammar to generate the following syntactic constructions: • Union via "|", for example, 0 1 "|" 1 should be in the language generated by the grammar • Intersection via "&", for example, 0 1 "&" 1 should be in the language • Concatenation: any nonempty sequence...