ECS 140A:  Homework Assignment 1

ECS 140A: 
Homework Assignment 1

This assignment asks you to prepare written answers to questions on BNF and EBNF.
Please turn in your solutions as a PDF file via Canvas by the due date above. Make sure
your written work is very readable. We will not grade what we cannot read. This is not a
group project; do your own work.
1. (15 pts) Consider the following BNF grammar:
<S> ::= a <S> c <B> | <A> | b
<A> ::= c <A> | c
<B> ::= d | <A>
For each of the strings below, indicate whether or not the string can be derived from
the grammar ("yes" or "no"). If the string can be derived from the grammar, provide a
derivation.
(a) (5 pts) aabccd
(b) (5 pts) accbcc
(c) (5 pts) accccc
2. (20 pts) Convert the following BNF grammar into EBNF.
<integer> ::= <unsigned> | <sign> <unsigned>
<unsigned>::= <digits> | <unsigned><digits>
<digits> ::= <digits><digit> | <digit>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<sign> ::= + | -
3. (25 pts) What language is generated by each of the BNF grammars below (assuming
that <S> is the start symbol):
(a) (5 pts)
<S> ::= ab | a <S> b
(b) (10 pts)
<S> ::= <A> <B> <C>
<A> ::= a <A> | a
<B> ::= b <B> | b
<C> ::= c <C> | c
(c) (10 pts)
<S> ::= <x> | <y>
<x> ::= 0 <x> 1 | <x1>
<x1> ::= 0 <x1> | 0
<y> ::= 0 <y> 1 1 | <y1>
<y1> ::= <y1> 1 | 1
4. (20 pts) 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.

(a) (10 pts) This grammar is ambiguous. Give a string having two different parse trees
and draw the parse trees.
(b) (10 pts) If we adopt the disambiguating rule (used in most languages) “match each
else with the closest previous unmatched then,” write an equivalent, un-ambiguous
grammar.
5. (20 pts) Give a BNF and an EBNF for each of the languages below.
(a) (10 pts) The set of all strings consisting of zero or more a’s.
(b) (10 pts) The set of all strings consisting of one or more a’s, where there is a
comma in between each a and the following a. Note that there is no comma before the
first a or after the last a.