如何从头开始编写递归下降解析器？
作为纯粹的学术练习，我从头开始编写递归下降解析器 - 而不使用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？
你知道语言语法吗？
假设是的，你有一个语法规则
...
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
...
希望你看到基本的想法。 这假设一个全局可变的标记流，允许'偷看下一个标记'和'消耗下一个标记'。
如果我从大学课程中记得，这个想法是建立表达树，如：
<program> --> <expression> <op> <expression> | <expression>
<expression> --> (<expression>) | <constant>
<op> --> * | - | + | /
<constant> --> <constant><constant> | [0-9]
那么一旦你完全建造你的树，所以你得到像这样的东西：
exp
exp op exp
5 + and so on
然后通过递归下降到树计算表达式的另一个程序来运行完成的树，直到获得答案。 如果您的解析器不理解树，则会出现语法错误。 希望有所帮助。
链接地址: http://www.djcxy.com/p/63197.html