| |
1.a) A ==> a A c ==> a a A c c ==> a a b c c
A ==> a A c ==> a b c
A ==> b
The sentences consist of one 'b' preceded by an number n >= 0 of 'a's and
followed by the same number n of 'c's,
or {anbcn: n >= 0}.
b) O ==> a E ==> a a O ==> a a a
O ==> a
O ==> a E ==> a a O ==> a a a E ==> a a a a O ==> a a a a a
There will always be an odd number ( >= 1) of 'a's,
or {an: n >= 1, n odd}.
("E" stands for "even" and "O" stands for "odd".)
c) L ==> L A ==> L A A ==> A A A ==> a A A ==> a a A ==> a a a
L ==> A ==> a
L ==> L A ==> A A ==> a A ==> a a
Any number n >= 1 of 'a's,
or {an: n >= 1}.
d) N ==> ( C ) ==> ( C , A ) ==> ( C , A , A ) ==> ( C , A , A , A ) ==>
( A , A , A , A ) ==> ( a , A , A , A ) == > ( a , b , A , A ) ==>
( a , b , c , A ) ==> ( a , b, c , d )
N ==> ( C ) ==> ( A ) ==> ( a )
n ==> ( C ) ==> ( C , A ) ==> ( A , A ) ==> ( a , A ) ==> ( a , c )
There will always be at least one 'a' 'b' 'c' or 'd' inside of a set of
parenthesis and if more than one, they are separated by commas.
e) S ==> A B ==> a A B ==> a a B ==> a a b B c ==> a a b b c c
S ==> A B ==> a B ==> a b c
S ==> A B ==> a B ==> a b B c ==> a b b c c
Any number n >= 1 of 'a's followed by any number m >= 1 of 'b's, and
the same number m of 'c's,
or {anbmcm: n >= 1, m >= 1}.
2.a) E ==> E * E ==> a * E ==> a * ( E ) ==> a * ( E + E ) ==> a * ( b + E )
==> a * ( b + c )
E
/|\
E * E
/ /|\
a ( E )
/|\
E + E
| |
b c
b) E ==> E + E ==> E * E + E ==> a * E + E ==> a * b + E ==> a * b + c
E ==> E * E ==> a * E ==> a * E + E ==> a * b + E ==> a * b + c
E E
/|\ /|\
E + E E * E
/|\ \ / /|\
E * E c a E + E
| | | |
a b b c
3.a) E ==> E + T ==> E + T + T ==> T + T + T ==> F + T + T ==> a + T + T ==>
a + F + T ==> a + b + T ==> a + b + F ==> a + b + c
E
/|\
E + T
/|\ \
E + T F
/ \ \
T F c
| |
F b
|
a
b) E ==> E + T ==> T + T ==> T * F + T ==> F * F + T ==> a * F + T ==> a * b + T
==> a * b + T * F ==> a * b + F * F ==> a * b + c * F ==> a * b + c * d
E
/|\
E + T
/ /|\
T T * F
/|\ | |
T * F F d
| | |
F b c
|
a
4.a) Terminals: = + - * / ^ ( ) a b c d
Non-Terminals: A E T S F L
Metasymbols: --> |
b.i) A ==> L = E ==> d = E ==> d = T ==> d = S ==> d = F ^ S ==> d = L ^ S ==>
d = a ^ S ==> d = a ^ F ^ S ==> d = a ^ L ^ S ==> d = a ^ b ^ S ==>
d = a ^ b ^ F ==> d = a ^ b ^ L ==> d = a ^ b ^ c
A
/|\
L = E
/ |
d T
|
S
/|\
F ^ S
/ /|\
L F ^ S
/ | |
a L F
| |
b L
|
c
b.ii) A ==> L = E ==> d = E ==> d = E + T ==> d = T + T ==> d = S + T ==>
d = F + T ==> d = L + T ==> d = a + T ==> d = a + T * S ==> d = a + S * S
==> d = a + F * S ==> d = a + L * S ==> d = a + b * S ==>
d = a + b * F ^ S ==> d = a + b * L ^ S ==> d = a + b * c ^ S ==>
d = a + b * c ^ F ==> d = a + b * c ^ L ==> d = a + b * c ^ d
A
/|\
L = E
/ /|\
d E + T
/ /|\
T T * S
| | /|\
S S F ^ S
| | | |
F F L F
| | | |
L L c L
| | |
a b d
c) The first tree shows that ^ associates from right to left, that is,
that a^b^c = a^(b*c). The other 4 ops associate from left to right.
The second tree shows that ^ has higher precedence (is carried out
earlier) that any of the other 4 operators.
5.a) <double> ==> <digit-list> <decimal part> <exp> ==>
<digit> <decimal part> <exp> ==> 2 <decimal part> <exp> ==>
2. <digit-list> <exp> ==> 2. <digit> <digit-list> <exp> ==>
2.4 <digit-list> <exp> ==> 2.4 <digit> <exp> ==> 2.45 <exp> ==>
2.45E <sign> <digit-list> ==> 2.45E- <digit-list> ==> 2.45E- <digit>
==> 2.45E-3
<double>
|
+---------------+--------------+----------+
| | |
<digit-list> <decimal part> <exp>
| | |
<digit> +----+--+ +----+----+-----+
| | | | | |
2 . <digit-list> E <sign> <digit-list>
| | |
+-------+--+ - <digit>
| | |
<digit> <digit-list> 3
| |
4 <digit>
|
5
6.a) (Following Mr. Watson's lead, I'm leaving off <> from <id> and <const>.)
<stat> ==>
<if_stat> ==>
if ( <exp> ) <stat> ==>
if ( id ) <stat> ==>
if ( id ) <cmpd_stat> ==>
if ( id ) { <stat_list> } ==>
if ( id ) { <stat> } ==>
if ( id ) { <iter_stat> } ==>
if ( id ) { while ( <exp> ) <stat> } ==>
if ( id ) { while ( id ) <stat> } ==>
if ( id ) { while ( id ) <assgn_stat> } ==>
if ( id ) { while ( id ) id = <exp> ; } ==>
if ( id ) { while ( id ) id = <exp> <op> <exp> ; } ==>
if ( id ) { while ( id ) id = id <op> <exp> ; } ==>
if ( id ) { while ( id ) id = id + <exp> ; } ==>
if ( id ) { while ( id ) id = id + const ; }
<stat>
|
<if_stat>
|
+---+---+---+-----+
| | | | |
if ( <exp> ) <stat>
| |
id <cmpd_stat>
|
+------+------+
| | |
{ <stat_list> }
|
<stat>
|
<iter_stat>
|
+----+---+---+---+
| | | | |
while ( <exp> ) <stat>
| |
id <assgn_stat>
|
+--+--+-+---+
| | | |
id = <exp> ;
|
+------+-------+
| | |
<exp> <op> <exp>
| | |
id + const
b) (Note that the original version of this problem was erroneous and could
not be derived using the given grammar. Some students faked it somehow
to make it work out, and I said that if their answer was close I would
accept it. The answer below is to the second corrected version.
Again, I'm leaving off <> from <id> and <const>.)
<stat> ==> <iter_stat> ==>
while ( <exp> ) <stat> ==>
while ( <exp> <op> <exp> ) <stat> ==>
while ( const <op> <exp> ) <stat> ==>
while ( const - <exp> ) <stat> ==>
while ( const - id ) <stat> ==>
while ( const - id ) <cmpd_stat> ==>
while ( const - id ) { <stat_list> } ==>
while ( const - id ) { <stat_list> <stat> } ==>
while ( const - id ) { <stat> <stat> } ==>
while ( const - id ) { <if_stat> <stat> } ==>
while ( const - id ) { if ( <exp> ) <stat> <stat> } ==>
while ( const - id ) { if ( id ) <stat> <stat> } ==>
while ( const - id ) { if ( id ) <assgn_stat> <stat> } ==>
while ( const - id ) { if ( id ) id = <exp> ; <stat> } ==>
while ( const - id ) { if ( id ) id = <exp> <op> <exp> ;<stat> } ==>
while ( const - id ) { if ( id ) id = id <op> <exp> ; <stat> } ==>
while ( const - id ) { if ( id ) id = id * <exp> ; <stat> } ==>
while ( const - id ) { if ( id ) id = id * <exp> ; <stat> } ==>
while ( const - id ) { if ( id ) id = id * const ; <stat> } ==>
while ( const - id ) { if ( id ) id = id * const ; <cmpd_stat> } ==>
while ( const - id ) { if ( id ) id = id * const ; { <stat_list> } } ==>
while ( const - id ) { if ( id ) id = id * const ; { <stat_list> <stat> } } ==>
while ( const - id ) { if ( id ) id = id * const ; { <stat> <stat> } } ==>
while ( const - id ) { if ( id ) id = id * const ; { <assgn_stat> <stat> } } ==>
while ( const - id ) { if ( id ) id = id * const ; { id = <exp> ; <stat> } } ==>
while ( const - id ) { if ( id ) id = id * const ; { id = const ; <assgn_stat> } } ==>
while ( const - id ) { if ( id ) id = id * const ; { id = const ; id = <exp> ; } } ==>
while ( const - id ) { if ( id ) id = id * const ; { id = const ; id = id ; } }
<stat>
|
<iter_stat>
|
+------+----+---------+------+
| | | | |
while ( <exp> ) <stat>
| |
+-------+----+ <cmpd_stat>
| | | |
<exp> <op> <exp> +-----+-----------------+----+
| | | | | | |
const - id { <stat_list> <stat> }
| |
<stat> <cmpd_stat>
| |
+-+---+---+---+ +----+--------+
| | | | | | | |
if ( <exp> ) <stat> { <stat_list> }
| | |
id <assgn_stat> +---------------+
| | |
+--+----+---+ <stat_list> <stat>
| | | | | |
id = <exp> ; <stat> <assgn_stat>
| | |
<exp> <op> <exp> <assgn_stat> +--+----+---+
| | | | | | | |
id * const +--+----+---+ id = <exp> ;
| | | | |
id = <exp> ; const
|
const
7.a) while ( id ) while ( id ) id = id + id; Is a legal sentence.
b) No, there is no ambiguity here. (Note: This statement may be
complex and confusing, in need of extra brackets, but that is
not at all the same as ambiguous, where there are two possible parse trees.
8.a) Original statement to work with:
if ((k >= 0) && (k < TABLE_SIZE)) {
if (table[k] >= 0)
printf("Entry %d is %d\n", k, table[k]);
else printf("Error: entry %d is negative.\n", k);
}
else printf("Error: index %d out of range.\n", k);
Answer to 8a:Statement with three added {} in red:
if ((k >= 0) && (k < TABLE_SIZE)) {
if (table[k] >= 0) {
printf("Entry %d is %d\n", k, table[k]);
}
else {
printf("Error: entry %d is negative.\n", k);
}
}
else {
printf("Error: index %d out of range.\n", k);
} |
b) If an if or an else has only one non-compound statement as its target
("non-compound" meaning not an if or an if-else or a while, or a
block of statements, etc.), it can be written without brackets but its
statement should be written on the same line as the if or else is.
Following this rule, I should have written the original statement as:
if ((k >= 0) && (k < TABLE_SIZE)) {
if (table[k] >= 0) printf("Entry %d is %d\n", k, table[k]);
else printf("Error: entry %d is negative.\n", k);
}
else printf("Error: index %d out of range.\n", k);
|