Parser fuer vereinfachte Typausdruecke

Dateiinhalt

(* 
Abstrakte Syntax: 
  typ ::= int | typ -> typ
 
Lexikalische Syntax: 
  ARR ::= "->"    INT ::= "int"      LPAR ::= "("      RPAR ::= ")"

Phrasale Syntax + Grammatik fuer rek.Abst. umgeschrieben: 
  typ ::= atyp [ ARR typ ]
 atyp ::= INT | LPAR typ RPAR
*)


datatype token = INT | ARR | LPAR | RPAR
exception error of string;
fun lex nil= nil
   |   lex (#" " :: cr) = lex cr
   |   lex (#"\t" :: cr) = lex cr
   |   lex (#"\n" :: cr) = lex cr
   |   lex (#"(" :: cr) = LPAR :: lex cr
   |   lex (#")" :: cr) = RPAR :: lex cr
   |   lex (#"-" :: #">" :: cr) = ARR :: lex cr
   |   lex (#"i" :: #"n" :: #"t" :: cr) = INT :: lex cr
   |   lex _ = raise error "lex";

datatype typ = Int  | Arr of typ * typ 

fun 
      parsetyp text = let val (tree,rest) = parseatyp text in 
                          case rest of 
                               ARR :: rest1 => let val (tree2,rest2) = 
                                            parsetyp rest1 in
                                       (Arr(tree,tree2), rest2) end
                             | _ => (tree,rest)
                      end
and parseatyp text  = case text of 
                             ARR :: rest => raise (error "misplaced ->")
    |                        INT :: rest => (Int, rest)
    |                        LPAR :: rest => let val (tree, rest1) = 
                                                          parsetyp rest in 
                                               case rest1 of 
                                                 RPAR :: rest2 => 
                                                       (tree, rest2)
                                                   | _ => raise (error "missing )")
                                             end
   |                         RPAR  ::rest => raise (error "misplaced )")