daisuzz.log

"コンピュータシステムの理論と実装 第9章 高級言語, 第10章 コンパイラ:構文解析" を読んだ

「コンピュータシステムの理論と実装」を読んだメモを書いていきます。

前回は↓

iikanji.hatenablog.jp

メモ

第9章

高水準言語

  • 今までの章は人が直接読み書きすることを想定していないレイヤ
  • 以降の章でJackコンパイラの実装とJackを使ったOSの実装を行う
  • Jack
    • オブジェクトベースの言語
    • コンパイラの実装の難易度を下げるため、弱い型付けを採用していたり、演算子の優先順位をあえて考慮していない
    • 文のパース処理を考えたときに、文の最初のトークンによって処理の内容が理解できる仕様の方がコンパイラを実装しやすいためJack言語では式を除いた構文はLL(1)文法になっている

第10章

コンパイル

  • 変換元の言語で書かれたプログラムを目的の言語で書かれたプログラムに変換する
  • 大きく2つのステップ
    • 構文解析
      • 変換元のプログラムの構文を理解して、プログラムの意味を理解すること
    • コード生成
      • 理解したプログラムの意味を、目的の言語のプログラムに書き直すこと

コンパイラ

  • 構文解析
    • tokenizer
      • 字句解析(lexical analysis, scanning, tokenizing)を行う
      • ソースコード中の文字の集まりを意味をもつ最小のコード単位(トークン)に変換する
    • parser
      • トークンのまとまりを言語の構文規則(文脈自由文法)に適合させて、構文構造を理解する
      • 文脈自由文法
        • ある言語の構文要素がより単純な要素からどのように構成されるか、を指定したルールの集合
      • 終端要素
      • 非終端要素
        • トークンの部分集合から構成されるより高水準な構文要素
      • 構文解析
        • 文法が、入力されたソースコードを正しいものとして受理するかどうかを確認する作業
        • 文法規則は階層構造になっているため、parserよって生成されるデータ構造は木構造になる
        • parserが生成するデータは構文木, 導出木と呼ばれる
        • 構文解析によって、入力されたソースコード全体の構文構造がわかる
        • コンパイラによってはコード生成やエラーチェックにも利用される
      • 再帰下降構文解析
        • 構文木を構築するためのアルゴリズムの一つ
        • 文法に記述された階層化された構文を用いて、トークンの列に対して再帰的に構文解析を行う
        • 非終端要素が終端要素だけで構成されている場合は終端要素を文法に沿って出力
        • 非終端要素が非終端要素を含む場合は非終端要素をパースするルーチンを再帰的に呼び出す
      • LL(1)文法
        • 非終端要素の種類を特定する場面において選択肢が複数ある場合に、最初のトークンから非終端要素の種類を決定することができる性質
        • 最初のトークンだけでは非終端要素の種類を決定できない場合は、次のトークンを先読みして解決する
    • 構文解析器は一般的にLEXやYACCなどのコンパイラ生成器を使ってtokenizerやparserを作る
  • コード生成器
    • 次章で実装

実装

Jackで書かれたプログラムに対して字句解析と構文解析をおこなって、構文木xmlの形式で出力するコンパイラをKotlinで実装する。 まず、字句解析を行うモジュールを実装し、その後構文解析を行うモジュールを実装する。 実装したソースコードは以下。

github.com

感想

字句解析を行ってトークンの出力を行うモジュールは比較的簡単に実装できたが、Jackの構文に沿ってトークンを解析するモジュールの実装に時間がかかってしまった。Jackの式は先頭のトークン1つだけで構文が決定するLL(1)文法ではないため、トークンの先読みの結果で処理を分岐する箇所の実装に少し時間がかかってしまった。また、セミコロンや閉じカッコなどの末尾の終端要素がない構文をパースする際に、トークンの読み込み処理が一つずれてしまって期待する出力が得られないというバグが頻発してしまい、デバッグに時間がとられ、実装の終了までに時間がかかってしまった。

この辺は学生の頃に、コンパイラの構成と最適化をゼミで読んでいたため知識としては復習になったが、実際に字句解析器や構文解析器を実装したことはなかったので、改めてコンパイラの仕組みを理解する良い機会になった。