Q6 : Using the grammar
in Example 3.2, show a parse tree and a leftmost derivation for each of the following
statements:
a.
A = A * (B + (C * A))
b.
B = C * (A * C + B)
c.
A = A * (B + (C))
A
:
a. A
= A + (B + (C * A))
= > A = <expr>
= > A =
<id> + <expr>
= > A =
A + <expr>
= > A =
A + ( <expr> )
= > A =
A + ( <id> + <expr> )
= > A =
A + ( B + <expr> )
= > A =
A + ( B + ( <expr> ) )
= > A =
A + ( B + ( <id> * <expr> ) )
= > A =
A + ( B + ( C * <expr> ) )
= > A =
A + ( B + ( C * <id> ) )
= > A =
A + ( B + ( C * A ) )
b. B
= C * (A * C + B)
<
assign > = > <id> = <expr>
=
> B = <expr>
= > B =
<id> + <expr>
=
> B = C + <expr>
= > B =
C + ( <expr> )
=
> B = C + ( <id> + <expr> )
=
> B = C + ( A * <expr> )
= > B =
C + ( A * <id> + <expr> )
= > B =
C + ( A * C + <expr> )
= > B =
C + ( A * C + <id> )
= > B =
C + ( A * C + B )
c. A
= A * (B + (C))
<
assign > = > <id> = <expr>
=
> A = <expr>
=
> A = <id> + <expr>
=
> A = A * <expr>
=
> A = A * (<expr> )
=
> A = A * ( <id> + <expr> )
=
> A = A * ( B + <expr> )
=
> A = A * ( B + ( <expr> ) )
= > A =
A * ( B + ( <id> ) )
=
> A = A * ( B + ( C ) )
Q7 : Using the grammar in Example 3.4, show a
parse tree and a leftmost derivation
for each of the following statements:
a.
A = ( A + B ) * C
b.
A = B + C + A
c.
A = A * (B + C)
d.
A = B * (C * (A + B))
A
: word “4020hw1”
Q8 :
Prove that the following grammar is ambiguous:
<S>
→ <A>
<A>
→ <A> + <A> | <id>
<id>
→ a | b | c
A : A grammar is ambiguous if the same string has 2 different parse trees. Here are two distinct parse trees for a + b + c .
S S
| |
A A
/ | \ / | \
A + A A + A
| / | \ / | \ |
<id> A + A A + A <id>
| | | | | |
a <id> <id> <id> <id> c
| | | |
b c a b
Q9 : Modify the
grammar of Example 3.4 to add a unary minus operator that has higher precedence than either + or
*.
A
: <assign>
-> <id> = <expr>
<id>
-> A | B | C
<expr>
-> <expr> + <term>
|
<term>
<term>
-> <term> * <factor>
|
<factor>
<factor>
-> ( <expr> )
|
+<id> | -<id>
Q10 : Describe, in
English, the language defined by the following grammar:
<S>
→ <A> <B> <C>
<A>
→ a <A> | a
<B>
→ b <B> | b
<C>
→ c <C> | c
A
: The LHS non-terminal S is defined as non-terminal A and
non-terminal B and non-terminal C, where non-terminal A can be one or more a’s
or one a, where non-terminal B can be one or more b’s or one b, and where
non-terminal C can be one or more c’s or one c.
No comments:
Post a Comment