· You have until the start of class on 24 June to hand in this extended quiz.
·
To be accepted the answers to the questions must be
typed.
· No late submissions will be accepted.
· If any outside sources are used they must be cited. Each question is weighted equally.
· You must work individually on this test.
o Failure to do so will result in a grade of zero for the test !
o No collaboration of any kind is permitted.
1. If possible using only the algorithm I showed you in class, remove the left recursion from the following grammar, if its not possible, explain why you cannot remove the left recursion. (Note: Any symbol not on the left hand side of any production is a terminal symbol)
<c> -> <q> *
<c> | <c>
@ <q> | d
<c>
<q> -> <q>
& <f> |
<q> # <f>
| <f>
<f> - > a | b | d
| <c>
2. Rewrite the following grammar expressed in EBNF to be in BNF
<g> ->
[ l ] { a { b c } b } <m>
<l> ->
z { z }
<m> -> x [ y ] z
3. If possible using only the algorithm I showed you in class, remove the left recursion from the following grammar, if its not possible, explain why you cannot remove the left recursion. (Note: Any symbol not on the left hand side of any production is a terminal symbol)
<z> ->
<y> %
<x> | <z>
( <y> ) | a <z>
<x> -> <z>
* <x> |
<x> / <y> | <w>
<w> -> e | f | g
4. Prove that the following grammar is ambiguous
A-> A # A | A ^ A | L | { A }
Where L is a token with lexemes a, b c.
5. Rewrite the grammar in Problem 4, if possible to remove the ambiguity.
6. Given the following BNF:
<exp>
-> { <list> } | (
<list> ) | [ <list> ] |
<char>
<list>
-> <list> , <exp> | <exp>
<char>
-> a | b | c | d | e
Show
the parse tree (if possible) for
( ( [ a , b, { c } ] , e ) c, { b } )
7. Give the EBNF specification for the language L that is made up of the chars a,b and c such that sentences in the language have the form
L : sqsR
where
· s is a string of any combination of the characters a and b
· sR is just that same string s reversed
· q is an odd number of c's followed by either an even number of b's or an even number of as.
8. Translate the following grammar expressed in EBNF into BNF
<goal>
-> { a b [ <bar> ]
} [<foo>] (<bar> | <baz>)
<bar> -> b [ e ] f
<foo> -> d { d e}
<baz> -> g { g }
9. Create the first/follow
tables for the following grammar:
G -> S S -> ( L ) | ML -> L , S | SM -> a | b
10. Generate the parse table for the grammar in Problem 9.
11.
Show the actions of the parser for the grammar in Problem 9 on the following
string :
((a), (a))
12. Explain
why a grammar must be left factored for a predictive parser to work.
13. Consider
the following grammar:
E -> E
* F | E / F
| F
Whats the value of the following expression given
that Number is any double precision number and that * denotes
multiplication, / denotes division, + denotes addition and - denotes
subtraction. 4.5 + 5.6 * 2.0 3.4 /
2.0 14.