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     ! 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.