Pratt構文解析
Vaughan Prattによる論文"Top Down Operator Precedence"(1973)
> とてもシンプルで理解しやすく、実装も容易で、使いやすく、理論上はともかく区実用上は非常に効率的であり、それでいて、利用者の殆どの合理的な構文に耐えられるほど柔軟である
構造体などは利用していない
用語の違い
nuds (null denotations): prefixParseFn
leds (left denotations): infixParseFns
演算子やオペランドを表現すること自体は難しいわけでなく、難しいのは優先順位のある記号の扱い方
Top Down Operator Precedence
ダグラス・クロックフォードがJSに移植したもの
Top Down Operator Precedenveを用いたパーサ
日本語では「下向き演算子順位解析」
演算子順位解析
あるトークンタイプに遭遇するたびに、対応する構文解析関数を呼ぶ
トークンタイプごとに最大2つの構文解析関数が関連付けられる
構文解析関数の種類
前置構文解析関数(prefix parsing function)
中置構文解析関数(infix parsing function)
中置演算子の左側の値のASTを引数に取る
そもそも構文解析では、符号(?)の優先度を比較する必要がある
PrattではPrefixとInfixの2つのパターンにわけて優先度を付けて構文解析する
nimproc tokenToPrecedence(tok: Token): Precedence =
case tok.Type
of EQ, NOT_EQ: return Precedence.Equals
of LT, GT: return Precedence.Lg
of PLUS, MINUS: return Precedence.Sum
of SLASH, ASTERISC: return Precedence.Product
else: return Precedence.Lowest
他のParserとの比較
使われているところ
JSLint
Douglas Crockford作
実装
Rust
参考