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