コンパイラ概論で遭遇した用語集まとめ

　The Elements of Computing Systems を読み進めている。今週からいよいよ大詰めのコンパイラ編に突入した。

The Elements of Computing Systems: Building a Modern Computer from First Principles (The MIT Press)

　概念としてのコンパイラのはたらきには、言語学の知識が絡んできていてとても面白い。たしか学部2年生のころに言語学入門の講義を履修したのであった。必ずしも優秀な生徒であった自信はないが、計算機科学の観点から言語学にアプローチするのは、ジョブズにとってのカリグラフィよろしく、点と点がいままさに線になろうとしているようでたいへん面白い。

　とはいえ、スッと飲み込むにはやはり難しい。まずは用語集を整理しなければ理解のスタートラインにすら立てない気がしている。そこでゼミの予習のような気持ちに立ち返って、まずは用語集を作ってみることにした。

　基本的にテキストに沿って整理している。英語のテキストをきちんと読み下して、日本語で整理している格好である。

　用語の日本語訳については wikipedia の多言語ページを参照している。ほとんどの項目について wikipedia に詳細な解説もあるが、直接の引用は行っていない。難しすぎて理解が及ばないのである。そのためまずはテキストに固執してきちんと精読している。

「計算機科学大辞典」のような、学者向けに重要概念や用語をコンパイルした文献があればだいぶ便利だったはず。ネット検索で出てくるのは玉石混交な情報ばかりで、きちんと頼れる情報源が見つけられなかった。 wikipedia をつい引用したくなる学部生の気持ちはとても共感できる。

　大学図書館あたりで文献を調べてみるというのはありなのかもしれないが、あいにくもはや自由に出入りできる身分ではないし、パンデミックな時節柄、一般利用者として押しかけるのも迷惑だろうから、それは控えた。いずれ機会があればきちんと調査してみたいなとは思っている。

　前口上はこれまでで、以下が用語集である。学生のノートを覗き見るような気持ちで眺めてみてほしい。

formal language - 形式言語

　人工的に単純化され、形式化された言語のこと。プログラミング言語を含むが、それにとどまらない。

　形式言語において自然言語の複雑さは捨象され、シンタックスの構造を精確に形式立てることができる。一般にプログラミング言語は、「文脈自由文法（ context-free grammar ）」と呼ばれる規約によって規則づけられる（後述）。

lexical analysis - 字句解析

　scanning, tokenizing とも。コンパイラの文脈においては、プログラムのソースコードを解析して、その文字列を分割可能な最小単位まで分割することを意味する。分割可能な最小単位のことをトークンとも呼ぶため、「トークン化（ tokenizing ）」とも呼ばれる。

terminals and non-terminals - 終端記号と非終端記号

「終端記号（ terminal ）」は「トークン」と同じ意味で、それ以上分割不能な最小単位のことを指す。対して「非終端記号（ non-terminal ）」とは、「終端記号」の組み合わせによって生ずる、より高次な表現である。

　例として、プログラミング言語における count, <=, 100 といった表現はそれぞれ、これ以上分解できない「終端記号」である。これらが集合し、 count <= 100 という表現を構成するとき、この要素は「非終端記号」である。

context-free grammer - 文脈自由文法

　形式言語における文法規則のこと。 count, <=, 100 という「終端記号」を利用して、 count <= 100 という「非終端記号」を表現できると上に書いたが、この count <= 100 が有効なことは当然、文法によって保証されていなければならない。

　あらゆる文脈自由文法は、「どのように終端記号を組み合わせて非終端記号を構成できるか」というボトムアップな指向性と、「どのように非終端記号を終端記号に分解できるか」というトップダウンな指向性の両面を規約する。

parsing - 構文解析

　入力されたテキストが文法に適っているかどうかを検証する行為のこと。

　コンパイラが構文解析を行うとは、与えられたソースコードの文字列に文法規則との完全な対応関係を与えるということである。またコンパイルエラーとは、ソースコードを文法規則に当てはめることに失敗したということに他ならない。

parse tree - 構文木

　構文解析の結果を表現するデータ構造のこと。文法規則は一般に階層構造をとるため、それを表現するにおいても階層構造をもつ木構造が利用される。

recursive descent parsing - 再帰下降構文解析

「構文木」を作成するアルゴリズムのうち、トップダウンに実行されるアルゴリズムのひとつに「再帰下降構文解析」がある。

　構文解析プログラムが「非終端記号」に遭遇するたびに、それを「終端言語」に再帰的に解析しつづけることで、すべてのトークンをもれなく処理しきることができることとなる。

LL(1) parser - LL(1) 構文解析

　再帰的に構文解析する際には、解析前に解析対象の中身を知る必要がしばしば生じる。

　例えばこれから解析しようとしている表現が while 文であるのか if 文であるのかによって、解析の仕方は異なる。そこであらかじめ解析対象の表現の先頭のトークンを覗き見て判断を下すのが、 LL(1) と呼ばれる方式である 。要するに、先頭のトークンが while であれば表現全体が while 文であることは明らかであるし、 if についても同様である、ということになる。

　先頭から k 個のトークンを先読みして初めて構文解析が可能な言語も成立しうる。こうして一般化される構文解析の方式のことを LL(k) と呼ぶ。ただし k が 1 に近いほど構文解析が容易であることは言うまでもない。