Zenn
📚

Nand2Tetris読書会（10章）

2022/08/12に公開
勉強会
読書会
idea

概要

Nand2Tetris読書会 を開催しています。
今回取り上げるのは、10章『コンパイラ#1：構文解析』です。

前の記事は こちら。

内容

「コンパイラ=変換を行うプログラム」であり、ソース言語で書かれたプログラムをターゲット言語で書かれたものに変換するプロセスをコンパイルと呼ぶ。
コンパイラの変換はふたつの作業に基づく。

  1. 構文解析: ソースプログラムの構文を理解して、プログラムの意味(semantic)を明らかにする
  2. コード生成: パースした情報から、ターゲット言語の構文からプログラムのロジックを再構成する

本章では、構文解析にスポットを当てて学習する。

構文解析の作業は、ふたつのモジュールに分けられる。

  • トークナイザ: 「トークン」(意味を持つコードの最小単位)に変換する
  • パーサ: 一連のトークンを言語の構文ルールに適合させて、構文構造を明らかにする

構文解析において、以下の4つがポイントとなる。

  • 字句解析(スキャニング、トークン化)
    • プログラム内の文字のグループをトークンにまとめること。
    • トークンは、キーワード、シンボル、識別子、定値などの可能性がある。
  • 文脈自由文法
    • ある言語の構文要素がより単純な要素からどのように構成されるかを指定したルールの集合のこと。
    • 宣言側の視点: トークン(終端要素、ターミナル) → 高水準な構文要素(非終端要素) → より高水準な非終端要素 → ... → トークンの集合 と組み合わせる。
    • 分析側の視点: トークンの集合 → 非終端要素 → より低水準な非終端要素 → ... → 終端要素 と分解する。
  • 構文木(導出木)
    • 構文解析のパーサモジュールによって生成される出力のデータ構造のこと。
    • コンパイラによっては、木構造をコード生成やエラー報告にも利用する。
  • 再帰降下アルゴリズム
    • 言語の文法で規定されるネスト化された構文を使って、トークンの列に再起的に構文解析をする。
    • Jack言語はLL(1)文法の言語なので、最初のトークンを見ればトークンの種類を決定できる。

本章のプロジェクトで作成する構文解析器は、コンパイル結果をXMLファイルとして出力する。
これにより、次章のプロジェクトではXMLファイル生成部をVMコード生成部に置き換えるだけでよくなる。

実装

本章では、3つのモジュールを使ってコンパイラを実装する。

  • JackAnalyzer: セットアップや他モジュールの呼び出しをする
    1. 入力のJackファイル(Xxx.lack)から、JackTokenizer を生成。
    2. 出力用のファイル(Xxx.xml)を作り、出力結果を書き込む準備をする。
    3. 入力の JackTokenizer を出力ファイルへコンパイルするため、CompilationEngine を使う。
  • JackTokenizer: トークナイザ
    1. 入力ストリームからすべてのコメントと空白文字を除去する。
    2. Jack文法に従ってJack言語のトークンへ分割する。
  • CompilationEngine: 再帰によるトップダウン式の解析器
    1. JackTokenizer からの入力を受け取る。
    2. 構文解析の結果である木構造を出力ファイル/ストリームへ出力する。

予習メモ

LL法とLR法

  • LL法: 入力文字列を左端から構文解析して左端導出をする。構文木を、最上位の非終端要素(根に相当)からスタートして、順次右辺の要素列へと書き換えていく構文解析方法。
  • LR法: 入力文字列を左端から構文解析して右端導出をする。構文木を、終端要素(葉に相当)からスタートして、順次左辺の非終端要素へと書き換えていき、最終的に最上位の非終端要素(根)を得る構文解析方法。

LL(k)文法/LR(k)文法とは、k字先のトークンを先読みする場合の表記であり、通常は k=1 なのでわざわざ表記しない。
k が大きい言語はそれだけ先読みをすることになるので、構文解析が大変になる。

多くのプログラミング言語がLR法で構文解析でき、LR法の実装は非常に効率がよい。
ただ、LR構文解析器を自作するのは難しく、普通はコンパイラ生成器(パーサジェネレータ)を利用する。

コンパイラ生成器

コンパイラの開発を支援するため、構文解析器を自動生成するプログラムのこと。

  • LEX(lexical analysis):
    レキシカルアナライザ(字句解析プログラム)を生成するプログラム(レキシカルアナライザジェネレータ)。実装で扱った JackTokenizer に相当するものを生成する。
  • YACC(Yet Another Compiler Compiler):
    構文解析器の解釈部分を生成するプログラム(パーサジェネレータ)。パーサジェネレータの中でも、LALR(1)の構文解析器を生成する。実装で扱った CompilationEngine に相当するものを生成する。

形式言語

書籍では、形式言語について「言語の特質や言語を規定するためのメタ言語と形式について議論する分野」とある。
「形式言語」とは特定の目的のために意図的に作られたプログラミング言語のような言語のことを指す言葉で、人間が日常的に用いる言語は時代や文化によって変化する「自然言語」とは逆の意味を持つ。
自然言語は話者同士の文脈に沿ったルールが存在しており曖昧さが許容されるが、形式言語は厳格なルールを持つ。

ディスカッションメモ

他の言語のコンパイラにはどのようなものがある？

本書ではトークナイザとパーサ分けているが、最近のPythonのコンパイラではこれらを一緒に処理している(PEG)。

https://ja.wikipedia.org/wiki/Parsing_Expression_Grammar

「プログラミング言語は通常、文脈自由文法と呼ばれる生成規則によって記述される」とあるけど本当？

実際に文脈自由文法で記述される言語はほとんどなさそう…
文脈依存文法で記述される方が多いみたい。

構文の定義はどのように書くの？

文脈自由文法を定義するメタ言語として、バッカス・ナウア記法(BNF) や EBNF がある。
10.1.2の例10-1で紹介されている文法は BNF と似ているが、少し違う記法で書かれている(どの記法なのか不明)。

感想

演習課題がかなり重めの章でした……。
なんとかテストは通るような形となりましたが、ここはもっとうまく書けるんじゃないかな？という箇所がいくつもあります。

演習のプログラムは、TypeScript で書きました。
仕事でたまに書いていましたが、一から全て自分で書く機会があまりなかったので、自動フォーマットの設定なども含めて学ぶことが多かったです。

最後に

『Nand2Tetris読書会始めました』の記事でも紹介していますが、読み進めているのはこちらの本です。
https://www.oreilly.co.jp/books/9784873117126/

初学者なりに書籍やその他に調べた内容をまとめていますが、理解が足りておらず間違ったことを書いているかもしれません。
そのような箇所を見つけた場合はコメントなどで指摘していただけると助かります。

次の記事は こちら。

GitHubで編集を提案

Discussion