読者です 読者をやめる 読者になる 読者になる

ottatiのブログ

無職学生がネットにクソアプリをまき散らしていく様子

【読書メモ】コンパイラ 中田育男 (オーム社)

f:id:ottati:20150103125718g:plain     🍣

ジョジョのアニメ版の最終回を休憩がてら観て、"Weird Al" Yankovicという人物を知ってググって観たが昔のパロディだけどやられた。Eat it

TIL: 戦後は「日本の子供は飢えてるんだから食え」というしつけ文句があった

コンパイラの勉強

中田育男さんというコンパイラの権威が1995年ーこれは僕が生まれた次の次の年であるがーに書いたコンパイラという本を何周か読んだ。

コンパイラ (新コンピュータサイエンス講座)

コンパイラ (新コンピュータサイエンス講座)

本当にコンパイラの基礎という基礎が詳しく書かれていて、それでいて理解しやすく非常に読みやすい良書だと思う。150ページくらい

中田育男さんは1971年から「コンパイラ技法」という本を出しているし最近もコンパイラの本出しているみたいだし何かがコンパイルされたらそれは中田さんのせい、コンパイルお化け、妖怪

今回読んだのはこっちじゃなくて前者のほう

わかりづらかったことと忘れそうなこと

字句解析と構文解析

字句解析プログラムを構文解析プログラム風に書いて教授に見せたらそれはちょっと違うんじゃないかとアドバイスしていただいた。どうやら字句解析と構文解析の根本的な存在意義の違いを理解していなかったらしい。

字句解析は意味のあるcharのまとまりを切り出して、トークンとして認識すること。大抵正規表現で行われる。つまり字句解析プログラムは正規表現解析プログラムみたいなものかな。

文脈自由文法で表せて、正規表現で表せないものの一つに括弧が挙げられる。括弧が持つ不可分性が問題で、例えば括弧がn回ネストされた文字列を正規表現で表すことはできない。

正規表現は決定性最小オートマトンとして書き出し、それを元にプログラムに書き直す。最初はこの認識でいいのだと思う。

<名前> -> <英字>{<英字>|<数字>}

state1: k = 0;
  if (charClassT[ch] == letter)
    goto state2;
  else
    error();

state2: a[k++] = ch; ch = nextChar();
  if (charClassT[ch] == letter || charClassT[ch] == digit)
    goto state2;
  else goto state3;

state3:

ちなみに字句解析しないで構文解析するコンパイラもあるらしい。字句解析する意味は効率化にある。

Director

Firstは最初にくるトークンの集合、Followは次にくるトークンの集合、じゃあDirectorは?

Directorは概念的にはFirstに近い。非終端記号Eで、次のトークンがaだった場合に、そのトークンがあるかどうか、あるならどの生成規則を使うのか、ということを示したもの。なので同じ非終端記号でDirectorの部分集合が重なってはLL(1)文法、つまり1つ次を読み込んだだけでわかる文法、ではないのだ。

全ての生成規則についてDirectorを求めると、このテキストには構文解析表について書いていないが、それを作成する時のその値になる。

括りだしと直接左再帰性

下向き構文解析の問題としてあげられるのが括りだしと左再帰性という問題。

括りだしはDirectorを算出してLL(1)文法になっているかどうかに関わってくる、という観点から見ればわかりやすい。B->b|bcの場合はどっちを生成すればいいのかわからないのでB->b(c|ε)とする。こうすることでDirector(B, b) ∩ Director(B, bc) = {b} ≠ φとなってしまい、LL(1)文法ではなかったのだが、Director(B, b(c|ε))とすることでLL(1)文法を満たすようになった。はじめのトークンが同じ場合はくくりだせばいい。

直接左再帰性A->Aaみたいな時にこれを馬鹿正直に下向き構文解析プログラムに直すとvoid A()の一番初めにA();を記述することになり、処理が永遠に終わらないという問題。ただA'と,新しい非終端記号を追加すればいい。

A -> A+B | Bという直接左再帰性を持った生成規則があるならば、A'というものを追加してAが一番左にこないようにしてやる

A -> BA'
A' -> +BA' | ε

さいごに

古い本は敬遠しがちだが、わかりやすい本だった ; )