It's not due until Monday but, from my page stats, it's obvious nobody's copying from here. Here's my first assignment for my languages course. The parse tree diagrams don't show up and I'm not really feeling like solving that problem right now.
CS4250: Programming Languages
HW#1
Eric Buckley
3) Rewrite the BNF of Example 3.4 to give + precedence over
* and force + to be right associative.
Original BNF from 3.4:
<assign> -> <id> =
<expr>
<id> -> A | B | C
<expr> -> <expr> +
<term> | <term>
<term> -> <term> *
<factor> | <factor>
<factor> -> (<expr>)
| <id>
Switching the operators for <expr> and <term>
gives + precedence over *. To make + right associative, me make sure the parse
tree expands from the right rather than the left for <term>. Thus, the
new BNF is:
<assign> -> <id> =
<expr>
<id> -> A | B | C
<expr> -> <expr> *
<term> | <term>
<term> -> < factor >
+ <term> | <factor>
<factor> -> (<expr>)
| <id>
6) Using the grammar in Example 3.2, show a parse tree and a
leftmost derivation of A=A*(B+(C*A))
BNF 3.2:
<assign> -> <id> =
<expr>
<id> -> A | B | C
<expr> -> <id> +
<expr> | <id> * <expr> | (<expr>) | <id>
Left derivation:
<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> * <expr>))
=>
A = A * (B + (C * <expr>))
=>
A = A * (B + (C * <id>))
=>
A = A * (B + (C * A))
Parse tree:
7. Using the grammar in Example 3.4, show a parse three and
a leftmost derivation for A=(A+B)*C
(See #3 for BNF)
Left derivation:
<assign> => <id> =
<expr>
=>
A = <expr>
=>
A = <term>
=>
A = <term> * <factor>
=>
A = <factor> * <factor>
=>
A = (<expr>) * <factor>
=>
A = (<expr> + <term>) * <factor>
=>
A = (<term> + <term>) * <factor>
=>
A = (<factor> + <term>) * <factor>
=>
A = (<id> + <term>) * <factor>
=>
A = (A + <term>) * <factor>
=>
A = (A + <factor>) * <factor>
=>
A = (A + <id>) * <factor>
=>
A = (A + B) * <factor>
=>
A = (A + B) * <id>
=>
A = (A + B) * C
7 (cont.) Parse Tree:
8) Prove the following grammar I ambiguous:
<S> -> <A>
<A> -> <A> +
<A> | <id>
<id> -> a | b | c
The ambiguity comes from the fact that association can parse
either left or right. The following two trees are both valid parsing of a + b +
c:
11) Consider the grammar:
<S> -> <A> a
<B> b
<A> -> <A> b | b
<B> -> a <B> | a
a) baab is valid (S => <A> a <B> b => baab
b) bbbab is not valid because the first and third rule imply
that there must always be a double “a” in the string (<S> includes “a
<B>” and <B> must always start with “a”).
c) bbaaaaaS is not valid because the character “S” is not in
any expansion.
d) bbaab is valid (S=> <A> a <B> b => <A>
ba <B> b => bbaab)
13. Grammar for strings of the form n “a” followed by n “b”
where n>0.
<S> -> ab | <A>
<A> -> ab | a<A>b
14. Parse trees for the above grammar for aabb and aaaabbbb.
16. Convert the BNF from Example 3.3 to EBNF:
BNF 3.3:
<assign> -> <id> =
<expr>
<id> = A | B | C
<expr> -> <expr> +
<expr> | <expr> * <expr> | (<expr>) | <id>
EBNF:
<assign>
-> <id> = <expr>
<id>
= A | B | C
<expr>
-> <expr> ( + | * ) <expr> | (<expr>) | <id>
17. Convert the following EBNF to BNF:
<S> -> <A> {b
<A>}
<A> -> a [b] <A>
BNF:
<S> -> <A>
<A> -> <A> b
<A> | <B>
<B> -> a <B> | ab
<B>
18. An Intrinsic
Attribute is an attribute of a leaf node on the parse tree whose value
comes from outside the parse tree (e.g., the type of a variable which is
typically stored in the symbol table during compilation). Intrinsic variables
are then passed to semantic functions for the leaf node to produce
non-intrinsic Synthetic Attributes
which are passed to the parent node, which in turn uses them as inputs for its
semantic functions.
23. Compute the weakest precondition {P} for each statement
and postcondition:
a) {P} a = 2
* (b – 1) – 1 {a > 0}
{P}
= {2 * (b – 1) – 1 > 0}
=
{2b > 3}
= {b > 3/2}
b) {P} b =
(c + 10) / 3 {b > 6}
{P} = {(c + 10) / 3 > 6}
=
{c + 10 > 18}
=
{c > 8}
c) {P} a = a
+ 2 * b – 1 {a > 1}
{P} = {a + 2 * b – 1 > 1}
=
{a + 2 * b > 2}
=
{b > (2 – a) / 2}
d) {P} x = 2
* y + x – 1 {x > 11}
{P} = {2 * y + x – 1 > 11}
=
{2 * y + x > 12}
=
{y > (12 – x)/2}
24. Compute the weakest precondition for each of the
following sequences of assignment statements and postconditions:
a) {P} a = 2
* b + 1; b = a – 3; {b < 0}
{P} a =
2 * b + 1 {P1}, {P1} b = a – 3; {b < 0}
{P1} = {a – 3 < 0}
=
{a < 3}
=> {P} =
{2 * b + 1 < 3}
=
{b < 1}
b) {P} a = 3
* (2 * b + a); b = 2 * a – 1 {b > 5}
{P} a =
3 * (2 * b + a) {P1}, {P1} b = 2 * a – 1 {b > 5}
{P1} = {2 * a – 1 > 5}
=
{a > 3}
=> {P} =
{3 * (2 * b + a) > 3}
=
{2 * b + a > 1}
=
{b > (1 – a) / 2}
