[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