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}
Example of intrinsic attributes??
ReplyDelete