递归下降解析器和函数式编程
所以最近我一直在编写一个简单的编译器来更好地理解编译器的概念。 作为stackoverfolow的勤奋读者，似乎有一种共识，即以功能性语言编写编译器比命令式编程语言更容易。 为此，我想我会尝试杀死两只鸟，并在F＃中编写一个编译器，以便同时学习一种函数式语言并编写一个编译器。
我一直在阅读龙书，并决定从F＃手写的递归下降解析器开始。 然而，龙书几乎囊括了所有的代码样本。 例如，匹配令牌功能通过副作用来完成其重要的工作。
所以我的问题是更传统的解析功能方法（即少数副作用）是什么样子？ 我知道Haskell编译器（GHC）是用Haskell编写的，但是我希望能够更小一些，更容易理解代码示例。
其次，值得尝试和采用一种功能性的解析方法，还是真的对中间代码进行优化，以使功能性语言发光并且我还没有得到呢？ 也就是说，我是否应该通过使用命令式样在F＃中进行解析并在稍后切换到更具功能性的方法？
来自这篇博客文章的答案：
所以我的问题是更传统的解析功能方法（即少数副作用）是什么样子？
听起来就像你需要将纯粹的功能（如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等任何内容都会产生杂质。
您可能会喜欢以下我在此博客上撰写过的关于此主题的文章（note paywall）：
System.Reflection.Emit生成运行时代码”（2008年8月31日）。 功能分析的一个策略是monadic解析器组合器。 你可以在这里阅读一些关于它的内容（并且关注链接）或者使用像FParsec这样的库。 不过，如果您只是学习/启动F＃/编译器，我不推荐这种方法。
F＃的另一种方法是使用FsLex / FsYacc（在PowerPack中）。 我有点不喜欢Lex / Yacc技术，所以我也不建议这样做。
我认为你应该手工编写一个递归体面的解析器。 对于一个标记器我没有太多的感受，只是将整个文件标记为一个（n不可变的）标记list ，然后做递归下降（并利用一些模式匹配）是处理解析的好方法。 当然，你会希望使用被歧义的联合来表示解析器的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 )
（希望没有令人震惊的错误。）
解析器组合器确实很漂亮！ FParsec是一个非常漂亮的monadic解析器组合库，您应该查看。 如果你想从一些简单的功能开始，你可能会喜欢F＃系列中的Scheme解释器（我的博客）中的标记器/解析器：http://blogs.msdn.com/b/ashleyf/archive/ 2010/09/24 / fscheme-0-0-0.aspx
链接地址: http://www.djcxy.com/p/42927.html