CSCE 314 Lecture 13

« previous | Monday, September 26, 2011 | next »

Grammar Hierarchy

Regular Grammars

Production rules of the form:

<A> ::= a<B>
<A> ::= a

where a is a terminal character and only one non-terminal character allowed on the right.

Regular grammars are useful for lexing (generating tokens by grouping characters; char-by-char)

Example Regular Grammar

<S> ::= a<A>
<A> ::= b<A>
<A> ::= c<A>
<A> ::= a

produces the words described by /^a[bc]*a$/

Note: any language with the sequence $\{a^{n}b^{n}|n\geq 1\}$ is not a regular language. For example: matching parentheses.

Data Types

3 constructs for data types:

data ("algebraic" and "from scratch" describing constructors)
type (synonym for C's typedef)
newtype (restricted form of data for wrapping)

Data

data Bool = False | True

Constructor values are False and True

Constructors can be matched as patterns (also called destructing)

Person = Person Name Gender Age
type Name = Sttring
data Gender = Male | Female
type Age = Int

-- example usage
let x = Person "Matthew" Male 19

-- destructor/pattern matching examples
name (Person n _ _) = n

findPrsn n (p@(Person n _ _):ps) | n == m = p
| otherwise = findPrsn n ps

> findPrsn "Hermione" [(Person "Harry" Male 13), (Person "Hermione" Female 13)]
Person "Hermione" Female 13

Only one constructor in Person definition with 3 arguments:

Person :: Name -> Gender -> Age -> Person

Parameterized data Declarations

Exactly like using type parameters in function type declarations:

data Pair a b = Pair a b
x = Pair 1 2
y = Pair "Howdy" 42

first :: Pair a b -> a
first (Pair x _) = x

apply :: (a -> a') -> (b -> b') -> Pair a b -> Pair a' b'
apply f g (Pair x y) = Pair (f x) (g y)

Maybe data type

Acts like a pointer in C: points to a value of type a or is a null pointer.

data Maybe a = Nothing | Just a

...where a is a parameter that can hold any type.

lookup :: (Eq a) => a -> [(a,b)] -> Maybe a

Recursive data types

data Nat = Zero | Succ Nat

Zero
Succ Zero
Succ (Succ Zero)
Succ (Succ (Succ Zero))
-- etc.

Lists are just recursive data types:

data List a = Nil | Cons a (List a)

Deriving

By default, the only thing you can do with a custom data type is construct and destruct. To import other functionality, use deriving keyword in definiton:

data Bool = False | True deriving (Eq, Ord, Enum, Read, Show, Bounded)

provides default implementation of functions for given data types. To override the defaults, create an instance declaration.

Example Evaluator

-- Evaluator.hs
data Tree = Lit Int
          | BinOp Op Tree Tree
            deriving Show

data Op = OpPlus | OpMinus | OpMult | OpDiv
            deriving Show

x = Lit 2
y = BinOp OpPlus (Lit 3) x


o2f :: Op -> (Int -> Int -> Int)
o2f OpPlus  = (+)
o2f OpMinus = (-)
o2f OpMult  = (*)
o2f OpDiv   = div

eval :: Tree -> Int
eval (Lit i) = i
eval (BinOp op l r) = f (eval l) (eval r)
    where f = o2f op