【F#从入门到实战】12. F#库FParsec解析表达式

       欢迎大家来到【F#从入门到实战】，在这里我将分享关于F#编程语言的系列文章，带大家一起去学习和成长，并探索函数编程语言F#这个有趣的世界。所有文章都会结合示例代码和笔者的经验进行讲解，真心想把十余年的IT经验分享给大家，希望对您有所帮助，文章中也定有不足之处，请海涵！本系统文章将从F#基本语法入手，逐步通过自定义类型来实现数学表达式的各种常见解析操作，如对表达式进行求值、化简、展开、求导和求积分等。此系统博文也是了解和实现一个简易的计算机代数系统的基础。

      下面给出【F#从入门到实战】系统专题文章的目录：

【F#从入门到实战】01. F#语言快速入门 
【F#从入门到实战】02. F#数组常见用法   
【F#从入门到实战】03. F#自定义操作符 
【F#从入门到实战】04. F#5.0新特征总结 
【F#从入门到实战】05. F#表达式求值     
【F#从入门到实战】06. F#表达式化简    
【F#从入门到实战】07. F#表达式展开    
【F#从入门到实战】08. F#大整数阶乘    
【F#从入门到实战】09. F#表达式求导   
【F#从入门到实战】10. F#表达式积分   
【F#从入门到实战】11. F#库FParsec入门  
【F#从入门到实战】12. F#库FParsec解析表达式   
【F#从入门到实战】13. F#库FParsec实现求导符号计算   
【F#从入门到实战】14. F#实现分部积分法   

     下面将正式开始本文的介绍： 

    上一篇我们介绍了F#FParsec入门，其中给出了具体的示例，来说明如何解析浮点类型的值，解析括号中的值等，如果感兴趣的可以回到这篇博客进行阅读。本次将用讲解F#解析器库FParsec对数学公式的解析，并结构化输出构成AST。

     首先，我们定义一个数学公式这个领域的自定义类型：

type Expr = 
      | CstF of float
      | Var of string
      | Add of Expr * Expr  // +
      | Sub of Expr * Expr // -
      | Mul of Expr * Expr // *
      | Div of Expr * Expr // / 
      | Pow of Expr * Expr // ^ 
      | Sin of Expr  
      | Cos of Expr 
      | Exp of Expr 
      | Ln of Expr 

     其中的Expr是定义的数学表达式类型，其中由多个元素构成，比如 CstF of float表示浮点类型的数值，Var of string则表示文本类型的变量，Add of Expr * Expr表示数学的加法操作，其中左边可以是一个Expr类型，右边也可以是一个Expr类型。此程序属于模块：

module Yd.ExpParser.Ast

     如果要使用FParsec，则需要引入此库的命名空间：

open FParsec

    然后，需要用内置的浮点类型解析器，文本类型的解析器等构建一些工具方法：

//忽略空白字符
let ws = CharParsers.spaces
//忽略特定字符并忽略末尾的空白字符
let ch c = CharParsers.skipChar c >>. ws
//解析浮点类型的值，忽略末尾的空白字符，并转换成 CstF 类型
let num = CharParsers.pfloat .>> ws  |>> (fun x -> CstF x)
//变量标识符规则
let identifier =
        let isIdentifierFirstChar c = isLetter c || c = '_'
        let isIdentifierChar c = isLetter c || isDigit c || c = '_'  
        many1Satisfy2L isIdentifierFirstChar isIdentifierChar "identifier"
//忽略空白
let identifierws =  spaces >>.  identifier  .>> spaces 
//变量解析
let id = identifierws
      |>>(fun x -> Var x)
      .>>ws

     其次，创建操作符解析器

//创建一个新的具有优先级的操作符解析器
let opp = new OperatorPrecedenceParser<_,_,_>()
//重命名表达式解析器ExpressionParser，方便调用
let expr = opp.ExpressionParser
//括号中提取表达式
let bra_expr = ch '(' >>. expr .>> ch ')'
// 定义支持的术语terms，即操作符外的类型解析器
//id表示变量解析器，num表示浮点类型解析器，bra_expr表示表达式解析器
let terms = choice[ id; num; bra_expr]
opp.TermParser <- terms

     再次，需要定义操作符解析器的优先级类型：

opp.AddOperator(InfixOperator("+", ws,1, Associativity.Left, fun x y -> Add(x, y)))
opp.AddOperator(InfixOperator("-", ws,1, Associativity.Left, fun x y -> Sub(x, y)))
opp.AddOperator(InfixOperator("*", ws,2, Associativity.Left, fun x y -> Mul(x, y)))
opp.AddOperator(InfixOperator("/", ws,2, Associativity.Left, fun x y -> Div(x, y)))
opp.AddOperator(InfixOperator("^", ws,3, Associativity.Left, fun x y -> Pow(x, y)))

opp.AddOperator(PrefixOperator("sin", ws,4, true, fun x  -> Sin(x)))
opp.AddOperator(PrefixOperator("cos", ws,4, true, fun x  -> Cos(x)))
opp.AddOperator(PrefixOperator("exp", ws,4, true, fun x  -> Exp(x)))
opp.AddOperator(PrefixOperator("ln", ws,4, true, fun x  -> Ln(x)))

opp.AddOperator(PostfixOperator("!", ws,5, true, fun x  -> Factorial(x)))

    其中的Associativity.Left代表左结合性。下面给出最终的解析函数：

//忽略空白
let expr_ws = ws >>. expr .>> ws
//调用run方法调用字符解析器
let parse s = CharParsers.run expr_ws s

   最后，给出测试示例：

let test () =
    //测试用例
    printfn "%s => %A" "1.0+2.0+a" (parse "1.0+2.0+a")
    printfn "%s => %A" "(x + 1.0) * 2.0"  (parse "(x + 1.0) * 2.0")
    printfn "%s => %A" "(x + 2) * y / 3.2"  (parse "(x + 2) * y / 3.2")
    printfn "%s => %A" "(x+2)^7"  (parse "(x+2)^7")
    printfn "%s => %A" "sin( x + 2) + 3 "  (parse "sin( x + 2) + 3 ")
    printfn "%s => %A" "sin( x + 2) + cos(x * 2)"  (parse "sin( x + 2) + cos(x * 2)")
    printfn "%s => %A" "2+exp(3*y)"  (parse "2+exp(3*y)")
    printfn "%s => %A" "2+ln(7*x)"  (parse "2+ln(7*x)")
    printfn "%s => %A" "(7*x)!+2"  (parse "(7*x)!+2")

    运行后，结果如下：

1.0+2.0+a => Success: Add (Add (CstF 1.0, CstF 2.0), Var "a")
(x + 1.0) * 2.0 => Success: Mul (Add (Var "x", CstF 1.0), CstF 2.0)
(x + 2) * y / 3.2 => Success: Div (Mul (Add (Var "x", CstF 2.0), Var "y"), CstF 3.2)
(x+2)^7 => Success: Pow (Add (Var "x", CstF 2.0), CstF 7.0)
sin( x + 2) + 3  => Success: Add (Sin (Add (Var "x", CstF 2.0)), CstF 3.0)
sin( x + 2) + cos(x * 2) => Success: Add (Sin (Add (Var "x", CstF 2.0)), Cos (Mul (Var "x", CstF 2.0)))
2+exp(3*y) => Success: Add (CstF 2.0, Exp (Mul (CstF 3.0, Var "y")))
2+ln(7*x) => Success: Add (CstF 2.0, Ln (Mul (CstF 7.0, Var "x")))
(7*x)!+2 => Success: Add (Factorial (Mul (CstF 7.0, Var "x")), CstF 2.0)

    控制台打印结果如下：