{-   
      Title: Parse values
      Author: Robin Cockett
      Notes: Using the second grammar:

             expr -> expr ADD term          P1
                   | term.                  P2
             term -> term MUL factor        P3
                   | factor.                P4
             factor -> NUM                  P5

      I create a mutually recursive datatype for the parse 
      trees of the grammar and write the "parse_value" function.
-}

data Expr = P1 Expr Add Term
          | P2 Term
     deriving (Show,Eq)
data Term = P3 Term Mul Factor
          | P4 Factor
     deriving (Show,Eq)
data Factor = P5 Nm
     deriving (Show,Eq)
data Add = ADD 
     deriving (Show,Eq)
data Mul = MUL
     deriving (Show,Eq)
data Nm = NUM
     deriving (Show,Eq)

-- We need a separate datatype for the tokens
data Tokens = TNUM | TADD | TMUL
     deriving (Show,Eq)

{-  Example of a parse tree

    (P1 (P2 (P4 (P5 NUM))) ADD (P4 (P5 NUM)))

-}

-- The function which given a parse tree outputs the list of 
-- terminals for which it is a parse
expr_parse_value:: Expr -> [Tokens]
expr_parse_value (P1 t1 ADD t2) 
    = (expr_parse_value t1)++[TADD]++(term_parse_value t2)
expr_parse_value (P2 t) = term_parse_value t

term_parse_value:: Term -> [Tokens]
term_parse_value (P3 t1 MUL t2) 
    = (term_parse_value t1)++[TMUL]++(factor_parse_value t2)
term_parse_value (P4 t) 
    = factor_parse_value t
 
factor_parse_value:: Factor -> [Tokens]
factor_parse_value (P5 NUM) = [TNUM]

{- An example of a call of this function is:
     
   expr_parse_value (P1 (P2 (P4 (P5 NUM))) ADD (P4 (P5 NUM)))

-}