sora

前言#

トークナイザーの構築手順については詳しく述べませんが、リポジトリ内のトークナイザーを参照するか、他のタイプのものを自分で作成して、トークナイザーが返すトークンとパーサー内のトークン（ここではSymbolクラスのインスタンス）が接続できるようにすれば大丈夫です。

このプロジェクトはドラゴンブック [1] に基づいて実装されており、Parser 内のかなりの部分の詳細はドラゴンブックに対応する部分が見つかるので、例としてドラゴンブックの理解を助けることができます。

このプロジェクトは Python 言語を使用しています。なぜなら、Python の自由度により、プログラムのロジックの実装に最大限集中でき、文法の細かい部分に煩わされることがなく、アイデアを実践するのに非常に適しているからです。また、型注釈を利用して静的チェックを実現できます。将来的にパフォーマンスが要求される場合は、これを基に C++ バージョンのプログラムを構築することも可能です。

最後に、こんなに難しい実験課題を出してくれた授業の先生に感謝します。そうでなければ、こんなことをすることは思いつかなかったでしょうし、約 1 週間ほど夢中になって取り組むこともなかったでしょう。

路線#

準備#

開発環境は Windows 11 + Jetbrains Pycharm + Python 3.9

• 使用する新しいバージョンの Python の特徴は以下の通りです:
  • Python 3.6 以降、組み込み型dictの挿入が順序付きになり、項集族を明確に印刷するために使用されます。
  • Python 3.7 以降でサポートされているfrom __future__ import annotationsの使用法は、型注釈に使用され、クラスの定義順序を緩和し、後で定義されたクラスを前で型注釈として使用できます。
• プログラミング習慣：
  • 定数はできるだけ統一されたファイルに置くようにし、魔法の数字や魔法の文字列を避ける。
  • 型注釈を多く使用し、変数の型を明確にし、静的なエラーを排除する。
  • クラス内でdebug_modeスイッチを定義し、デバッグ情報を印刷する。
  • ユニットテストを行う。
    • コード内の単体テストはtester.pyを参照。
• 外部メインプログラム main.py からデバッグするには？
  • 外部メインプログラムにcreate_cfgメソッドを実装し、その中で文脈自由文法を定義および変更する。
  • テスト用のプログラムテキストを準備する（例：test.c）。
    • サンプル CFG 文法は test.c 内のc_generatorsを参照。
  • Tokenizer インスタンスを定義し、すべてのトークンを読み込む。
  • Parser インスタンスを定義し、デバッグモードを開き、構造を初期化する。
  • Tester インスタンスを使用してテストプロセスをカプセル化することができる。
  • 出力を観察および分析し、実装を調整し続ける。
    • 確認のために、出力をファイルにリダイレクトすることができる。

シンボル、生成規則、項、項集などのモデリング#

シンボル、生成規則、項、項集などのモデリングはgrammar.pyファイルにあります。

• 文法シンボル -> Symbolクラス
  • メンバー変数
    • sType: トークンのタイプ
      • 終端シンボルと非終端シンボルの 2 つのカテゴリに分類。
    • name: トークンのタイプ
      • 数値定数、識別子などに分類。
      • 例えば、識別子に対応するnameはconstants。
    • content: トークンの文字列表現
      • 例：int a;の中でaは識別子型で、属性nameは "constants"、属性contentは "a"。
  • メンバー関数
    • __str__：文字列表現に変換し、印刷を容易にする。
    • __hash__と__eq__：集合型の使用を容易にする。
    • fromStr: str型からSymbol型に変換し、外部で終端シンボルセットを指定する必要がある。
  • 空シンボルはどう表現するか？
    • constants.pyに定数を定義し、εで表す。
    • Symbol型またはstrで定義することができる。
• 生成規則 -> Generatorクラス
  • メンバー変数
    • start：生成規則の左側の非終端シンボル。
    • end: 生成規則の右側の文法シンボル列。
  • メンバー関数
    • __str__：文字列表現に変換し、印刷デバッグを容易にする。
  • ComposedGeneratorは何のためにあるのか？
    • 手動で CFG 文法を定義する際、文字列を書く方がSymbolを定義するよりもはるかに便利なので、ComposedGeneratorで変換の層を作成した。
    • また、同じ生成規則の左側が複数の生成規則の右側に対応する場合（例：A -> a | b）、ComposedGenerator内のメンバーendの型注釈はlist[list[str]]となり、"Composed" を示す。
      • 例：A -> a | b
        • ComposedGeneratorとして定義すると{start: 'A', end: [['a'], ['b']]}。
        • Generatorに変換すると 2 つのGenerator型のインスタンスが得られる。
          • {start: 'A', end: ['a']}
          • {start: 'A', end: ['b']}
• LR (1) 項 -> Itemクラス
  • メンバー変数
    • start: 生成規則の左側の非終端シンボル。
    • end: 生成規則の右側の文法シンボル列。
    • point: 生成規則内の点、読み込まれた位置を示す。
    • lf_symbols: 前方参照のシンボル、LR (1) は 1 つだけ見る。
  • メンバー関数
    • __hash__と__eq__：インスタンスを区別し、集合型の使用を容易にする。
    • __str__：文字列表現に変換し、印刷を容易にする。
      • ここでは生成規則が空である場合を特別に扱っている。
• LR (1) 項集 -> ItemSetクラス
  • メンバー変数
    • _items：すべての項。
  • メンバー関数
    • add：項を項集に追加し、重複は自動的に無視される。
    • union：他のItemSet型と統合する。
    • toList: リストに変換する。
      • 後続の LR オートマトンの状態を数字でインデックスするのに便利。
    • __hash__と__eq__：インスタンスを区別し、集合型の使用を容易にする。
    • __iter__: 内部イテレータを返し、forループでの反復に使用する。
    • __len__: サイズを返す。
      • Sizedを継承する必要がある。
  • なぜ項集をモデリングする必要があるのか？set(Item)を直接使用することはできないのか？
    • いい質問です、最初は私もそう思いました。
    • 問題は LR (1) 標準項集族を求めるときに発生します。
      • 新しい項集が追加されていないかを判断する必要があり、最初の反応はset(Item)の外側にもう一層重ねること、set(set(Item))です。
      • しかし、set(Item)には偏序と等価のデフォルト定義がなく、複合型です。
        • "複合型" についてはプログラミング原本 [2] 第十二章を参照。
      • したがって、項集のために手動で偏序と等価を定義する必要があります。
    • また、印刷デバッグなどの要件があるため、項集をモデリングする必要があります。
• 文脈自由文法 (CFG) -> GrammarCFGクラス
  • start_mark: 開始シンボルのリテラル。
  • end_mark: 終端シンボル。
    • 一般的にはスタックの底の '$'。
  • end_symbols: 終端シンボルの集合。
  • generators: 生成規則の集合。
    • ここから非終端シンボルの集合を得ることができる。

FIRST 集合と FOLLOW 集合の求め方の実装#

このステップから Parser の実装を開始し、対応する参考実装はparser.pyにあり、対応するドラゴンブックのページ番号はコードに詳細な注釈があります。

• 参考コード中の関連関数
  • get_first
  • get_chain_first（文法シンボル列の first を求める）
  • get_follow
  • _get_follow_once
  • _get_follow_all
• 参考コード中の関連メンバー変数
  • self._map_follow
  • self._map_first
• なぜ最初に first 集合と follow 集合を求めるのか？
  • first 集合と follow 集合を求めることは後続のアルゴリズムの基礎です。
  • さらに、文法をモデリングしているので、ドラゴンブックのプロセスに従って実装すればよく、文法シンボルと生成規則に関わるだけです。
  • 簡単な操作から始めて、繰り返しデバッグすることで、プログラミングの状態を徐々に見つけることができます。
• どのように求めるべきか？
  • first 集合を求めるのに特に問題はなく、関数の呼び出しプロセスは木構造です。
    • 例えば：A -> B と B -> bの場合、
      • first(A)を求めるためにfirst(B)を呼び出します。
      • first(B)を求めると{b}が得られます。
  • しかし、follow 集合を求める場合、関数の呼び出しプロセスには環があります。
    • 例えば：A -> aB と B -> bA | bの場合、
      • follow 集合の第三のルールに基づいて、
      • follow(A)を求めると、follow(A)はすべてfollow(B)にあります。
      • follow(B)を求めると、follow(B)はすべてfollow(A)にあります。
    • 参考実装の解決方法は比較的単純で粗暴です。
      • すべての非終端シンボルの follow 集合を事前に計算し、dictに保存してグローバル変数self._map_followにします。
      • すべての非終端シンボルの follow 集合をスキャンし続け、新しい終端シンボルが追加されなくなるまで繰り返します。
        • 判断方法は、例えば 2 つの非終端シンボルの follow 集合を統合し、lenに変化があるかどうかを確認するなどです。
    • より良い実装を探してみることができます。

CLOSURE と GOTO の求め方の実装#

first 集合と follow 集合を求めるツールができたので、次のステップは LR (1) 項に関連するアルゴリズムに取り組むことができます。対応する参考実装はparser.pyにあり、対応するドラゴンブックのページ番号はコードに詳細な注釈があります。

• 参考コード中の関連関数
  • get_closure
  • get_goto
• 書籍で言及されていない部分は？
  • 依存順序に従って、まず closure を実装し、その後 goto を実装します。
  • closure 集
    • 重複を避けることに注意が必要です。
    • 一度の遍歴で新しく追加された項を別に保存し、次回は新しく追加された項だけを遍歴します。
    • 新しく追加された項を最後に加えることに注意し、イテレータの無効化を防ぎます。
    • 参考コード中の私の実装は非常に劣っており、今思うと偶然動いているだけで、当時酔っていた可能性があるため、参考にしないことをお勧めします。
  • goto 集には特に問題はありません。
    • 次のシンボルが X で、点を移動させるだけで追加できます。
    • 最後に closure を求めて返します。

LR (1) 項集の求め方の実装#

拡張文法の最初の生成規則から closure を求め始め、goto ができたので LR (1) 項集を求めることができます。goto を求め続け、新しい項集が追加されなくなるまで繰り返します。対応する参考実装はparser.pyにあり、対応するドラゴンブックのページ番号はコードに詳細な注釈があります。

• follow 集合を求めるのと似た方法で「新しい項集が追加されていない」ことを判断できます。
• 参考コード中の関連関数
  • get_lr1_items
• このステップを順調に完了すると、goto のプロセスを印刷し、各項集を状態として見ることで、実際に LR (1) 項集のオートマトンを完成させたことがわかります。このステップで既に成功の半分を達成しています。

LR (1) の解析表の実装#

• 参考コード中の関連関数
  • get_lr
• 必要なこと
  • アクションをモデリングし、解析表に埋め込む内容とする。
    • メンバーには以下を含める必要があります。
      • 実行するアクションのタイプ。
      • アクションを実行するために必要な情報。
        • 例えば：
          • どの生成規則を使って還元するか。
          • 次にどの状態に進むか。
  • LR (1) 解析表をモデリングし、1 つずつ埋め込む。
    • 対応するLRSheet。
    • 一次元は状態のインデックス、一次元はシンボル。
  • 標準 LR (1) 項集族をすべての状態として使用する。
• 参考コードのようにルールに従ってアクションを 1 つずつ埋め込むことも、まとめてアクションを埋め込むこともできます。
• 埋め込む過程で 1 つのセルに 2 回埋めた場合は？
  • 実装にエラーがあります。
  • 文法が LR (1) 文法ではありません。
• その他
  • 参考コード中、空生成規則の還元はエラー後にスタックのトップに空シンボルを試して置くことで実現されています。

LR (1) の構造の実装#

• 構造をモデリングする。
  • すべての入力が既知であると仮定する。
  • ここでは 158 ページ [1] の定義に厳密には従っていません。
  • スタック内の入力と残りの入力に加え、スタック内の状態インデックスもあり、下から上への処理過程をデバッグおよび観察しやすくします。
  • 参考コード中では、1 ステップのアクションを実行することも構造に組み込まれており、状態を印刷しやすくしています。
• このステップで基本的に完成します。

簡単な SDD 構文導出解析の追加#

ここでの SDD は S 属性の SDD に限られ、create_cfg()内で再帰的なサブルーチンの形式で定義され、アクションが生成規則の還元操作のときにのみトリガーされます。生成規則の中間やアクションが移入操作のときにトリガーされるように自分で修正してみることができます。

• SDD を追加するための手順は以下の通りです：
  • Symbol などのモデリングを拡張し、さまざまな意味属性を持たせる。
  • 簡単な型宣言を実装する。
  • 簡単な式評価を実装する。
  • 簡単な型チェックルールを実装する。
  • 制御フローの SDD を実装する。
• 注意
  • Python 内部ではオブジェクトは浅いコピーであるため、forwardで意味アクションを実行する前に深いコピーを行い、他のSymbolインスタンスの SDD を上書きしないようにします。
• どのように拡張するか？
  • 再帰的なサブルーチンの形式を定めます。例えば：
    • パラメータリストはすべて(input_symbols: list[grammar.Symbol], reduction_symbol: grammar.Symbol, st: parser.SymbolTable)。
    • 属性の名前をconstants.pyで定義します。
      • これは定数を統一して定義する利点を反映しています。
      • リテラルを何度も手打ちする必要がなく、誤字が発生しやすく、予期しないバグを引き起こす可能性があります。
  • 各生成規則を定義する際に、関数を再帰的なサブルーチンとしてバインドします。
  • Itemクラスにもこのパラメータを追加します。
  • Parser クラスのさまざまなメソッドで新しいItemインスタンスを作成する際に、バインドされた関数も一緒に渡します。
  • forwardで 1 ステップの還元アクションを実行する際に意味アクションを実行します。
  • 詳細は参考コードの Git 差分を参照してください。

存在する問題#

• モデリングの初期段階でSymbolの等価性の問題を十分に考慮しなかった。
  • 例えば：aとbは生成規則内でどちらもidentifierであるため、それらを比較すると等しい結果が得られる。
  • 最終的には生成規則内の表現のみを比較し、文字列の内容は比較しないことにした。
• なぜsTypeとnameの 2 つが分かれているのか？両方ともトークンタイプを表しているのに、統合するのは良くないのか？
  • 当初、これら 2 つを分けたのはインターフェースとの接続の問題があったため。
  • トークナイザー部分のタイプは終端シンボルと非終端シンボルに分けられておらず、5 つのカテゴリに細分化されていた。
  • 最後に外部で CFG 文法を定義する際に再度終端シンボルと非終端シンボルに分けたため、処理が確かに良くなかった。トークナイザーで分けるべきだった。
• Parser 内部のいくつかの関数は公開されている。
  • 単体テストを容易にするためだが、あまり整然としていない。
• if-elseの処理がうまくいっておらず、特別な空の else を使用している。
  • 実際には文法定義で解決できるため、ドラゴンブック 134 ページを参照。
• 真のパニックモードを実装しておらず、必要なトークンが現れるまで単に捨てているだけ。
• 実装の効率性の問題を考慮していない。
  • 例えば、follow 集合と LR (1) 標準項集族を求める際、新しい項または項集が追加されていないかを判断する操作は非常に単純で粗暴である。
• SDD、三アドレスコードの実装が不規則。
• constants.pyと外部のcreate_cfgの結合度が高い。
• ItemSetは変更後のハッシュを求める問題を十分に考慮していない。
• closure を求める際の重複排除の実装が良くない。
  • 例えば、cur_itemsを使用して重複を排除するのではなく、f_listを使用して重複を排除している。
  • f_listは前方参照のシンボルと生成規則の右側を混在させており、潜在的なバグがある。

参考資料#

• [1] コンパイラ原理 第 2 版（Compilers: Principles, Techniques and Tools, Second Edition）、（米）Alfred, V.A. など著；赵建华など訳、—— 北京：機械工業出版社、2009.1
• [2] プログラミング原本（Elements of Programming）、（米）Stepanov, A.、（米）McJones, P. 著；裘宗燕訳。—— 北京：機械工業出版社、2011.12