Return to parser.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / doc / examples

Annotation of researchv10no/cmd/sml/doc/examples/parser.sml, revision 1.1.1.1

1.1       root        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","."];

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.