構文解析
- Go言語でつくるインタプリタ で構文解析方法についてかじったので、調査の幅を広げてみる
演算子順位構文解析
- Shunting-yard algorithm ← ダイクストラ法のダイクストラが発表w!
- トークンを演算子の種類ごとにスタックに積んで優先度をつける
- Pratt parsing ← Go言語のインタプリタで紹介されてるPratt
- トークンを演算子の種類ごとに再帰的に木構造に追加して処理する
上向き構文解析
- LR parsing
- 決定性有限オートマトン
- GLR parsing
- 非決定性有限オートマトン
- Earley parsing
- CYK algorithm
- Valiant parsing
- 行列積
下向き構文解析
- LL(k) parsing
- k文字先読み
- Packrat parsing
- Packrat parsing with left recursion
- 強欲マッチ
- GLL parsing
- グラフ構造継続
- Adaptive LL(*) parsing
- 先読みオートマトンの動的構築