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つのパターンにわけて優先度を付けて構文解析する

code:nim

proc 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

参考