[Solved] ECS140A-Assignment 1

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

• aabccd
• accbcc
• accccc

2. 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. What language is generated by each of the BNF grammars below (assuming that <S> is the start symbol):

<S> ::= ab | a <S> b

<S> ::= <A> <B> <C>

<A> ::= a <A> | a

<B> ::= b <B> | b

<C> ::= c <C> | c

<S> ::= <x> | <y>

<x> ::= 0 <x> 1 | <x1>

<x1> ::= 0 <x1> | 0

<y> ::= 0 <y> 1 1 | <y1>

<y1> ::= <y1> 1 | 1

4. 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.

• This grammar is ambiguous. Give a string having two different parse trees and draw the parse trees.

• 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. Give a BNF and an EBNF for each of the languages below.

• The set of all strings consisting of zero or more as.

• The set of all strings consisting of one or more as, 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.