如何从零开始编写递归下降解析器？

Question

作为纯粹的学术练习，我正在从零开始编写一个递归下降解析器 -- 不使用ANTLR或lex/yacc。

我正在编写一个简单的函数，将数学表达式转换为它们等效的AST。 我有以下代码：

// grammar
type expr =
    | Lit of float
    | Add of expr * expr
    | Mul of expr * expr
    | Div of expr * expr
    | Sub of expr * expr

// tokens
type tokens =
    | Num of float
    | LParen | RParen
    | XPlus | XStar | XMinus | XSlash

let tokenize (input : string) =
    Regex.Matches(input.Replace(" ", ""), "\d+|[+/*\-()]")
    |> Seq.cast<Match>
    |> Seq.map (fun x -> x.Value)
    |> Seq.map (function
        | "+" -> XPlus
        | "-" -> XMinus
        | "/" -> XSlash
        | "*" -> XStar
        | "(" -> LParen
        | ")" -> RParen
        | num -> Num(float num))
    |> Seq.to_list

所以，tokenize "10 * (4 + 5) - 1" 返回以下标记流：

[Num 10.0; XStar; LParen; Num 4.0; XPlus; Num 5.0; RParen; XMinus; Num 1.0]

此时，我想根据运算符优先级将令牌流映射到其AST。

Sub(
    Mul(
        Lit 10.0
        ,Add(Lit 4.0, Lit 5.0)
       )
    ,Lit 1.0
   )

然而，我一片空白。我从未从头开始编写解析器，也不知道如何开始。

如何将令牌流转换为其表示的AST？

- Juliet

---

真巧！我刚好在创建一个用 F# 编写解析器的项目！《龙书》是终极参考书。 - Mehrdad Afshari

请参见https://dev59.com/v3E95IYBdhLWcg3wlu6z#2336769。 - Ira Baxter

Answer 1

您知道语言语法吗？

如果是的话，您应该知道语法有一些规则，例如：

...
addTerm := mulTerm addOp addTerm
         | mulTerm

addOp   := XPlus | XMinus

mulTerm := litOrParen mulOp mulTerm
         | litOrParen
...

最终会变成像这样的代码（在浏览器中编写代码，从未编译）。

let rec AddTerm() =
    let mulTerm = MulTerm() // will parse next mul term (error if fails to parse)
    match TryAddOp with  // peek ahead in token stream to try parse
    | None -> mulTerm    // next token was not prefix for addOp rule, stop here
    | Some(ao) ->        // did parse an addOp
         let rhsMulTerm = MulTerm()
         match ao with
         | XPlus -> Add(mulTerm, rhsMulTerm)
         | XMinus -> Sub(mulTerm, rhsMulTerm)
and TryAddOp() =
    let next = tokens.Peek() 
    match next with
    | XPlus | XMinus ->
        tokens.ConsumeNext()
        Some(next)
    | _ -> None
...

希望您能理解基本思路。这假设存在一个全局可变的令牌流，允许同时进行“查看下一个令牌”和“消耗下一个令牌”的操作。

- Brian

Answer 2

如果我记得大学课程上的理念是要构建表达式树，类似于：

<program> --> <expression> <op> <expression> | <expression>
<expression> --> (<expression>) | <constant>
<op> --> * | - | + | /
<constant> --> <constant><constant> | [0-9]

然后，一旦您完全构建了树形结构，您将得到类似以下的内容：

            exp
       exp   op     exp
    5        +       and so on

然后你将完成的树运行到另一个程序中，该程序递归地进入树中计算表达式，直到得出答案。如果你的解析器不理解这棵树，那么就会出现语法错误。希望这可以帮到你。

- Chad