ECS140A-Assignment 1 Solved

Description

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 a’s.

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