递归下降解析器和函数式编程

5 回答

• 12

  来自this blog article的答案：

  所以我的问题是什么是更传统的解析功能方法（即几个副作用）看起来像什么？

  听起来你需要将功能（如Lisp，Scheme，Standard ML，CAML，OCaml，F＃）与纯度（没有副作用，如Haskell）和偶然语言特征（代数数据类型，模式匹配）分开 .

  由于代数数据类型，模式匹配和高阶函数，F＃非常适合解析，非常适合转换和代码生成，但大多数用F＃编写的生成解析器都不是纯粹的 . 从历史上看，F＃语言系列主要源自（MetaLanguages或MLs），专门用于这种元编程 .

  这是一组非常简单的相互递归的活动模式，它解析和评估由单个数字， + - * 运算符和括号子表达式组成的数学表达式：

  > let rec (|Term|_|) = function
      | Factor(e1, t) ->
          let rec aux e1 = function
            | '+'::Factor(e2, t) -> aux (e1 + e2) t
            | '-'::Factor(e2, t) -> aux (e1 - e2) t
            | t -> Some(e1, t)
          aux e1 t
      | _ -> None
    and (|Factor|_|) = function
      | '-'::Factor(e, t) -> Some(-e, t)
      | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
      | Atom(e, t) -> Some(e, t)
      | _ -> None
    and (|Atom|_|) = function
      | c::t when '0'<=c && c<='9' -> Some(int(string c), t)
      | '('::Term(e, ')'::t) -> Some(e, t)
      | _ -> None;;
  val ( |Term|_| ) : char list -> (int * char list) option
  val ( |Factor|_| ) : char list -> (int * char list) option
  val ( |Atom|_| ) : char list -> (int * char list) option
  

  以下是用于解析和计算表达式的示例：

  > let (Term e) = List.ofSeq "1+2*(3-4)*-5";;
  val e : int * char list = (11, [])
  

  这是一个纯粹的解决方案，它使用带有F＃活动模式的列表进行模式匹配 . 实际上，您需要为抽象语法树定义一个类型并返回该类型的值 . 这在F＃中非常简单：

  type expr =
    | Int of int
    | Neg of expr
    | Add of expr * expr
    | Sub of expr * expr
    | Mul of expr * expr
  
    static member (~-) f = Neg f
    static member (+) (f, g) = Add(f, g)
    static member (-) (f, g) = Sub(f, g)
    static member (*) (f, g) = Mul(f, g)
  
  let rec (|Term|_|) = function
    | Factor(e1, t) ->
        let rec aux e1 = function
          | '+'::Factor(e2, t) -> aux (e1 + e2) t
          | '-'::Factor(e2, t) -> aux (e1 - e2) t
          | t -> Some(e1, t)
        aux e1 t
    | _ -> None
  and (|Factor|_|) = function
    | '-'::Factor(e, t) -> Some(-e, t)
    | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
    | Atom(e, t) -> Some(e, t)
    | _ -> None
  and (|Atom|_|) = function
    | c::t when '0'<=c && c<='9' -> Some(Int(int(string c)), t)
    | '('::Term(e, ')'::t) -> Some(e, t)
    | _ -> None
  
  let (Term e) = List.ofSeq "1+2*(3-4)*-5"
  

  请注意，只需要对解析器进行一次小的更改，因为AST也可以使用 + ， - 和 * 运算符构造 .

  其次，尝试采用功能性方法进行解析是否值得，或者它是否真的对中间代码进行了优化，而功能语言的发光却让我还没有到达那里？

  你说的是纯度，而不是函数式编程 . 纯度在解析文本的上下文中并不特别有用，事实上，它可能是一个真正的障碍（例如，实习符号在Haskell中是一场噩梦） . 但是，F＃还有许多其他好处，可以解决这一系列问题 . 特别是，尽管像OCaml这样的其他语言有更好的解析工具，但我认为F＃在这种情况下是最好的.NET语言 .

  也就是说，我是否应该使用命令式样式在F＃中进行解析并稍后切换到更具功能性的方法？

  完全取决于你想要的功能 . 我会使用fslex和fsyacc与纯代码在动作中构建AST，但是对于像散列消耗或生成唯一ID这样的杂质 .

  您可能会对我在this blog（注意付费专区）上就此主题撰写的以下文章表示感谢：

  • "Parsing text with Lex and Yacc"（2007年9月30日） .

  • "Optimizing a simple bytecode interpreter"（2007年10月31日） .

  • "Parser combinators"（2007年11月30日） .

  • "Language-oriented programming: The Term-level Interpreter"（2007年12月31日） .

  • "Language-oriented programming: Term Rewriting"（2008年8月16日） .

  • “使用 System.Reflection.Emit 生成运行时代码”（2008年8月31日） .

  • "Parsing and visualizing binary Geographic Information System data"（2009年11月30日） .

  回复于 2024-04-27T04:26:52+08:00
• 3

  功能解析的一种策略是monadic解析器组合器 . 你可以阅读一些关于它here（并按照链接）或使用像FParsec这样的库 . 但是，如果您只是学习/启动F＃/编译器，我不推荐这种方法 .

  使用F＃的另一种方法是使用FsLex / FsYacc（在PowerPack中） . 我有点厌恶Lex / Yacc技术，所以我也不推荐这个 .

  我认为你应该手工编写一个递归的正确解析器 . 我对标记化器没有强烈的感觉，只是简单地将整个文件标记为一个（n个不可变的）标记，然后进行递归下降（并利用一些模式匹配）是处理解析的好方法 . 当然，您将需要使用已取消的联合来表示解析器的AST输出（la here） .

  我很久没看过龙书，但我显然是这个星球上唯一一个不喜欢它的人 . 我会考虑放弃该文本，转而讨论使用基于ML的语言讨论编译器的书，尽管我不能推荐一个 .

  编辑

  我有一段时间没有做过其中的一个，所以我花了几分钟来编写一个小样本 .

  // AST for tiny language
  type Op = 
      | Plus 
      | Minus 
  type Expr = 
      | Literal of int 
      | BinaryOp of Expr * Op * Expr // left, op, right 
  type Stmt =
      | IfThenElse of Expr * Stmt * Stmt // cond, then, else; 0=false in cond 
      | Print of Expr
  
  // sample program
  let input = @"
      if 1+1-1 then 
          print 42 
      else 
          print 0"
  
  // expected AST
  let goal = 
      IfThenElse(
          BinaryOp( BinaryOp(Literal(1),Plus,Literal(1)), Minus, Literal(1)), 
          Print(Literal(42)), 
          Print(Literal(0))) 
  
  ////////////////////////////////////////////////////////////////////////////
  // Lexer
  
  type Token =
      | IF
      | THEN
      | ELSE
      | PRINT
      | NUM of int  // non-negative
      | PLUS
      | MINUS
      | EOF
  
  let makeTokenizer (s:string) =
      let i = ref 0
      let keywords = [
          "if", IF 
          "then", THEN
          "else", ELSE
          "print", PRINT
          "+", PLUS
          "-", MINUS ]
      let rec getNextToken() =
          if !i >= s.Length then
              EOF
          elif System.Char.IsWhiteSpace(s.[!i]) then
              incr i
              getNextToken()
          elif System.Char.IsDigit(s.[!i]) then
              let mutable j = !i
              while j < s.Length && System.Char.IsDigit(s.[j]) do
                  j <- j + 1
              let numStr = s.Substring(!i, j - !i)
              i := j
              NUM(System.Int32.Parse(numStr)) // may throw, e.g. if > MAXINT
          else 
              let keyword = keywords |> List.tryPick (fun (kwStr,kwTok) ->
                  if s.IndexOf(kwStr, !i) = !i then
                      i := !i + kwStr.Length
                      Some(kwTok)
                  else
                      None)
              match keyword with
              | Some k -> k
              | None -> 
                  failwith "unexpected char '%c' at position %d" s.[!i] !i
      getNextToken
  
  let tokens = 
      let nextToken = makeTokenizer input
      let t = ref(nextToken())
      [ 
          yield !t
          while !t <> EOF do
              t := nextToken()
              yield !t
      ]
  
  printfn "%A" tokens // sanity check our tokenizer works
  
  /////////////////////////////////////////////////////////////////////////
  // Parser
  
  let parseExpr toks =
      match toks with
      | NUM x :: rest ->
          let mutable rest = rest
          let mutable expr = Literal x
          while rest.Head = PLUS || rest.Head = MINUS do
              let op,y,r = 
                  match rest with
                  | PLUS::NUM y::t -> Plus, Literal y, t
                  | MINUS::NUM y::t -> Minus, Literal y, t
                  | _ -> 
                      failwith "parse error in expression, expected number"
              expr <- BinaryOp(expr, op, y)
              rest <- r
          expr, rest
      | _ -> failwith "parse error in expression, expected number"
  let rec parseStmt toks =
      match toks with
      | PRINT :: rest -> 
          let e,rest = parseExpr(rest)
          Print(e), rest
      | IF :: rest ->
          let e,rest = parseExpr(rest)
          match rest with
          | THEN :: rest ->
              let s1,rest = parseStmt(rest)
              match rest with
              | ELSE :: rest ->
                  let s2,rest = parseStmt(rest)
                  IfThenElse(e,s1,s2), rest
              | _ -> 
                  failwith "parse error after if branch, espected 'else'"
          | _ -> 
              failwith "parse error after if expression, expected 'then'"
      | _ -> failwith "parse error, expected statement"
  let parseProgram toks =
      let s,rest = parseStmt toks
      match rest with
      | [EOF] -> s
      | _ -> failwith "parse error after statement, expected EOF"
  
  let p = parseProgram tokens
  printfn "%A" p
  assert( p = goal )
  

  （希望没有令人震惊的错误 . ）

  回复于 2024-04-27T04:26:52+08:00
• 8

  Parser组合器确实很漂亮！ FParsec是一个非常光滑的monadic解析器组合库，你应该检查 . 如果你想从一些简单但仍然纯粹功能的东西开始，你可能会喜欢F＃系列中的Scheme解释器中的tokenizer / parser（我的博客）：http://blogs.msdn.com/b/ashleyf/archive/2010/09/24/fscheme-0-0-0.aspx

  回复于 2024-04-27T04:26:52+08:00
• 6

  比其他好答案更简单的答案：

  函数语言中的解析器将令牌流带入解析树和令牌流的其余部分 . 也就是说，它有类型

  token list -> ast * token list
  

  递归的正确解析器通常具有大量此类型的函数，这些函数会占用令牌流，然后构建解析树的一小部分 . 通过递归调用这些（递归正常） - 你得到你想要的 .

  下一步是使用更高阶的解析器：在其他解析器上运行的解析器 . 这就是解析器组合库所做的事情 . 也许您可以从简单的递归方案开始，然后将其升级到解析器组合器 .

  回复于 2024-04-27T04:26:52+08:00
• 6

  我已经在F＃中使用ECMAScript编译器了一段时间，所以我和你在同一条船上 . Mayhap我的一些工作可能对你有用 . 这是一个简单的解析器组合库，我一直在研究它与FParsec结合使用 . 它不是近乎完美的地方，但它应该给你一些简单的东西来学习，这样你就可以转向更高级的东西 . 如果你最终使用FParsec，你可能会注意到这里的很多东西都是受它启发的 .

  module Tools =
  
      open System
      open System.Diagnostics
      open LazyList 
  
      [<Struct;DebuggerStepThrough>]
      type State<'a, 'b> (input:LazyList<'a>, data:'b) = //'
          member this.Input = input
          member this.Data = data
  
      type Result<'a, 'b, 'c> = //'
      | Success of 'c * State<'a, 'b>
      | Failure of list<string> * State<'a, 'b>    
  
      type Parser<'a, 'b, 'c> = //' 
          State<'a, 'b> -> seq<Result<'a, 'b, 'c>>
  
      let zero<'a, 'b, 'c> (state:State<'a, 'b>) = //'
          Seq.empty<Result<'a, 'b, 'c>>
  
      let item<'a, 'b> (state:State<'a, 'b>) = seq { //'
          match state.Input with
          | Cons (head, tail) ->
              yield Success(head, State (tail, state.Data))
          | Nil -> ()
      } 
  
      let result<'a, 'b, 'c> (value:'c) (state:State<'a, 'b>) = seq  { //'
          yield Success (value, state)
      }
  
      let run p i d =
          p (State(i, d)) 
  
      let (>>=) (m:Parser<'a, 'b, 'c>) (f:'c -> Parser<'a, 'b, 'd>) (state:State<'a, 'b>) = //'
          let rec run errors = seq {
              for r in m state do
                  match r with
                  | Success (v, s) ->
                      yield! f v s
                  | Failure (ms, s) ->
                      yield! run (errors @ ms)
          }
          run []
  
      let (<|>) (l:Parser<'a, 'b, 'c>) (r:Parser<'a, 'b, 'c>) (state:State<'a, 'b>) = //'  
          let rec run p = seq {
              for result in p state do
                  match result with
                  | Success (_, _) ->
                      yield result
                  | Failure (_, _) -> ()
          }
          Seq.append (run l) (run r)
  
      type ParseMonad() =        
          member this.Bind (f:Parser<'a, 'b, 'c>, g:'c -> Parser<'a, 'b, 'd>) : Parser<'a, 'b, 'd> = f >>= g //'     
          member this.Combine (f, g) = f <|> g      
          member this.Delay (f:unit -> Parser<'a, 'b, 'c>) (state:State<'a, 'b>) = f () state //'
          member this.Return x = result x
          member this.ReturnFrom p = p
          member this.Zero () = zero
  
      let parse = ParseMonad()
  
      let (|>>) (parser:Parser<'a, 'b, 'c>) (f:'c -> 'd) = parse { //'
          let! v = parser
          return f v   
      }
  
      let satisfy predicate = parse {
          let! value = item
          if predicate value then
              return value 
      }
  
      let maybe parser = parse {
          return! parser |>> Some <|> result None 
      }
  
      let choice (ps:seq<Parser<'a, 'b, 'c>>) (state:State<'a, 'b>) = seq { //'
          if not (LazyList.isEmpty state.Input) then
              for p in ps do
                  yield! p state    
      }
  
      let between left right parser =
          parse {
              let! _ = left
              let! v = parser
              let! _ = right
              return v
          }
  
      let skip p = parse {
          let! v = p
          return ()
      }
  
      let many parser = 
          let rec many result = parse {
              let! v = parser
              let result = v::result
              return! many result
              return result    
          }
          many []
  
      let many1 parser = parse {
          let! r = many parser
          if not r.IsEmpty then
              return r
      }
  
      let manyFold parser start (f:_ -> _ -> _) = parse {
          let! r = many parser
          return r |> List.fold f start
      }
  
      let many1Fold parser start (f:_ -> _ -> _) = parse {
          let! r = many1 parser
          return r |> List.fold f start
      } 
  
      let isNotFollowedBy p =
          parse {
              let! v = maybe p
              match v with
              | Some _ -> ()
              | None -> return ()
          }
  
      let pipe2 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (f:'c -> 'd -> 'e) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              return f v1 v2
          }
  
      let pipe3 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (f:'c -> 'd -> 'e -> 'f) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              let! v3 = p3
              return f v1 v2 v3
          }
  
      let pipe4 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (f:'c -> 'd -> 'e -> 'f -> 'g) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              let! v3 = p3
              let! v4 = p4
              return f v1 v2 v3 v4
          }
  
      let pipe5 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (p5:Parser<'a, 'b, 'g>) (f:'c -> 'd -> 'e -> 'f -> 'g -> 'h) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              let! v3 = p3
              let! v4 = p4
              let! v5 = p5
              return f v1 v2 v3 v4 v5
          }
  
      let tuple2<'a, 'b, 'c, 'd, 'e> (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (f:'c * 'd -> 'e) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              return f (v1, v2)
          }
  
      let tuple3 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (f:'c * 'd * 'e -> 'f) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              let! v3 = p3
              return f (v1, v2, v3)
          }
  
      let tuple4 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (f:'c * 'd * 'e * 'f -> 'g) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              let! v3 = p3
              let! v4 = p4
              return f (v1, v2, v3, v4)
          }
  
      let tuple5 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (p5:Parser<'a, 'b, 'g>) (f:'c * 'd * 'e * 'f * 'g -> 'h) = //' 
          parse {
              let! v1 = p1
              let! v2 = p2
              let! v3 = p3
              let! v4 = p4
              let! v5 = p5
              return f (v1, v2, v3, v4, v5)
          }
  
      let createParserRef<'a, 'b, 'c> () = //'
          let dummyParser = fun state -> failwith "a parser was not initialized"
          let r = ref dummyParser
          (fun state -> !r state), r : Parser<'a, 'b, 'c> * Parser<'a, 'b, 'c> ref //'
  

  NOTE: LazyList 类型需要FSharp PowerPack .

  Example:

  and conditionalExpressionNoIn = 
      parse {
          let! e1 = logicalORExpressionNoIn
          return! parse {
              do! skip expectQuestionMark
              let! e2 = assignmentExpression
              do! skip expectColon
              let! e3 = assignmentExpressionNoIn
              return ConditionalExpressionNoIn (e1, e2, e3)
          }
          return ConditionalExpressionNoIn (e1, SourceElement.Nil, SourceElement.Nil)
      }
  

  回复于 2024-04-27T04:26:52+08:00