Skip to content

Instantly share code, notes, and snippets.

@raven38

raven38/0.0.markdown

Last active July 27, 2024 06:48
Show Gist options
  • Save raven38/18d3a16748f7fdd73705 to your computer and use it in GitHub Desktop.
Save raven38/18d3a16748f7fdd73705 to your computer and use it in GitHub Desktop.
Download ZIP
『コンパイラ 原理・技法・ツール』読書メモ
Raw
0.0.markdown

#コンパイラ 原理 技法 ツール

######著者

  • Alfred V. Aho
  • Jeffrey D. Ullman

コンパイラ 原理 技法 ツール、通称ドラゴン本の訳書です。 出版社が培風館で情報処理シリーズのうちの一巻なので表紙がドラゴンじゃない

原始言語云々とかマシンとかによらず、コンパイラを設計する際に例外なく遭遇する問題を解決するための本。決して初学者が読むものではない(激し後悔)。

一般のソフトウェアの設計に役立つ考え方や技法が多く述べられている(メインの目的、アルゴリズム)。

#####各章の要約

  1. [コンパイラの基本構造(絶対重要)] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-1-0-markdown)
  2. [プログラミング言語の基礎概念(省くな)] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-2-0-markdown)
  3. [字句解析、有限状態技法、走査系生成系(最初の２節は省くな)] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-0-markdown)
  4. 構文解析基礎概念(読まないと分からない)
  5. 演算子順位法と再帰降下法(時間なければ省いてもいい)
  6. 最強のLR構文解析法(省いてもいいけどもったいない)
  7. 中間コード生成、代入や制御構造に対する翻訳方式(ここの内容は全て省くな)
  8. その他の言語の構成要素(省いてもいいよ)
  9. 記号表(いままでデータ構造の選択を誤ったことのないものだけがこの章に石を投げてよい)
  10. 実行時の構成。(3節は省いても問題ない程度の内容)
  11. 誤りの回復(知らないと恥)
  12. コードの最適化、導入(やっとけ)
  13. コードの最適化(入門程度では理解できない)
  14. コードの最適化(君たちには理解することはできない)
  15. 目的コードの生成(君たちでも理解できるだろう)
  • 付録B コンパイラの前半部分を作成するためのenshuumondai
Raw
1.1.markdown

###コンパイラと翻訳系

翻訳系(translator)は、一つのプログラミング言語(原始言語(source language))で書かれた プログラムを入力としてとり、別の言語(目的言語(object language))のプログラムを出力として作り出すプログラムである。 現在で言えば処理系(implementation)って言う方が理解しやすい。 原始言語がFORTRANとかPL/IとかCOBOLといった高水準言語で、目的言語がアセンブリやマシン語といった低水準言語である翻訳系をコンパイラ(compailer)と呼ぶ。

かつてはコンパイラを幻の産物と思われてたらしい。最初のFORTRANコンパイラを実現するのに18人年かかった。簡単に作れるようになった過去20年の主な発展の所産

  • コンパイルの過程を系統立ててまとめモジュール化する方法が分かった
  • コンパイル中に現れる多数の重要な仕事を扱うための系統的な技法が見つかった
  • コンパイラ及びコンパイラの構成要素の実現を容易にするソフトウェアによる道具が開発された

######他の翻訳系 解釈系(interpreter)、コンパイラよりも小さく複雑な言語の構成要素を実現しやすいことが多い。その反面、実行時間が悲惨。 アセンブラ(assembler)や前処理系(preprocessor)と呼ばれるものもある。

ほとんどまとまってない。

Raw
1.10.markdown

###誤り処理

原始プログラム中の誤りの検出と報告はコンパイラの最も重要な機能の一つ。 エラーメッセージはプログラマにとって、その誤りがどこで起こったかが正確にわかるものでなければならない。

誤りを見つけたとき、その誤りを誤り処理系に報告しなきゃならない。すると誤り処理系は適切な診断メッセージを出す。ひとたび誤りを検出したら、コンパイラは、まだあるかもしれない誤りを探すためにそれから後も引き続き処理できるように、その誤りを検出したフェーズへの入力を修正する必要がある。

誤りが後の誤りを隠しちゃうもんだから優れた誤り処理はたいへん。

Raw
1.11.markdown

###コンパイラ作成道具

走査系および構文解析系生成系から、コンパイラコンパイラ(compiler-compiler)とかコンパイラ生成系(compiler generator)とかあるいは翻訳系記述系(translator-writing system)とか世おばれてる。

######主な入力仕様

  • 原始言語の字句および構文構造の記述
  • おのおのの原始言語の構成要素に対して生成すべき出力の記述
  • 対象とする機械の記述

コンパイラコンパイラには限界がある。主要な問題は利用者のためにコンパイラコンパイラが自動的になしうる作業量と、どの程度その系を柔軟にすることができるかの取引。

現在のコンパイラが備えてる主要な機能

  1. 走査系生成系(scanner generator)
  2. 構文解析系生成系(parser generator)
  3. コード生成のための機能
Raw
1.12.markdown

###始めるにあたって

コンパイラはシステムの中の一つにプログラムにすぎないが、ふつうは、多数の人に使われる重要なプログラムである。従ってコンパイラ設計者はコードを書き始めるまえに以下の問題点を考慮しなければならない。

  • 対象とする機械の性質および操作環境
  • コンパイラのimplementation language、プログラム作成環境よぼび利用できる道具
  • 保守運用が容易いこと

別の機械のための目的コードを生成するクロスコンパイラ(cross compiler)。

Raw
1.2.markdown

###翻訳系の必要性

明らかである。マシン語は0と1の列なので退屈。

######記号アセンブリ言語 命令コードおよびデータ番地に対して簡略名(mnemonic name)を用いる。 しかし、コンピュータはアセンブリ言語で書かれたプログラムを実行できない。アセンブラを用いてマシン語へ翻訳する。

######マクロ テキストを置き換える機能。

######高水準言語 アセンブリでもプログラマは特定の計算機の動き方の詳細を知らなければならない。機械の中でデータがどこでどのように表現されてるか、いちいち気をつける必要がある。 高水準言語は特定の計算機がどのように機能するかというこまかいことには煩わされず、より自然な記法でアルゴリズムを表現できる。

高水準言語はプログラミングの仕事をより単純にするが、コンパイラが必要となる。コンパイラは本質的にアセンブラよりも複雑なプログラム。

プログラミング言語の構成要素の形および意味が、その言語のためのコンパイラの設計全般に強く影響する。

Raw
1.3.markdown

###コンパイラの構造

コンパイラは原始プログラムを入力としてとり、それと等価な機械命令の列を出力として作り出す。めっちゃ複雑。論理的な立場からも実現の立場からも、コンパイルの過程を単一ステップで行われることと考えると痛い目見る。 コンパイルの過程はフェーズ(phase)と呼ぶ一連の副過程に分割するのがしきたり。フェーズは原始プログラムの一表現を入力としてとり、別の表現を出力として作り出す一つの論理的に密着している操作。

######字句解析系(lexical analyzer)、走査系(scanner) 字句(token)に分離する。tokenは手掛り語(keyword)、識別子(identifier)、演算子記号(operator)、区切り文字がある。

#####構文解析系(syntax analyzer, parser) lexical analyzerから渡された字句を構文構造にまとめる。例えば

A + B

を表現する三つの字句は、式(expression)という一つの構文構造にまとめられる。式をさらにまとめ、文が形成される。葉を字句とする木とみなすことがある。

######中間コード生成系(intermediate code generator) 一連の単純な命令を作る。様々な表現法のうち、一般的なものの一つとして、演算子を一つと非演算子をいくつかもった命令がある。これはマクロに似たもの。

######コード最適化(code optimization) 最終的な目的プログラムがより速く、より小さい記憶域になるように中間コードを改良する。

######コード生成(code generation) データのための記憶位置を決定し、おのおののデータにアクセスするためのコードを選び、そして個々の計算を行うレジスタと選ぶことによって目的コードを作り出す。効率のより目的プログラムを作り出すコード生成系を設計sるのはコンパイラ設計のうちで最も困難な部分の一つ(できるものならやってみろ)

######表管理(table management)、記帳(bookkeeping) そのプログラムで用いられた名前を覚えておき、型のようなおのおのについての本質的な情報を記録しておく、記号表(symbol table)と呼ばれるデータ構造を用いる。

######誤り処理系(error handler) 原始プログラム中に欠陥が検出されたときに呼び出される。診断を出すことでプログラマに警告し、おのおののフェーズが先に進むことができるように、フェーズからフェーズに渡される情報を調整する必要がある。少なくとも構文解析フェーズを終了できるように調整するのが望ましい。一回のコンパイルでできる限り多くの誤りを検出することができる。 表管理ルーチン、誤り処理ルーチンは、ともに、コンパイラの全てのフェーズと相互に作用する。

こんな感じになる

 字句解析 → 構文解析 → 中間コード生成 → コードの最適化 → コード生成

#####パス コンパイラを実現する際には、一つ以上のフェーズをまとめてパス(pass)と呼ぶ一つのモジュールにする。原始プログラムまたは一つ前のパスの出力を読み込み、その各フェーズで指定されている変換を行い、出力を中間ファイルに書き出す。パスの数およびパスとしてフェーズをまとめることは、通常、個々の言語や機械に関連した種々の考察により決められる。

コンパイラの動作環境もパスの数に影響を及ぼす。多重パスのコンパイラは、単一パスのそれに比べて少しの記憶域しか使用せずに作ることができるが、中間ファイルのI/Oが発生するので遅くなる。

#####パスの数を少なくすること 後埋め(backpatchin)として知られる手法を用いることでいくつかのフェーズを一つのパスに併合することもできる。

いずれにせよ、実際のコンパイラではすべてのフェーズは協力して働く必要があり、一つのフェーズに対して採用した方式は、その後のフェーズでしなければならない処理の種類に影響し得る。

Raw
1.4.markdown

###字句解析

字句解析系は原始プログラムとコンパイラとのインターフェース。 原始プログラムを一文字ずつ読み、字句(token)と呼ぶ一連の最小単位に分割していく。識別子、手掛り語、定数、演算子、区切り文字は代表的な字句。

######ex IF(5 .EQ. MAX) GOTO 100

というFORTRAN文はIF, (, 5, .EQ. MAX, ), GOTO, 100という8この字句がある。

字句は言語に依存するだけでなく、コンパイラ設計者の判断にもある程度依存する。 字句はIFやセミコロンのような特別な文字列と識別子、定数あるいは名札のような種類の文字列の二種類がある。これを扱うために字句を、字句の型と字句の値という二つの部分からなる対として取り扱う。

字句解析系と構文解析系は一つのパスにされることが多い。字句解析系は構文解析系の制御の下で動くかあるいは構文解析系のコルーチンとして動く。構文解析系は次の字句が必要になるたびにそれを字句解析系に要求する。字句解析系は取り出した字句に対するコードを構文解析系に渡す。字句が識別子とか値をもった字句の場合にはその値も渡される。通常の方法として、字句解析系が記帳ルーチンを呼び出し、実際の値が記号表に記入されてなければ、記入するものがある。それから字句解析系は字句の二つの構成要素を渡す。最初の要素は字句の型(識別子)にたいするコードで、二つ目は値(取り出した特定の値のためにとられている記号表内の場所へのポインタ)である。

#####字句の取り出し 次の実を取り出すために、まだ字句として集めてない最初の文字から調べる。 次の文字がなんであるかを決めるには次の字句の先の方の文字も探す。

Raw
1.5.markdown

###構文解析

構文解析系には入力(字句解析系の出力)として現れた字句が、原始言語に対する仕様によって許されているパターンと合致するかどうかの検査とコンパイラのこの後のフェーズで用いる木状の構造に字句をはめ込む二つの機能がある。

たとえば

A + / B

という式があるとすると、字句解析後、この式は構文解析系には

id + / id

という字句列に見える。/を見て、構文解析系ではこの式が誤りであることを指摘しなければならない。

構文解析系のもう一つの面は字句の連なりのどの部分を一緒にすべきかを識別することで、入ってくる字句の連なりの階層構造を明確にすること。たとえば、

A / B * C

という式は FOTRANのように

(A / B) * C

もしくはAPLのように

A / (B * C)

という二通りの解釈ができる。これはおのの、解析木(parse tree)によって表せる。

           exp                         exp
         /  |  \                     /  |   \
        /   |   \                   /   |    \
       /     \   \                 /    |     \
     exp      \   exp            exp    |     exp
   /  |  \     \    \             |     |    / | \ 
  /   |   \     \    \            |     |   /  |  \ 
 A    /    B     *    C           A     /   B  *   C

こんな感じ、分かりやすい。 どちらの解釈をとるか、一般に、個々の原始プログラムがどのような階層構造をもつか、が言語仕様からわからなければならない。これらの規則がプログラミング言語の構文仕様を形成する。4章で文脈自由文法(context-free grammar)が言語の構文構造を規定するのに、特に役立つことがわかる。さらに、ある種の文脈自由文法からは自動的に効率のよい構文解析系をつくることができる。

Raw
1.6.markdown

###中間コード生成

論理的なレベルでは、構文解析系の出力は、ある種の解析木の表現になっている。中間コードフェーズでは、この解析木を原始プログラムの中間言語表現に変換する。

######3-番地コード よく使われる中間言語の一つとして、いわゆる"3-番地コード(three-address code)"がある。代表的な3-番地コードの文は

A := B op C

である。ここで、A,B,Cは被演算子で、opは2項演算子。 前の節の式を3-番地コードの列に変換すると

T1 := A / B
T2 := T1 * C

となるはず。 ほかのwhileとかforとかの分岐文もこれらの低水準の条件つき3-番地コード文に翻訳される。

たいていのコンパイラでは解析木を陽に生成せず、むしろ構文解析を行うにつれて、直接、中間コードを生成する。構文解析では陽に解析木を作り出すものとしたのは、解析と中間コードの詳細を渾然一体にしないで、5,6章で各種の構文解析アルゴリズムを評価したいから。

7,8章では構文主導型翻訳(syntax-directed translation)による中間コード生成について述べる。これは構文解析フェーズの動作が翻訳に導く手法である。

Raw
1.7.markdown

###最適化

速くて小さい目的プログラムを生成できる、中間言語をつくる。 最良のプログラムにはならない。 よい最適化コンパイラは、全体的な速度でおよそ2桁ほど目的プログラムをよくする。

######局所的最適化

    if A > B goto L2
    goto L3
L2:
    if A <= B goto L3

こんな感じ、または

	A := B + C + D
	E := B + C + F
	T1 := B + C
	A  := t1 + D
	F  := t1 + F

こうなる もっと効果のあるものでは、コンパイラ自身によって生成される計算からでてくる。 そのうちの筆頭は添字計算である。機械の主記憶がバイト単位で番地付けされ、1語が4バイトとすると、

A[I] := B[I] + B[I]

という文だと4*Iを3回計算する必要がある。これを一回の計算で済むように中間プログラムを修正できる。これらの番地計算は原始プログラムの段階では陽に出てこないのでプログラマがいじれない

######ループの最適化

ループをまわるたびに全く同じ結果を作り出す計算を、プログラム中で、そのループに入る直前の位置に移す。そのような計算をループで不変な計算(loop invariant computation)という。

  • 12章で種々のコード最適化-局所的最適化、ループの最適化、制御およびデータの流れ解析
  • 13章では制御の流れ解析、ループ及びループの最適化
  • 14章ではデータの流れ解析、すなわちプログラム全体でのデータの使用に関する情報の収集と利用

について述べる

Raw
1.8.markdown

###コード生成

コード生成のフェーズでは中間コードを機械命令の列に変換する。 素直に中間コードから機械コードへマクロのような展開をすると、大食漢の機械コードになる(赤城さんの悪口を言ってる訳ではない)

これらの冗長なロードと格納をさけるために、コード生成系では実行時のレジスタの内容を覚えておく。数少ない高速レジスタと能率よく利用することを試みる。コード生成のこの部分をレジスタ割当て(register allocation)というが、最善のことを行うのは極めて難しい。適度によい結果にするにはいくつかの発見的方法が知られている。 15章で説明する。

Raw
1.9.markdown

###記帳

コンパイラで収集する必要のある原始プログラムに現われるすべてのデータ対象に関する情報を記入する。たとえば、型や、配列の大きさ、関数の引数の数など、

データ対象に関して集められた情報の用途は広大。たとえばA+Bという式があって、Aは整数型、Bが実数型だとする。そして、その言語で整数を実数に加えることが許されているとすると、たいていの計算機では、加算を行うためにAを整数から実数に変換するコードを生成しなければならない。逆に異なるデータ構造同士の加算が禁止されているならば、エラーメッセージを出さなければならない。

######意味解析(semantic analysis) 中間結果の型の決定、被演算子が演算子を適用することができる型かどうかの検査、および演算子によって示された演算の決定。意味解析は構文解析、中間コード生成、コード生成のいずれのフェーズでの行える。

Raw
2.1.markdown

###高水準プログラミング言語

何百という数のプログラミング言語が存在する。(現在は5000とかなんとか)。

次に示すのは高水準言語がマシン語やアセンブリに対して優れている点

  • 理解のしやすさ(読みやすく、書きやすく、正しいことを証明しやすい)
  • 自然さ(アルゴリズムを表現する際の容易さ、問題領域に対する使用言語)
  • 移植性(異なるアーキテクチャのマシンでも走ること、Write once, run any whereみたいな)
  • 使用効率(時間のかかるJavaはいやだ)

信頼性の高いプログラムを作成するのに役立つ高水準言語の機能

  • データ構造
  • プログラムの他の部分を知らず知らずに影響を与えることなく、プログラムの一部を修正できる有効範囲規則
  • プログラム中のループ構造を明瞭に示す制御の流れの構成要素
  • プログラムを分割して設計できるサブルーチン
Raw
2.10.markdown

###データ環境

プログラムに

A := B + 1

という文があるものとする。Bの値はどのようにして決まるのか。Bはいろんなとこに現れるかも、大域変数や局所変数かもしれない。仮引数だったりする。それぞれの場合について、プログラムの実行時にBの適切な値を決定するために、異なった規則が適用される。識別子とそれが現在表している名前との対応関係を、文、ブロックあるいは副ブロックのenvironment(環境)と呼ぶ。

######識別子の名前とbind(結合)

FORTRAN,ALGOL,PL/Iのような言語のstatic(性的)結合とSNOBOL,LISPやAPLといった言語のdynamic(動的)結合がある。

######有効範囲規則 scope(有効範囲)はその名前を使うことのできるプログラムの部分。 識別子Aを書いたときには、それを囲んでいる最も内側のAが宣言されているブロックのAの宣言を参照する。これをmost closely nested rule(至近規則)と呼ぶ。

Raw
2.11.markdown

###引数の転送

######引数

formal parameterまたはformal(仮引数)、他の対応英語としてdummy argument、parameterとactual parameterまたはactual(実引数)、argumentがある。

######call-by-reference(参照呼び)

呼び出すプログラムではサブルーチンに各実引数のr値へのポインタを引き渡す。

######call-by-value(値呼び)

実引数が評価され、そのr値が言語の実現方式によって定められた位置におかれ、サブルーチンに引き渡される。

これを一般化したものとしてcopy-restore linkage. copy-in, copy-out linkageとかvalue-result linkage(複写復元連係)がある。呼び出す前に実引数が評価される。そして、値呼びのように、実引数のr値が呼び出された手続きへ引き渡される。しかし、さらに、l値を持っている実引数はそのl値も呼び出す前に定められる。呼び出したところへ戻るおtき仮引数の値の現在の値が、呼び出す前に求めたl値を用いて、実引数のl値のところへ複写されて返される。

######call-by-name(名前呼び)

ALGOLで第一の方法として規定されている名前呼びは相当の威力をもち、理論的にも興味のある機構であるが、実現することは難しい。その基本的な考え方は、実引数がそれらが必要とされるまで評価せずにおいておき、必要とされるたびに改めて評価するというものである。この考え方の通常の実現方法は実引数のl値やr値を評価することができるthunk(サンク)と呼ばれる引数なしのサブルーチンを、呼び出された手続きに引き渡すというものである。

名前呼びの意味を定義するこれまでの方法は、ALGOLのcopy rule(複写規則)によるものである。これによると、呼び出された手続きはマクロであるかのように、すなわち仮引数を完全に実引数で置き換えたその手続き自身でその呼び出しを置き換えるかのように実現することになる。実引数にある名前と同じ識別子をもつ呼び出された手続きの局所名には、仮引数を実引数で置き換える前に別の識別子を与えなければならない。また、実引数は、もとのままの状態を保つために必要ならば括弧でかこまなければならない。

Raw
2.12.markdown

###記憶域管理

目的プログラムを実行するためにデータ構造、変数、定数とか手続きの情報を記憶する必要がある。

######性的記憶割当て

あらゆるデータ項目の大きさをコンパイラで決めることができる。再帰的な手続きが許されていなければ、すべてのプログラムおよびデータのための領域は翻訳時に、すなわち性的に割り当てることができる。この場合には、名前と位置の結びつけも性的に行うことができる。性的割当は、効率よく実現することが容易で、しかも記憶域を割り当てるためのrum-time support(実行時の支援)(目的プログラムと一緒にロードされるライブラリルーチン)をいっさい必要としない利点もある。

######動的記憶域割当て

言語で再帰的手続きか寸法が整合可能なデータ構造を許すと、ある種の動的記憶域管理が必要になる。一般にスタック割当てとヒープ割当てがある。両方使うことも。

stack allocation(スタック割当て)は、再帰的手続きを処理するのに都合がいい。

heap allocation(ヒープ割当て)はプログラムが実行するにつれて寸法が変わるようなデータ、たとえばSNOBOLの文字列やLISPのリストを実現するのに都合がよい。

######再帰とディスプレイ

再帰手続きでは、同じブロックや手続きに体する活動記録がいくつも実行時スタック上に同時に現れることもある。

至近規則のもとで、識別子と名前との性的結合を用いているALGOLその他言語に対して都合のよい方法としてdisplay(ディスプレイ)がある。 ブロックや手続きに体する活動記録をいくつでも含むことのできるポインタのリスト。

######ヒープ割当て

ヒープの現在使われていない部分はavailable space list(使用可能領域リスト)につながれている。

Raw
2.2.markdown

###プログラミング言語の定義

プログラミング言語を定義するのに用いることができる次のような特徴をもつ表記法があることが望ましい。(ないんだけどね)

  1. 言語設計者が、どのようなプログラムが正しく、しかもそれらのプログラムが何を意味するのかを単純でしかも明瞭に表現することができる

  2. プログラマが、自分がどのようなプログラムを書くことができ、しかもそれらが何をするのか決定することができる。

  3. コンパイラ設計者が、コンパイラがどのような原始プログラムを受理すべきか、それらに対して、コンパイラでどのような目的コードを生成すべきかを決定することができる。

######構文 たいていの言語のプログラムはアルファベットの文字集合。その文字列が正しいプログラムであるかを告げる規則をsyntax、構文という。どの文字列が簡潔で、しかも厳密に定めることは、ほぼ不可能。正規表現と文脈自由文法はプログラミング言語の構文の大部分を指定するのに役立ち、コンパイラ作成の助けになる。

######意味 プログラムに対して意味を与えるsemantics、意味。構文を指定するよりも意味を指定するのは難しい。

  1. 解釈的意味(interpretive semantics):全てのデータ対象、それらの値およびプログラムとそのプログラムカウンタのからなる状態(state)によって特徴づけられた抽象的な機械上で実行するための規則
  2. 翻訳(traslation):個々の正しいプログラムに、その意味がすでに分かっている言語の文を対応させる規則を与える。ラムダ計算のような数学的言語や特定の機械語。
  3. 公理的定義(axiomatic definition):おのおののプログラムの構成要素の実行の前後で、データを関係づける規則を定義することができる。
  4. 拡張可能定義(extensible definition):基本的な操作を定義し、これらの基本的な操作を用いて言語の意味を定義する。代表的なものとしてLISP。
  5. 数学的意味(mathematical semantics):プログラムに対応する数学的対象を定義し、プログラムをそれらの抽象的な対象に翻訳する規則を与える。

######プログラミング言語の階層構造

                            プログラム
                                |
                       サブルーチンおよびブロック
                                |
                                文
                                |
                                式
                             /  |   \
                     データ参照 演算子 関数

プログラミング言語の構成要素は、論理的な意味とimplementation(実現)の両面を併せ持っている。実数を表す名前は、論理的なレベルでは、実数の格納場所であるのに大使、実現のレベルでは、名前はビット列に入れておくための主記憶の語あるいは語の列を表す。

Raw
2.3.markdown

###言語の字句構造および構文構造

言語の字句構造で度のよな記号の集まりを識別子や演算子として取り扱うべきかを定める。構文構造で、これらの字句の構成要素をどのようにまとめてsyntactic category(構文上のカテゴリ)と呼ばれるより大きな構造にすべきかを定める。

######alphabet(アルファベット) プログラミング言語で使われる記号の集合をこの言語のcharacter set(文字集合)あるいはalphabetという。

######token

  1. 定数
  2. 識別子
  3. 演算子記号
  4. 手掛り語
  5. 区切り記号

######上位レベルの構成要素 構文構造は字句の集まり。式は代入演算子、区切り記号および手掛り語とともに、文、ブロックおよびプログラムといった上位レベルの構成要素を形成するための要素となる。

######字句解析上の約束 FORTRANのように、文の要素は入力行の決められた位置に書かなければならないものがある。アセンブリ言語の名残。高水準言語の設計では文を入力行のどこにでもおくことができる自由形式の入力を採用する傾向にある。

Raw
2.4.markdown

###データ要素

演算子を適用したり、複雑なデータ構造を構築したりすることができるもの。 様々なプログラミング言語に共通して備えられている代表的なもの

  • 数値データ
  • 論理データ
  • 文字データ
  • ポインタ
  • 名札

######識別子および名前 論理的なレベルでは、おのおののプログラミング言語は、整数や実数のようなデータ要素とか配列や手続きのようなもっと複雑なものとかといったobject(対象)あるいはvalue(値)を操作したり使用したりする。計算機はどの型の値でも格納できる記憶単位からなる抽象的なstore(記憶)で構成されているものと見なす。おのおのの記憶単位はname(名前)を持っている(変数のこと)、identifier(識別子)で表される。

######属性 type(型)とかscope(有効範囲)とか

######宣言 一般に名前の属性は陽に宣言することによって設定することができる

######属性と名前との結合 binding(結合)、属性を名前と結びつける。概ね、コンパイル時に行われるstatic binding(性的結合)。ほとんどの言語では性的結合しか許していない。実行時に属性を結合(dynamic binding(動的結合))することを許している言語もある。 性的結合では属性は宣言時に決定されているため。あとから変更することができない、またコンパイル時に広範囲にわたるtype checking(型の検査)ができるため、演算子を効率よく実現できる。

動的結合では、同じ名前をある行では整数として扱い、次の行では配列として使うことができる(まるで夢のよう)。すべての名前は名前の一部としてデータ記述子を持つ必要がある。演算の際には引数のデータ記述子を調べる。効率が悪くなったり。

Raw
2.5.markdown

###データ構造

論理的なレベルでは基本的なデータ要素および他のデータ構造の集合と、構成要素間の構造的関係の集合からなる。データ構造は再帰的に定義されることがよくある。

  1. list(リスト):論理的なレベルでは、リストは空かデータ要素の後にリストが続けられたもののいずれか。基本的な演算として要素の挿入、削除、置き換え、検索などがある。
  2. tree(木):再帰的な構造を持つnode(節)の集合

その他、array、queue、stack、string、graphなど。

データ構造に関係する関数

  • constructor(構成子):データ構造の実体を作り出す
  • destructor(破壊子):データ構造を取り除き、それらが占めていた記憶域を使用可能にする
  • selector(選択子):データ構造にアクセスする

######コンパイラによるデータ構造の実現 論理的な定義を近似したもの。論理的な定義ではデータ構造の大きさの制限は与えられていないにも関わらず、実際の計算機では制限される。

######配列 index、subscript…個々の次元に沿った距離の長さ 翻訳時に大きさがきまる固定寸法と実行時に決まる動的配列がある

######レコード構造 論理的には、レコード構造は、そのレコードの欄(第二レベルの構造)が根の子供であり、部分欄(第三レベルの構造)がそれらの子供であるような木構造。

######文字列 文字を要素とする１次元の配列。

######リスト構造 任意のリスト構造を許す言語の例としてLISPがある。LISPのリストは歴史的な理由からCARとCDRと呼ばれる二つの欄を持つレコードである要素から形成される。これらの欄には、atom(アトム、整数や文字の酔うな基本的なデータ型)か空ポインタか他のレコードの番地かのいずれか。

######スタック LIFO

再帰的手続きを許している言語では手続きに関するデータを保存しておくrun-time stackがある。これはプログラマが陽に操作できない。

Raw
2.6.markdown

###演算子

######arithmetic operator(算術演算子) prefix(前置)、infix(中置)、postfix(後置)とかある。

######arithmetic expression(算術式) 演算子を組み合わせて式を作る典型的な規則は以下の通り

  1. データ参照は、それだけで式である。
  2. θを2項中置演算子、𝐸1,𝐸2を式とすると、𝐸1 θ 𝐸2は式である。
  3. θを単項前置演算子、𝐸を式とすると、θ𝐸は式である。後置演算子もいっしょ
  4. 𝐸を式とすると(𝐸) は式である。

######relational operator(関係演算子)

######logical operator(論理演算子)

(A + B) and (X < Y)

は、整数和A+Bが論理値として解釈される言語では正しい式である。

######string operator(文字列演算子) PL/Iにおける||はconcatenation(連接)演算子である。

######結合性と順位 left-associative(左結合的)、right-associative(右結合的)だったり。 常に数学と同じような結合が行われるわけではなく、言語により

a + b * c

という式が

(a + b) * c
a + (b * c)

という二通りの解釈ができる
precedonce level(順位レベル)という概念により定められている。

######演算子の代数的性質 多くの演算子は一定の代数の法則に従う。このことはコンパイラが式をある程度単純化するのに役立つ。通常代数では可換則、結合則、分配則がある。

実際の計算機では多くの場合、可換則しか成り立たない。 例えば

(a + b) + c
a + (b + c)

この二つの式が等価であることは保証できない。

######その他の演算子 ternary operator(三項演算子)と呼ばれるconditional(条件式)やselector(選択子)がある。添字づけ演算子は、variadic(変項)またはpolyadic(多項)である。すなわち任意の数の被演算子をとることができる。

#######coercion(型強制) intからdoubleにするとか

######演算子の実現 基本的なデータ型に体する一般的な演算子の多くは、対応する機械命令で実現される。算術演算子、論理演算子など。関係演算子は比較命令と条件付き飛び越しで実現される。その他の演算子はいくつかの機械命令の列またはサブルーチン呼び出しを必要とする。文字列処理演算子、多倍精度の被演算子や複素数に対する算術演算子などがある。小型の計算機では乗算や除算ですら、サブルーチンを必要とする場合がある。

Raw
2.7.markdown

###代入

######l値とr値 名前によって表される位置と値とは二つの異なった概念であることは既に述べた。 そこで名前と関連づけられている値をその名前のr-value(r値)と呼び、名前によって示されている位置をその名前のl-value(l値)と呼ぶ。 一つの名前からなる式はその名前と同じl値とr値を持つ。演算子のある式のr値は、その演算子を適用して得られる値である。しかし、どの式もl値を持つわけではない。

整数型変換は、それ自身ではl値しか表現できない。dereferencing(内容取り出し)とか呼ばれる。

######代入の実現

A := B
  1. Bのr値を計算し、それをあるレジスタrに入れるコードを生成
  2. AとBのデータ型が一致してなければ、Bのr値をAに適した型に変換するためのコードを生成
  3. 必要なら、Aのl値を決定するためのコードを生成。Aが基本的な型なら、ほとんどの言語、計算機ではこのためのコードは必要としない。
  4. レジスタrの内容をAのl値へ格納するためのコードを生成する。

######演算子としての代入 Cではこんなコードがかける(自慢)

A = (B = C + D) + (E = F + G)

𝐸1,𝐸2を式とし、=を代入演算子とすると、𝐸1 = 𝐸2のr値は、𝐸2のrと同じである。式はl値を持たない。

B = C + D
E = F + G
A = B + E

こう解釈される。

######より一般的な代入 言語によってはAとBが基本的なデータ要素以外の複雑なデータ構造の場合にもA := Bという形の代入を許している。通常、AとBはconformable(適合)であると条件がある。たとえばAを配列とするとPL/IではA = 0は配列の全ての要素に0を初期設定する。A = BはAの各要素にBの対応する要素の値が代入される。代入A = 0では整定数0は適当な配列定数へ陰に型が変更されることに注意。

Raw
2.8.markdown

###文

######simple statement(単純文)とcompound statement(複合文) それぞれ、その中に他の文が埋め込まれていない、一つ以上埋め込まれている文。

######文の型

  1. computation statement(計算文):新しい値を計算するために演算子を被演算子に適用する文。
  2. sequence-control statement(順序制御文):goto,break,call,returnなど意図的に制御の流れを変えるもの。
  3. structural statement(構造文):ENDのようなある種の文は、単純を構造にまとめる働きをする。
  4. declaration statement(宣言文):一般に実行可能なコードを生成しない。これらの文の意味的な効果は、コンパイラにプログラム中で現れる名前の属性について知らせることである。
  5. input and output statement(入力および出力文)
Raw
2.9.markdown

###プログラム単位

プログラミング言語の構成要素の階層の最上位のレベルであるブロック、手続きおよびプログラム。これらのプログラム構造について３種類の言語を考察することで、プログラム単位の基本的な用語を導入する。

######FORTRAN FORTRANではプログラムは一つの主プログラムと０個以上の副プログラムからなる。

global(大域)データ、すなわち二つ以上の単位で使用可能なデータは、COMMON文によって宣言することができる。また、それらが宣言されている単位の外では既知ではないlocal(局所)がある。

######ALGOL ALGOLではプログラムは一つのblock(ブロック)である。ブロックは自分自信の名前を宣言することができるプログラムの副単位である。

ALGOLはblock-structured language(ブロック構造をもつ言語)である。

有効範囲について

  1. ブロックBで宣言されたなま円は、ブロックBだけで有効。
  2. ブロックB'がBに入れ子になっているときは、Bで有効な名前は、その名前に体する識別子がB'で再宣言されていなければ、B'でも有効である。

######PL/I PL/Iのプログラム構造はFORTRANとALGOLの特徴を組み合わせたもの。PL/Iプログラムは外部手続きの集合からなり、そのうち一つが主プログラムとして区別される。ALGOLの手続きのようにその中にブロックおよび内部手続きを入れ子にすることができる。task(タスク)と呼ばれる種類の副プログラムによって二つ以上の手続きを同時に実行させる機能がある。

Raw
3.0.markdown

##字句解析

原始プログラムを１字ずつ読み込み、それをtokenの列に翻訳すること。regular expression(正規表現)という本質的にプログラミング言語のすべての字句を記述するのに用いることができる記法を導入する。

字句を認識するための機構。transition diagram(遷移図)とfinite automata(有限オートマトン)が、字句認識系を設計するのに都合がよい。

字句を規定するのに正規表現を用いる一つの利点は、その正規表現で表される字句に体する認識系を、正規表現から自動的に作ることができること。

####節

  1. [字句解析系の役割] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-1-markdown)
  2. [字句解析系を設計するための簡単な方法] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-2-markdown)
  3. [正規表現] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-3-markdown)
  4. [有限オートマトン] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-4-markdown)
  5. [正規表現から有限オートマトンへの変換] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-5-markdown)
  6. [DFAの状態数の最小化] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-6-markdown)
  7. [字句解析系を規定するための言語] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-7-markdown)
  8. [字句解析系の実現] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-8-markdown)
  9. [万能道具としての走査系生成系] (https://gist.github.com/raven38/18d3a16748f7fdd73705#file-3-9-markdown)
Raw
3.1.markdown

###字句解析系の役割

たいていは字句解析系と構文解析系は一つのパスとなってる。

######字句解析系の必要性

字句解析系と構文解析系を二つに分けるとコンパイラの設計が楽になる。

ほかにも、行番号を数えたり、必要なら出力リストを作ったり、余白を取り除いたり、コメント削除したりできる。

######入力バッファリング

字句解析系では、字句を見つけるための原始プログラムの文字と１文字ずつ走査する。しかし、次の字句を定めるにはその字句の先まで多くの文字を調べる必要がある。 それを解決する為に入力を入力バッファから読むようにするといい。 一つのポインタでいま見つけようとしてる字句の先頭をさす。lokkahead pointer(先読みポインタ)で先頭から字句が見つかるまで走査する。

######予備走査

文字を原始ファイルからバッファに移すときに行うのがもっともよい処理がいくつかある。注釈を取り除いたり不要な空白列を取り除いたりすることである。このような前処理を施すことで、先読みポインタを注釈や空白列の上で行ったり来たりさせる手間を省ける。

Raw
3.2.markdown

###字句解析系を設計するための簡単な方法

transition diagram(遷移図)と呼ばれるものを用いるといい。遷移図は、流れ図の箱は丸く描き、state(状態)と呼ぶ。状態はedge(辺)と呼ぶ矢印で結ぶ。状態から出ている辺の上の名札で、その状態後に現れ得る入力文字を示す。

######reseved word(予約語)

手掛り語を識別子として扱い、予め記号表に、それらが手掛り語であるという印をそれらの字句に対するコードと一緒に入れておけば、手掛り語を認識するための遷移図の部分を省くことができる。

Raw
3.3.markdown

###正規表現

######文字列と言語

特殊な文字列、empty string(空列)があり、εで表す。

xとyが文字列のときxとyのconcatenation(連接)は、x・yまたは単にxyと表し、xの記号全体にyの記号全体を続けた文字列を表す。空列と任意の文字列の連接は、後者の文字列である。εx = xε = xってこと。

連接は一種の積と考えることができる。

x² = xx
x³ = xxx
x⁰ = ε

という具合。

xが文字列の時、xの末尾の記号を0個以上取り除いてできる文字列をxのprefix(語頭)、反対にsuffix(語尾)という。substring(部分列)は、xから語頭および語尾とのぞいたもの。

言語には、これらの他に字句を規定する際に重要な役割を演じる演算子がある。 closure(閉包)すなわち任意個の演算である

######正規表現の定義

アルファベットΣ上の正規表現とは、以下の規則から作ることのできる表現のこと。

  1. εは正規表現である。、 {ε}、すなわち空列だけを含む言語を表す。
  2. Σ内の各aに対して、aは正規表現であり、{a}すなわち一つの記号からなる一つの文字列だけを含む言語を表す。
  3. RおよびSが正規表現であり、それぞれ言語Lr及びLsを表すものとすると
    1. (Ｒ)|(S)は正規表現であり、 Lr∪Lsを表す。
    2. (Ｒ)|(S)は正規表現であり、Lr・Lsを表す。
    3. (Ｒ)*は正規表現であり、Lr*を表す。

この定義は、recursive definition(再帰的定義)の一つの例である。すなわち正規表現は、基本的な正規表現(定義のbasis(基))と複合正規表現(induction(帰納))とから定義されている。

任意の正規表現R,S,Tに対してなりたつ公理

1. R|S = S|R                            (|の可換性)
2. R|(S|T) = (R|S)|T                    (|の結合性)
3. R(ST) = (RS)T                        (∙の結合性)
4. R(S|T) = RS|RT および (S|T)R = SR|TR  (∙の|に対する分配性)
5. εR = Rε = R                          (εは連接に対する単位元)
Raw
3.4.markdown

###有限オートマトン

######非決定性オートマトン

正規表現を認識系に変換するよりより方法は、正規表現がら一般化した遷移図を作ることである。この遷移図は有限オートマトンと呼ばれる。これは一般には単純なプログラムでは模倣することが容易にできないが、その変形で決定性有限オートマトンは容易に模倣できる。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment