87 people like it.

Top-Down-Operator-Precedence Parser

F# implementation of a generic Top-Down-Operator-Precedence Parser as described in this paper http://portal.acm.org/citation.cfm?id=512931 Example starts at line ~300

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
130: 
131: 
132: 
133: 
134: 
135: 
136: 
137: 
138: 
139: 
140: 
141: 
142: 
143: 
144: 
145: 
146: 
147: 
148: 
149: 
150: 
151: 
152: 
153: 
154: 
155: 
156: 
157: 
158: 
159: 
160: 
161: 
162: 
163: 
164: 
165: 
166: 
167: 
168: 
169: 
170: 
171: 
172: 
173: 
174: 
175: 
176: 
177: 
178: 
179: 
180: 
181: 
182: 
183: 
184: 
185: 
186: 
187: 
188: 
189: 
190: 
191: 
192: 
193: 
194: 
195: 
196: 
197: 
198: 
199: 
200: 
201: 
202: 
203: 
204: 
205: 
206: 
207: 
208: 
209: 
210: 
211: 
212: 
213: 
214: 
215: 
216: 
217: 
218: 
219: 
220: 
221: 
222: 
223: 
224: 
225: 
226: 
227: 
228: 
229: 
230: 
231: 
232: 
233: 
234: 
235: 
236: 
237: 
238: 
239: 
240: 
241: 
242: 
243: 
244: 
245: 
246: 
247: 
248: 
249: 
250: 
251: 
252: 
253: 
254: 
255: 
256: 
257: 
258: 
259: 
260: 
261: 
262: 
263: 
264: 
265: 
266: 
267: 
268: 
269: 
270: 
271: 
272: 
273: 
274: 
275: 
276: 
277: 
278: 
279: 
280: 
281: 
282: 
283: 
284: 
285: 
286: 
287: 
288: 
289: 
290: 
291: 
292: 
293: 
294: 
295: 
296: 
297: 
298: 
299: 
300: 
301: 
302: 
303: 
304: 
305: 
306: 
307: 
308: 
309: 
310: 
311: 
312: 
313: 
314: 
315: 
316: 
317: 
318: 
319: 
320: 
321: 
322: 
323: 
324: 
325: 
326: 
327: 
328: 
329: 
330: 
331: 
332: 
333: 
334: 
335: 
336: 
337: 
338: 
339: 
340: 
341: 
342: 
343: 
344: 
345: 
346: 
347: 
348: 
349: 
350: 
351: 
352: 
353: 
354: 
355: 
356: 
357: 
358: 
359: 
360: 
361: 
362: 
363: 
364: 
365: 
366: 
367: 
368: 
369: 
370: 
371: 
372: 
373: 
374: 
375: 
376: 
377: 
378: 
379: 
380: 
381: 
382: 
383: 
384: 
385: 
386: 
387: 
388: 
389: 
390: 
391: 
392: 
393: 
394: 
395: 
396: 
397: 
398: 
399: 
400: 
401: 
402: 
403: 
404: 
405: 
406: 
407: 
408: 
409: 
410: 
411: 
412: 
module Parser = 
  
  (*
  F# implementation of a generic Top-Down-Operator-Precedence Parser 
  as described in this paper http://portal.acm.org/citation.cfm?id=512931.

  The parser has been extended to allow for statements in comparison to Pratt's
  original algorithm which only parsed languages which use expression-only grammar.

  The parser is "impure" in the sense that is uses a ref-cell for storing the
  input in the T<_, _, _> record object, this is soley for performance reasons
  as it's to expensive to create a new record object for every consumed token.

  Certain functions also throw exceptions, which generally also is considered impure.

  More information:
  * http://en.wikipedia.org/wiki/Vaughan_Pratt (Original Inventor)
  * http://en.wikipedia.org/wiki/Pratt_parser (Alias name)
  * http://effbot.org/zone/simple-top-down-parsing.htm (Python implementation)
  * http://javascript.crockford.com/tdop/tdop.html (JavaScript implementation)
  *)

  type Pos = int * int

  type T<'a, 'b, 'c> when 'c : comparison = {
      Input : 'a list ref
      Null : Map<'c, 'a -> T<'a, 'b, 'c> -> 'b>
      Stmt : Map<'c, 'a -> T<'a, 'b, 'c> -> 'b>
      Left : Map<'c, 'a -> 'b -> T<'a, 'b, 'c> -> 'b>
      Bpwr : Map<'c, int>
      Type : 'a -> 'c
      Line : 'a -> Pos
  }
  
  type Pattern<'a, 'b, 'c> when 'c : comparison 
    = Sym of 'c
    | Get of (T<'a, 'b, 'c> -> 'b)

  type Exn (msg, pos) = 
    inherit System.Exception(msg)
    member x.Position = pos

  let exn msg = Exn(msg, (-1, -1)) |> raise
  let private exn_line pos msg = Exn(msg, pos) |> raise

  let private unexpected_end () = "Unexpected end of input" |> exn
  let private type_mismatch a b pos = 
    let msg = sprintf "Expected token of type %A but found %A" a b
    msg |> exn_line pos

  let inline private call_nud tok x = x.Null.[x.Type tok] tok x
  let inline private call_smd tok x = x.Stmt.[x.Type tok] tok x
  let inline private call_led tok left x = x.Left.[x.Type tok] tok left x
  let inline private get_bpw tok x = 
    match x.Bpwr.TryFind (x.Type tok) 
      with Some pwr -> pwr | _ -> 0

  let current_exn x =  
    match !x.Input with
    | x::_ -> x
    | _ -> unexpected_end ()

  let current x = 
    match !x.Input with
    | x::_ -> Some x
    | _ -> None

  let current_type x =
    match x |> current with
    | None -> None
    | Some tok -> Some(tok |> x.Type)

  let current_type_exn x = 
    x |> current_exn |> x.Type

  let skip x =
    match !x.Input with
    | _::xs -> x.Input := xs
    | _ -> unexpected_end ()

  let skip_if type' x =
    match !x.Input with
    | tok::xs when x.Type tok = type' -> x.Input := xs
    | tok::_ -> type_mismatch type' (x.Type tok) (x.Line tok)
    | _ -> unexpected_end ()

  let skip_if_try type' x =
    match !x.Input with
    | tok::xs when x.Type tok = type' -> x.Input := xs; true
    | tok::_ -> false
    | _ -> false
   
  let expr rbpw x =
    let rec expr left =
      match x |> current with
      | Some tok when rbpw < (x |> get_bpw tok) -> 
        x |> skip
        expr (x |> call_led tok left)

      | _ -> left

    let tok = x |> current_exn
    x |> skip
    expr (x |> call_nud tok)

  let expr_then then' x =
    let expr = x |> expr 0
    x |> skip_if then'
    expr

  let expr_any x = expr 0 x

  let rec expr_list x =
    match !x.Input with
    | [] -> []
    | _ -> (x |> expr 0) :: (x |> expr_list)

  let stmt term x =
    let tok = x |> current_exn
    match x.Stmt.TryFind (tok |> x.Type) with
    | None -> 
      let xpr = x |> expr 0
      x |> skip_if term
      xpr

    | Some f ->
      x |> skip
      f tok x

  let rec stmt_list term x =
    match !x.Input with
    | [] -> []
    | _ -> (x |> stmt term)  :: (x |> stmt_list term)

  let match' pat parser =

    let rec match' pat acc p =
      match pat with
      | [] -> acc |> List.rev

      | Sym(s)::pat -> 
        if p |> skip_if_try s
          then p |> match' pat acc
          else []

      | Get(f)::pat ->
        let acc = (f p :: acc)
        p |> match' pat acc

    parser |> match' pat []

  let match_error () = failwith ""

  let create<'a, 'b, 'c when 'c : comparison> type' line = {
    Input = ref []
    Null = Map.empty<'c, 'a -> T<'a, 'b, 'c> -> 'b>
    Stmt = Map.empty<'c, 'a -> T<'a, 'b, 'c> -> 'b>
    Left = Map.empty<'c, 'a -> 'b -> T<'a, 'b, 'c> -> 'b>
    Bpwr = Map.empty<'c, int>
    Type = type'
    Line = line
  }

  let smd token parser x = {x with T.Stmt = x.Stmt.Add(token, parser)}
  let nud token parser x = {x with T.Null = x.Null.Add(token, parser)}
  let led token parser x = {x with T.Left = x.Left.Add(token, parser)}
  let bpw token power  x = {x with T.Bpwr = x.Bpwr.Add(token, power)}
    
  let run_expr input parser =
    {parser with T.Input = ref input} |> expr_list

  let run_stmt term input parser =
    {parser with T.Input = ref input} |> stmt_list term

(*

Example parser for a very simple grammar, assumes the Parser module exists in current namespace

*)

//AST Types
type UnaryOp
  = Plus
  | Minus
  
type BinaryOp
  = Multiply
  | Add
  | Subtract
  | Divide
  | Assign
  | Equals

type Ast
  = Number of int
  | Identifier of string
  | String of string
  | Binary of BinaryOp * Ast * Ast
  | Unary of UnaryOp * Ast
  | Ternary of Ast * Ast * Ast // test * ifTrue * ifFalse
  | If of Ast * Ast * Ast option // test + ifTrue and possibly ifFalse (else branch)
  | Call of Ast * Ast list // target + arguments list
  | Block of Ast list // statements list
  | True
  | False

//Shorthand types for convenience
module P = Parser
type Token = string * string * (Parser.Pos)
type P = Parser.T<Token, Ast, string>

//Utility functions for extracting values out of Token
let type' ((t, _, _):Token) = t
let value ((_, v, _):Token) = v
let pos ((_, _, p):Token) = p
let value_num (t:Token) = t |> value |> int

//Utility functions for creating new tokens
let number value pos : Token = "#number", value, pos
let string value pos : Token = "#string", value, pos
let identifier name pos : Token = "#identifier", name, pos

let symbol type' pos : Token = type', "", pos
let add = symbol "+"
let sub = symbol "-"
let mul = symbol "*"
let div = symbol "/"
let assign = symbol "="
let equals = symbol "=="
let lparen = symbol "("
let rparen = symbol ")"
let lbrace = symbol "{"
let rbrace = symbol "}"
let comma = symbol ","
let qmark = symbol "?"
let colon = symbol ":"
let scolon = symbol ";"
let if' = symbol "if"
let true' = symbol "true"
let else' = symbol "else"

//Utility functions for converting tokens to binary and unary operators
let toBinaryOp tok =
  match type' tok with
  | "=" -> BinaryOp.Assign
  | "+" -> BinaryOp.Add
  | "-" -> BinaryOp.Subtract
  | "*" -> BinaryOp.Multiply
  | "/" -> BinaryOp.Divide
  | "==" -> BinaryOp.Equals
  | _ -> P.exn (sprintf "Couldn't convert %s-token to BinaryOp" (type' tok))

let toUnaryOp tok =
  match type' tok with
  | "+" -> UnaryOp.Plus
  | "-" -> UnaryOp.Minus
  | _ -> P.exn (sprintf "Couldn't convert %s-token to UnaryOp" (type' tok))

//Utility function for defining infix operators
let infix typ pwr p =
  let infix tok left (p:P) =
    Binary(tok |> toBinaryOp, left, p |> P.expr pwr)

  p |> P.bpw typ pwr |> P.led typ infix
  
//Utility function for defining prefix operators
let prefix typ p =
  let prefix tok (p:P) =
    Unary(tok |> toUnaryOp, p |> P.expr 70)

  p |> P.nud typ prefix
  
//Utility function for defining constants
let constant typ value p =
  p |> P.nud typ (fun _ _ -> value)

//Utility function for parsing a block 
let block p =
  let rec stmts p =
    match p |> P.current_type with
    | None -> []
    | Some "}" -> p |> P.skip; []
    | _ -> (p |> P.stmt ";") :: (stmts p)

  p |> P.skip_if "{"
  Block(p |> stmts)

//The parser definition
let example_parser =
  (P.create type' pos)

  //Literals and identifiers
  |> P.nud "#number" (fun t _ -> t |> value |> int |> Number) 
  |> P.nud "#identifier" (fun t _ -> t |> value |> Identifier)
  |> P.nud "#string" (fun t _ -> t |> value |> String)

  //Constants
  |> constant "true" Ast.True
  |> constant "false" Ast.False
  
  //Infix Operators <expr> <op> <expr>
  |> infix "==" 40
  |> infix "+" 50
  |> infix "-" 50
  |> infix "*" 60
  |> infix "/" 60
  |> infix "=" 80

  //Prefix Operators <op> <expr>
  |> prefix "+"
  |> prefix "-"
  
  //Grouping expressions (<expr>)
  |> P.nud "(" (fun t p -> p |> P.expr_then ")")

  //Ternary operator <expr> ? <expr> : <expr>
  |> P.bpw "?" 70
  |> P.led "?" (fun _ left p ->
      let ternary = [P.Get P.expr_any; P.Sym ":"; P.Get P.expr_any]
      match p |> P.match' ternary with
      | ifTrue::ifFalse::_ -> Ternary(left, ifTrue, ifFalse)
      | _ -> P.match_error()
    )

  //If/Else statement if(<condition>) { <exprs } [else { <exprs> }]
  |> P.smd "if" (fun _ p ->
      let if' = [P.Sym "("; P.Get P.expr_any; P.Sym ")"; P.Get block]
      let else' = [P.Sym "else"; P.Get block]

      match p |> P.match' if' with
      | test::ifTrue::_ -> 
        match p |> P.match' else' with
        | ifFalse::_ -> If(test, ifTrue, Some(ifFalse))
        | _ -> If(test, ifTrue, None)
      | _ -> P.match_error()
    )

  //Function call
  |> P.bpw "(" 80
  |> P.led "(" (fun _ func p ->
      let rec args (p:P) =
        match p |> P.current_type_exn with
        | ")" -> p |> P.skip; []
        | "," -> p |> P.skip; args p
        | _ -> (p |> P.expr_any) :: args p

      Call(func, args p)
    )
    
//Code to parse
(*
1: x = 5;
2: y = 5;
3: 
4: if(x == y) {
5:   print("x equals y");
6: } else {
7:   print("x doesn't equal y");
8: }
*)

//The code in tokens, manually entered
//since we don't have a lexer to produce
//the tokens for us
let tokens = 
  [
    //x = 5;
    identifier "x" (1, 1)
    assign (1, 3)
    number "5" (1, 5)
    scolon (1, 6)

    //y = 5;
    identifier "y" (2, 1)
    assign (2, 3)
    number "5" (2, 5)
    scolon (2, 6)

    //if(x == y) {
    if' (4, 1)
    lparen (4, 3)
    identifier "x" (4, 4)
    equals (4, 6)
    identifier "y" (4, 9)
    rparen (4, 10)
    lbrace (4, 12)

    //print("x equals y");
    identifier "print" (5, 3)
    lparen (5, 7)
    string "x equals y" (5, 9)
    rparen (5, 21)
    scolon (5, 22)

    //} else {
    rbrace (6, 1)
    else' (6, 3)
    lbrace (6, 7)

    //print("x doesn't equal y");
    identifier "print" (7, 3)
    lparen (7, 7)
    string "x doesn't equal y" (7, 9)
    rparen (7, 27)
    scolon (7, 28)

    //}
    rbrace (8, 1)
  ]

let ast =
  example_parser |> P.run_stmt ";" tokens
type Pos = int * int

Full name: Script.Parser.Pos
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type T<'a,'b,'c (requires comparison)> =
  {Input: 'a list ref;
   Null: Map<'c,('a -> T<'a,'b,'c> -> 'b)>;
   Stmt: Map<'c,('a -> T<'a,'b,'c> -> 'b)>;
   Left: Map<'c,('a -> 'b -> T<'a,'b,'c> -> 'b)>;
   Bpwr: Map<'c,int>;
   Type: 'a -> 'c;
   Line: 'a -> Pos;}

Full name: Script.Parser.T<_,_,_>
T.Input: 'a list ref
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
T.Null: Map<'c,('a -> T<'a,'b,'c> -> 'b)>
Multiple items
module Map

from Microsoft.FSharp.Collections

--------------------
type Map<'Key,'Value (requires comparison)> =
  interface IEnumerable
  interface IComparable
  interface IEnumerable<KeyValuePair<'Key,'Value>>
  interface ICollection<KeyValuePair<'Key,'Value>>
  interface IDictionary<'Key,'Value>
  new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
  member Add : key:'Key * value:'Value -> Map<'Key,'Value>
  member ContainsKey : key:'Key -> bool
  override Equals : obj -> bool
  member Remove : key:'Key -> Map<'Key,'Value>
  ...

Full name: Microsoft.FSharp.Collections.Map<_,_>

--------------------
new : elements:seq<'Key * 'Value> -> Map<'Key,'Value>
T.Stmt: Map<'c,('a -> T<'a,'b,'c> -> 'b)>
T.Left: Map<'c,('a -> 'b -> T<'a,'b,'c> -> 'b)>
T.Bpwr: Map<'c,int>
T.Type: 'a -> 'c
T.Line: 'a -> Pos
type Pattern<'a,'b,'c (requires comparison)> =
  | Sym of 'c
  | Get of (T<'a,'b,'c> -> 'b)

Full name: Script.Parser.Pattern<_,_,_>
union case Pattern.Sym: 'c -> Pattern<'a,'b,'c>
union case Pattern.Get: (T<'a,'b,'c> -> 'b) -> Pattern<'a,'b,'c>
Multiple items
type Exn =
  inherit Exception
  new : msg:string * pos:(int * int) -> Exn
  member Position : int * int

Full name: Script.Parser.Exn

--------------------
new : msg:string * pos:(int * int) -> Exn
val msg : string
val pos : int * int
namespace System
Multiple items
type Exception =
  new : unit -> Exception + 2 overloads
  member Data : IDictionary
  member GetBaseException : unit -> Exception
  member GetObjectData : info:SerializationInfo * context:StreamingContext -> unit
  member GetType : unit -> Type
  member HelpLink : string with get, set
  member InnerException : Exception
  member Message : string
  member Source : string with get, set
  member StackTrace : string
  ...

Full name: System.Exception

--------------------
System.Exception() : unit
System.Exception(message: string) : unit
System.Exception(message: string, innerException: exn) : unit
System.Exception(info: System.Runtime.Serialization.SerializationInfo, context: System.Runtime.Serialization.StreamingContext) : unit
val x : Exn
member Exn.Position : int * int

Full name: Script.Parser.Exn.Position
Multiple items
val exn : msg:string -> 'a

Full name: Script.Parser.exn

--------------------
type exn = System.Exception

Full name: Microsoft.FSharp.Core.exn
val raise : exn:System.Exception -> 'T

Full name: Microsoft.FSharp.Core.Operators.raise
val private exn_line : int * int -> msg:string -> 'a

Full name: Script.Parser.exn_line
val private unexpected_end : unit -> 'a

Full name: Script.Parser.unexpected_end
val private type_mismatch : a:'a -> b:'b -> int * int -> 'c

Full name: Script.Parser.type_mismatch
val a : 'a
val b : 'b
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val private call_nud : tok:'a -> x:T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.call_nud
val tok : 'a
val x : T<'a,'b,'c> (requires comparison)
val private call_smd : tok:'a -> x:T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.call_smd
val private call_led : tok:'a -> left:'b -> x:T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.call_led
val left : 'b
val private get_bpw : tok:'a -> x:T<'a,'b,'c> -> int (requires comparison)

Full name: Script.Parser.get_bpw
member Map.TryFind : key:'Key -> 'Value option
union case Option.Some: Value: 'T -> Option<'T>
val pwr : int
val current_exn : x:T<'a,'b,'c> -> 'a (requires comparison)

Full name: Script.Parser.current_exn
val x : 'a
val current : x:T<'a,'b,'c> -> 'a option (requires comparison)

Full name: Script.Parser.current
union case Option.None: Option<'T>
val current_type : x:T<'a,'b,'c> -> 'c option (requires comparison)

Full name: Script.Parser.current_type
val current_type_exn : x:T<'a,'b,'c> -> 'c (requires comparison)

Full name: Script.Parser.current_type_exn
val skip : x:T<'a,'b,'c> -> unit (requires comparison)

Full name: Script.Parser.skip
val xs : 'a list
val skip_if : type':'a -> x:T<'b,'c,'a> -> unit (requires comparison)

Full name: Script.Parser.skip_if
val type' : 'a (requires comparison)
val x : T<'b,'c,'a> (requires comparison)
T.Input: 'b list ref
val tok : 'b
val xs : 'b list
T.Type: 'b -> 'a
T.Line: 'b -> Pos
val skip_if_try : type':'a -> x:T<'b,'c,'a> -> bool (requires comparison)

Full name: Script.Parser.skip_if_try
val expr : rbpw:int -> x:T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.expr
val rbpw : int
val expr : ('b -> 'b)
val expr_then : then':'a -> x:T<'b,'c,'a> -> 'c (requires comparison)

Full name: Script.Parser.expr_then
val then' : 'a (requires comparison)
val expr : 'c
val expr_any : x:T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.expr_any
val expr_list : x:T<'a,'b,'c> -> 'b list (requires comparison)

Full name: Script.Parser.expr_list
val stmt : term:'a -> x:T<'b,'c,'a> -> 'c (requires comparison)

Full name: Script.Parser.stmt
val term : 'a (requires comparison)
T.Stmt: Map<'a,('b -> T<'b,'c,'a> -> 'c)>
val xpr : 'c
val f : ('b -> T<'b,'c,'a> -> 'c) (requires comparison)
val stmt_list : term:'a -> x:T<'b,'c,'a> -> 'c list (requires comparison)

Full name: Script.Parser.stmt_list
val match' : pat:Pattern<'a,'b,'c> list -> parser:T<'a,'b,'c> -> 'b list (requires comparison)

Full name: Script.Parser.match'
val pat : Pattern<'a,'b,'c> list (requires comparison)
val parser : T<'a,'b,'c> (requires comparison)
val match' : (Pattern<'d,'e,'f> list -> 'e list -> T<'d,'e,'f> -> 'e list) (requires comparison)
val pat : Pattern<'d,'e,'f> list (requires comparison)
val acc : 'e list
val p : T<'d,'e,'f> (requires comparison)
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev
val s : 'f (requires comparison)
val f : (T<'d,'e,'f> -> 'e) (requires comparison)
val match_error : unit -> 'a

Full name: Script.Parser.match_error
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val create : type':('a -> 'c) -> line:('a -> Pos) -> T<'a,'b,'c> (requires comparison)

Full name: Script.Parser.create
val type' : ('a -> 'c) (requires comparison)
val line : ('a -> Pos)
val empty<'Key,'T (requires comparison)> : Map<'Key,'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Map.empty
val smd : token:'a -> parser:('b -> T<'b,'c,'a> -> 'c) -> x:T<'b,'c,'a> -> T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.smd
val token : 'a (requires comparison)
val parser : ('b -> T<'b,'c,'a> -> 'c) (requires comparison)
member Map.Add : key:'Key * value:'Value -> Map<'Key,'Value>
val nud : token:'a -> parser:('b -> T<'b,'c,'a> -> 'c) -> x:T<'b,'c,'a> -> T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.nud
T.Null: Map<'a,('b -> T<'b,'c,'a> -> 'c)>
val led : token:'a -> parser:('b -> 'c -> T<'b,'c,'a> -> 'c) -> x:T<'b,'c,'a> -> T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.led
val parser : ('b -> 'c -> T<'b,'c,'a> -> 'c) (requires comparison)
T.Left: Map<'a,('b -> 'c -> T<'b,'c,'a> -> 'c)>
val bpw : token:'a -> power:int -> x:T<'b,'c,'a> -> T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.bpw
val power : int
T.Bpwr: Map<'a,int>
val run_expr : input:'a list -> parser:T<'a,'b,'c> -> 'b list (requires comparison)

Full name: Script.Parser.run_expr
val input : 'a list
val run_stmt : term:'a -> input:'b list -> parser:T<'b,'c,'a> -> 'c list (requires comparison)

Full name: Script.Parser.run_stmt
val input : 'b list
val parser : T<'b,'c,'a> (requires comparison)
type UnaryOp =
  | Plus
  | Minus

Full name: Script.UnaryOp
union case UnaryOp.Plus: UnaryOp
union case UnaryOp.Minus: UnaryOp
type BinaryOp =
  | Multiply
  | Add
  | Subtract
  | Divide
  | Assign
  | Equals

Full name: Script.BinaryOp
union case BinaryOp.Multiply: BinaryOp
union case BinaryOp.Add: BinaryOp
union case BinaryOp.Subtract: BinaryOp
union case BinaryOp.Divide: BinaryOp
union case BinaryOp.Assign: BinaryOp
union case BinaryOp.Equals: BinaryOp
type Ast =
  | Number of int
  | Identifier of string
  | String of string
  | Binary of BinaryOp * Ast * Ast
  | Unary of UnaryOp * Ast
  | Ternary of Ast * Ast * Ast
  | If of Ast * Ast * Ast option
  | Call of Ast * Ast list
  | Block of Ast list
  | True
  ...

Full name: Script.Ast
union case Ast.Number: int -> Ast
union case Ast.Identifier: string -> Ast
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
Multiple items
union case Ast.String: string -> Ast

--------------------
module String

from Microsoft.FSharp.Core
union case Ast.Binary: BinaryOp * Ast * Ast -> Ast
union case Ast.Unary: UnaryOp * Ast -> Ast
union case Ast.Ternary: Ast * Ast * Ast -> Ast
union case Ast.If: Ast * Ast * Ast option -> Ast
type 'T option = Option<'T>

Full name: Microsoft.FSharp.Core.option<_>
union case Ast.Call: Ast * Ast list -> Ast
union case Ast.Block: Ast list -> Ast
union case Ast.True: Ast
union case Ast.False: Ast
module Parser

from Script
type Token = string * string * Parser.Pos

Full name: Script.Token
type P = Parser.T<Token,Ast,string>

Full name: Script.P
val type' : string * string * Parser.Pos -> string

Full name: Script.type'
val t : string
val value : string * string * Parser.Pos -> string

Full name: Script.value
val v : string
val pos : string * string * Parser.Pos -> Parser.Pos

Full name: Script.pos
val p : Parser.Pos
val value_num : string * string * Parser.Pos -> int

Full name: Script.value_num
val t : Token
val number : value:string -> int * int -> Token

Full name: Script.number
val value : string
val pos : Parser.Pos
Multiple items
val string : value:string -> int * int -> Token

Full name: Script.string

--------------------
type string = System.String

Full name: Microsoft.FSharp.Core.string
val identifier : name:string -> int * int -> Token

Full name: Script.identifier
val name : string
val symbol : type':string -> int * int -> Token

Full name: Script.symbol
val type' : string
val add : (Parser.Pos -> Token)

Full name: Script.add
val sub : (Parser.Pos -> Token)

Full name: Script.sub
val mul : (Parser.Pos -> Token)

Full name: Script.mul
val div : (Parser.Pos -> Token)

Full name: Script.div
val assign : (Parser.Pos -> Token)

Full name: Script.assign
val equals : (Parser.Pos -> Token)

Full name: Script.equals
val lparen : (Parser.Pos -> Token)

Full name: Script.lparen
val rparen : (Parser.Pos -> Token)

Full name: Script.rparen
val lbrace : (Parser.Pos -> Token)

Full name: Script.lbrace
val rbrace : (Parser.Pos -> Token)

Full name: Script.rbrace
val comma : (Parser.Pos -> Token)

Full name: Script.comma
val qmark : (Parser.Pos -> Token)

Full name: Script.qmark
val colon : (Parser.Pos -> Token)

Full name: Script.colon
val scolon : (Parser.Pos -> Token)

Full name: Script.scolon
val if' : (Parser.Pos -> Token)

Full name: Script.if'
val true' : (Parser.Pos -> Token)

Full name: Script.true'
val else' : (Parser.Pos -> Token)

Full name: Script.else'
val toBinaryOp : string * string * Parser.Pos -> BinaryOp

Full name: Script.toBinaryOp
val tok : Token
val exn : msg:string -> 'a

Full name: Script.Parser.exn
val toUnaryOp : string * string * Parser.Pos -> UnaryOp

Full name: Script.toUnaryOp
val infix : typ:string -> pwr:int -> p:Parser.T<Token,Ast,string> -> Parser.T<Token,Ast,string>

Full name: Script.infix
val typ : string
val p : Parser.T<Token,Ast,string>
val infix : (Token -> Ast -> P -> Ast)
val left : Ast
val p : P
val expr : rbpw:int -> x:Parser.T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.expr
val bpw : token:'a -> power:int -> x:Parser.T<'b,'c,'a> -> Parser.T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.bpw
val led : token:'a -> parser:('b -> 'c -> Parser.T<'b,'c,'a> -> 'c) -> x:Parser.T<'b,'c,'a> -> Parser.T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.led
val prefix : typ:string -> p:Parser.T<Token,Ast,string> -> Parser.T<Token,Ast,string>

Full name: Script.prefix
val prefix : (Token -> P -> Ast)
val nud : token:'a -> parser:('b -> Parser.T<'b,'c,'a> -> 'c) -> x:Parser.T<'b,'c,'a> -> Parser.T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.nud
val constant : typ:'a -> value:'b -> p:Parser.T<'c,'b,'a> -> Parser.T<'c,'b,'a> (requires comparison)

Full name: Script.constant
val typ : 'a (requires comparison)
val value : 'b
val p : Parser.T<'c,'b,'a> (requires comparison)
val block : p:Parser.T<'a,Ast,string> -> Ast

Full name: Script.block
val p : Parser.T<'a,Ast,string>
val stmts : (Parser.T<'b,'c,string> -> 'c list)
val p : Parser.T<'b,'c,string>
val current_type : x:Parser.T<'a,'b,'c> -> 'c option (requires comparison)

Full name: Script.Parser.current_type
val skip : x:Parser.T<'a,'b,'c> -> unit (requires comparison)

Full name: Script.Parser.skip
val stmt : term:'a -> x:Parser.T<'b,'c,'a> -> 'c (requires comparison)

Full name: Script.Parser.stmt
val skip_if : type':'a -> x:Parser.T<'b,'c,'a> -> unit (requires comparison)

Full name: Script.Parser.skip_if
val example_parser : Parser.T<Token,Ast,string>

Full name: Script.example_parser
val create : type':('a -> 'c) -> line:('a -> Parser.Pos) -> Parser.T<'a,'b,'c> (requires comparison)

Full name: Script.Parser.create
val expr_then : then':'a -> x:Parser.T<'b,'c,'a> -> 'c (requires comparison)

Full name: Script.Parser.expr_then
val ternary : Parser.Pattern<'a,'b,string> list
union case Parser.Pattern.Get: (Parser.T<'a,'b,'c> -> 'b) -> Parser.Pattern<'a,'b,'c>
val expr_any : x:Parser.T<'a,'b,'c> -> 'b (requires comparison)

Full name: Script.Parser.expr_any
union case Parser.Pattern.Sym: 'c -> Parser.Pattern<'a,'b,'c>
val match' : pat:Parser.Pattern<'a,'b,'c> list -> parser:Parser.T<'a,'b,'c> -> 'b list (requires comparison)

Full name: Script.Parser.match'
val ifTrue : Ast
val ifFalse : Ast
val smd : token:'a -> parser:('b -> Parser.T<'b,'c,'a> -> 'c) -> x:Parser.T<'b,'c,'a> -> Parser.T<'b,'c,'a> (requires comparison)

Full name: Script.Parser.smd
val if' : Parser.Pattern<'a,Ast,string> list
val else' : Parser.Pattern<'a,Ast,string> list
val test : Ast
val func : Ast
val args : (P -> Ast list)
val current_type_exn : x:Parser.T<'a,'b,'c> -> 'c (requires comparison)

Full name: Script.Parser.current_type_exn
val tokens : Token list

Full name: Script.tokens
val ast : Ast list

Full name: Script.ast
val run_stmt : term:'a -> input:'b list -> parser:Parser.T<'b,'c,'a> -> 'c list (requires comparison)

Full name: Script.Parser.run_stmt

More information

Link:http://fssnip.net/2X
Posted:13 years ago
Author:fholm
Tags: parsers , parser