Homework Assignment 1 Solution

Description

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.

1. (5 pts) aabccd

2. (5 pts) accbcc

3. (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.


1. 1. (10 pts) This grammar is ambiguous. Give a string having two different parse trees and draw the parse trees.

1. 2. (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.

5. 1. (10 pts) The set of all strings consisting of zero or more a’s.

5. 2. (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.