This assignment asks you to prepare written answers to questions on BNF, EBNF, and Syntax Diagrams. Each of the questions has a short answer — no essays, please! You may discuss this assignment with other students and work on the problems together. However, your write-up should be your own individual work. Please turn in your solutions electronically via Canvas by the due date.
1. (15pts) Consider the following BNF grammar:
A::=[B,A]|B
B::=C|(A;C)
C::={C}|D
D ::= a | b | c
Note that in this grammar, [, ], ,, ;, (, ), f, g, a, b, and c are terminals, whereas A, B, C, and D are non-terminals. For each of the strings listed below, indicate all the non-terminals that can generate it (if there is none, write down “none”):
(5pts) [c,(b;a)]
(5pts) ([(a;b),c];a)
(5pts) [(a;c),[(b;[a,c]),b]]
(20pts) Given the following BNF:
<integer ::= <unsigned | <sign <unsigned <unsigned::= <digits | <unsigned<digits <digits ::= <digits<digit | <digit <digit ::= 0 | 1 | ... | 9 <sign ::= + | -
(10pts) Convert the grammar into EBNF.
(10pts) Show the syntax diagram of the above EBNF.
(25pts) What language is generated by each of the BNF grammars below (assuming that <s is the start symbol):
(5pts)
<s ::= 0 <s 1 1 1 1 | empty
(b) (10pts)
<s ::= <x | <y | empty
<x ::= 1 <x 0 0 | empty
<y ::= 0 <y 1 | empty
1
(c) (10pts)
<s ::= <x | <y
<x ::= 0 <x 1 | <x1
<x1 ::= 0 <x1 | 0
<y ::= 0 <y 1 1 | <y1
<y1 ::= <y1 1 | 1
4. (20pts) Given the following grammar:
<stmt ::= if <expr then <stmt
if <expr then <stmt else <stmt
other
<expr ::= true | false
where other is a terminal that stands for any other kinds of statements.
(10pts) This grammar is ambiguous. Give a string having two different parse trees and draw the parse trees.
(10pts) If we adopt the disambiguating rule (used in most languages) “match each else with the closest previous unmatched then,” write an equivalent, unambiguous grammar.
(10pts) Given the following grammar:
<S ::= if <E then <S else <S
{ <S <D
print <E
<D ::= } | ; <S <D
<E ::= 0
Show the parse tree for the following string:
if 0 then { if 0 then print 0 else print 0 ; print 0 } else { print 0 }
(20pts) In a grammar, a grammar symbol X is useless if X can never appear in a derivation of a string.
(15pts) Write an algorithm for eliminating all productions containing useless symbols from a given grammar.
(5pts) Apply your algorithm to the following grammar:
<S ::= 0 | <A | <C
<A ::= <A <B
<B ::= 1
<C ::= 2
where <S is the start symbol.
2
