[SOLVED] CS Haskell module SyntaxPractice where

module SyntaxPractice where

* Practice Set 1

1. Determine whether each string can be generated by the grammar. If the
string can be generated, determine which syntactic category it belongs
to. For each problem, write either Expr, Stmt, or Prog to indicate its
syntactic category, or write syntax error if the string cannot be
generated.

a. Expr
b. syntax error
c. Stmt
d. Stmt
e. syntax error
f. Prog
g. syntax error
h. Prog
i. Stmt

2. Implement the grammar as a set of Haskell data types.

type Var = String

data Expr
= Lit Int
| Ref Var
| Add Expr Expr
deriving (Eq,Show)

data Stmt
= Set Var Expr
| Print Expr
deriving (Eq,Show)

type Prog = [Stmt]

3. For each string that can be produced by the grammar, write the
corresponding Haskell value using your data types.

ex1a :: Expr
ex1a = Add (Lit 2) (Ref x)

ex1b is a syntax error

ex1c :: Stmt
ex1c = Set x (Add (Lit 3) (Ref y))

ex1d :: Stmt
ex1d = Print (Add (Ref x) (Ref y))

ex1e is a syntax error

ex1f :: Prog
ex1f = [Print (Lit 2), Print (Lit 3)]

ex1g is a syntax error

ex1h :: Prog
ex1h = [Set x (Lit 2), Print (Lit 4)]

ex1i :: Stmt
ex1i = Set z (Add (Add (Lit 2) (Ref x)) (Ref y))
OR:
ex1i = Set z (Add (Lit 2) (Add (Ref x) (Ref y)))

* Practice Set 2

4. Determine whether each string can be generated by the grammar. If the
string can be generated, determine which non-terminal you must start
with in order to generate it. In each blank, write either A, B, or C
if the string can be generated, or write syntax error if it cannot
be generated.

a. A
b. B
c. syntax error
d. A
e. C
f. syntax error
g. B
h. syntax error
i. B
j. B

5. Implement the grammar as a set of Haskell data types.

data A = OAO A
| IBI B

data B = BBC B B C
| O

data C = CCC C C C
| I

Note that you can choose whatever names you like for the data constructors.
I chose them to look like the original rules, using O and I for 0 and 1.
To help see the relationship to the original grammar, it helps to see what
the corresponding pretty printers looks like. Recall that pretty printers
translate from abstract syntax to concrete syntax.

| Pretty printer for A.
prettyA :: A -> String
prettyA (OAO a) = 0 ++ prettyA a ++ 0
prettyA (IBI b) = 1 ++ prettyB b ++ 1

| Pretty printer for B.
prettyB :: B -> String
prettyB (BBC b1 b2 c) = prettyB b1 ++ prettyB b2 ++ prettyC c
prettyB O = 0

| Pretty printer for C.
prettyC :: C -> String
prettyC (CCC c1 c2 c3) = prettyC c1 ++ prettyC c2 ++ prettyC c3
prettyC I= 1

6. For each string that can be produced by the grammar:
(a) write the corresponding Haskell value
(b) draw the corresponding abstract syntax tree
(using the Haskell data constructors as nodes).

Note that these solutions are not necessarily unique!

|
>>> prettyA ex2a
101
ex2a :: A
ex2a = IBI O

|
>>> prettyB ex2b
00111
ex2b :: B
ex2b = BBC O O (CCC I I I)

ex2c is a syntax error

|
>>> prettyA ex2d
0100110
ex2d :: A
ex2d = OAO (IBI (BBC O O I))

|
>>> prettyC ex2e
11111
ex2e :: C
ex2e = CCC (CCC I I I) I I

ex2f is a syntax error

|
>>> prettyB ex2g
0010111
ex2g :: B
ex2g = BBC (BBC O O I) O (CCC I I I)

ex2h is a syntax error

|
>>> prettyB ex2i
0000111
ex2i :: B
ex2i = BBC O (BBC O (BBC O O I) I) I

|
>>> prettyB ex2j
0011101
ex2j :: B
ex2j = BBC (BBC O O (CCC I I I)) O I