home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / parser.sml < prev    next >
Encoding:
Text File  |  1995-12-30  |  2.3 KB  |  82 lines  |  [TEXT/R*ch]
  1. (* a simple parser.  (R. Burstall)
  2. The grammar is:
  3.  
  4.     var      = x | y | z
  5.     const = 0 | 1 | 2
  6.     aexpr = var | const | (expr)
  7.     expr  = aexpr + expr | aexpr * expr | aexpr
  8.     stmt  = var := expr
  9.       | if expr then stmt
  10.       | while expr do stmt
  11.       | begin stmts end
  12.     stmts = stmt ; stmts | stmt
  13.     decl  = var : integer | var : boolean
  14.     decls = decl ; decls | decl
  15.     prog  = var decls begin stmts end .
  16.  
  17. If S is a set of string lists we say that a function f: string list -> string list
  18. recognizes S if
  19.  
  20.   (1) if l does not begin with a list in S then f l fails
  21.   (2) if s is the longest list in S such that l = s@m for some list m, then 
  22.       f l = m
  23.  
  24. Each phrase name in the grammar above denotes a set of string lists.  We write ML
  25. functions called var, const, aexpr, ..., to recognized each of these phrases
  26. (i.e. to recognize the associated set of string lists).
  27.  
  28. If f1 recognizes P1 and f2 recognizes P2 then we can define a function g to
  29. recognize P1 P2 by 
  30.  
  31.   g = f1 & f2       where f & g = (fn s => g(f s))
  32.  
  33. We can define a function h to recognize P1 | P2 by
  34.  
  35.   h = f = f1 || f2    where f || g = (fn s => f1 s handle Fail => f2 s)
  36. *)
  37.  
  38. exception Fail
  39.  
  40. infix 3 &
  41. infix 2 ||
  42.  
  43. fun f1 & f2 = (fn s => f2(f1 s))
  44. fun f1 || f2 = (fn s => f1 s handle Fail => f2 s)
  45.  
  46. fun quote (t: string) ([]: string list) = raise Fail
  47.   | quote t (t' :: rest) = if t = t' then rest else raise Fail
  48.  
  49. val var = quote "x" || quote "y" || quote "z"
  50.  
  51. val const = quote "0" || quote "1" || quote "2"
  52.  
  53. fun aexpr s = (var || const || quote "(" & expr & quote ")") s
  54.  
  55. and expr s = (aexpr & quote "+" & expr || 
  56.           aexpr & quote "*" & expr || 
  57.           aexpr) s
  58.  
  59. and stmt s = (var & quote ":=" & expr || 
  60.           quote "if" & expr & quote "then" & stmt ||
  61.           quote "while" & expr & quote "do" & stmt ||
  62.           quote "begin" & stmts & quote "end") s
  63.  
  64. and stmts s = (stmt & quote ";" & stmts || stmt) s
  65.  
  66. and decl s = (var & quote ":" & quote "integer" ||
  67.           var & quote ":" & quote "boolean") s
  68.  
  69. and decls s = (decl & quote ";" & decls || decl) s
  70.  
  71. and prog s = (quote "var" & decls & quote "begin" & stmts & quote "end" &
  72.           quote ".") s
  73.  
  74. fun parse s = (if prog s = [] then "YES" else "NO") handle Fail => "NO";
  75.  
  76. (* examples *)
  77.  
  78. expr ["x","+","1", "end", "."];
  79.  
  80. parse ["var","x",":","integer",";","y",":","boolean",
  81.        "begin","x",":=","0","end","."];
  82.