作りながら学ぶパーサジェネレータ入門 0

はじめに

こんにちは。@junk0612です。これは、パーサジェネレータに興味があるけど難しくてよくわからないという方向けに、パーサジェネレータに関連する内容をある程度の粒度で分割し、1つずつ手を動かしながら学べるようにすることを目指した文章です。以下の内容で進むことを想定しています。

  1. 言語と文法
  2. 構文木
  3. 字句解析・レキサの生成
  4. オートマトンの作成
  5. 構文解析表の計算
  6. パーサの生成
  7. 発展的な内容

作るもの

この文書で作成するものの詳細です。これは「分かる人」向けの説明ですので、この節に書いてあることがなんとなく分かる方はこの文書の想定読者ではないかもしれません。

  • 生成するパーサのアルゴリズムは LR(0)
  • Reduce-Reduce Conflict は解消しない。ぶら下がり else 問題を解消するため、Shift-Reduce Conflict は常に Shift に解決する
  • 文法ファイルのようなものは作らず、文法の記述は Ruby のコードとして行う
  • 生成されるパーサは入力の構造を表示するだけとし、アクションは実装しない
  • レキサの生成も実装しない。入力を String#chars で区切ったものをトークンとする

取り扱う言語

この文書では、例として「非負整数」を解析するパーサを生成するパーサジェネレータを開発します。言語は自由に変更できるようなプログラムを書きますが、パーサ生成のアルゴリズムが貧弱なため、期待通りに動くパーサが生成できないことも多いでしょう。そのときには、発展的な内容に含まれるより強力なアルゴリズムを使うか、言語の一部を修正するか、諦めて例に戻るかが現実的な選択肢です。

想定する読者

この文書では、以下のような読者を想定しています。

  • パーサ・パーサジェネレータについて興味はあるが、あまり知識はない
    • 構文木とかいうデータを作ってくれるプログラム、というざっくりとした理解があれば十分です
  • オブジェクト指向および Ruby のプログラミングについてある程度の知識がある
    • パーサジェネレータは Ruby で書きますが、言語仕様について詳しい説明はしません。Ruby 特有の機能をいくつか使用するので、他言語で実装する際には工夫が必要かもしれません。