トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

構文解析

[プログラミング言語作成]

構文解析

ビジュアル構文解析 から、構文解析方法の一覧を拝借。

  演算子順位構文解析

  • 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
    • 先読みオートマトンの動的構築
お名前: コメント: