作爲一個純粹的學術練習,我從頭開始編寫遞歸下降解析器 - 不使用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?
真是巧合!我只是在F#中創建項目來編寫解析器!最終參考=龍書。 – 2009-10-28 20:25:53
請參閱http://stackoverflow.com/a/2336769/120163 – 2015-11-30 14:44:35