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

Question

最近我一直在编写一个简单的编译器来更好地理解编译器概念.作为stackoverfolow的勤奋读者,似乎有一种共识,即在函数式语言中编写编译器比命令式编写器更容易.为此,我想我会尝试杀死两只鸟,并在F#中编写一个编译器来学习一种函数式语言并同时编写一个编译器.

我一直在阅读龙书,并决定从F#手写的递归下降解析器开始.然而,龙书几乎所有的代码样本都是命令式的.例如,匹配令牌功能通过副作用完成其工作的重要部分.

所以我的问题是什么是更传统的解析功能方法(即几个副作用)看起来像什么？我知道Haskell编译器(GHC)是用Haskell编写的,但我希望能够理解一些更小,更容易理解的代码示例.

第二,尝试采用功能性方法进行解析是否值得,或者它是否真的在对功能语言闪耀的中间代码进行优化,而我还没有到达那里？也就是说,我是否应该使用命令式样式在F#中进行解析并稍后切换到更具功能性的方法？

Answer 1

来自此博客文章的答案:

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

听起来你需要将功能(如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这样的杂质.

您可能会欣赏我在此博客上撰写的有关此主题的以下文章(注意付费专区):

• "用Lex和Yacc解析文本"(2007年9月30日).
• "优化简单的字节码解释器"(2007年10月31日).
• "Parser combinators"(2007年11月30日).
• "面向语言的编程:术语级解释器"(2007年12月31日).
• "面向语言的编程:术语重写"(2008年8月16日).
• "使用运行时代码生成System.Reflection.Emit"(2008年8月31日).
• "解析和可视化二进制地理信息系统数据"(2009年11月30日).

Answer 2

功能解析的一种策略是monadic解析器组合器.你可以在这里阅读一些(并按照链接)或使用像FParsec这样的库.但是,如果您只是学习/启动F#/编译器,我不推荐这种方法.

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

我认为你应该手工编写一个递归的正确解析器.我对标记化器没有强烈的感觉,只是简单地将整个文件标记为(n个不可变的)list标记,然后进行递归下降(并利用一些模式匹配)是处理解析的好方法.当然,你会想要使用discrimated unions来表示解析器的AST输出(这里是la ).

我很久没看过龙书,但我显然是这个星球上唯一一个不喜欢它的人.我会考虑放弃该文本,转而讨论使用基于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 )

(希望没有令人震惊的错误.)

Answer 3

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

Answer 4

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

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

 token list -> ast * token list

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

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