コンパイラ 2012年10月11日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html.

Presentation on theme: "コンパイラ 2012年10月11日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html."— Presentation transcript:

1 コンパイラ 2012年10月11日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp)

2 構文図式 ＢＮＦと記述力は変わらない。 直感的でわかりやすい。 [プログラム] 関数定義 変数宣言 ; 返戻型 ブロック 識別子 ( ) ,
[関数定義] [変数宣言] 要素型 識別子 文 { } [ブロック]

3 [文] 式 return 条件式 ブロック 文 識別子 変数宣言 ; ( = if while ) 関数呼出し 識別子 式 ( ) , [関数呼出し] [式] 項 加減演算子 [項] 因数 乗除演算子

4 [条件式] 式 == != > < >= <= [加減演算子] [乗除演算子] + - ＊ / 要素型 void [数字]と[英字]は非終端記号なので、 本来はそれらも終端記号に至るまでの 定義が必要。しかし、省略されている。 前回のＢＮＦの例でも省略されている。 [返戻型] 数字 英字 [識別子] [整数] 数字 int [要素型]

5 字句解析(Lexical Analysis)
文字や文字の並びを、意味の有る字句として認識する。 自然言語では単語に分解することに相当する。 文法に基づき、予約語・識別子・演算子などに分解する。 識別子が関数名なのか変数名なのかは区別しない。 あくまで、単語に分解するだけである。 分解されたものは、文法上の構成単位である。 構文解析器の要求により動作する。 字句の要求に対する、字句への分解と字句の出力。 ソースプログラムからの文字の読み取り。 ファイルからのソースプログラムの読み込み。 読み込んだソースプログラムのバッファリング。

6 字句解析の位置づけ ソースプログラムという文字の並び（文字列）から、 意味のある字句の並び（字句）へと変換する。
ソースプログラムという文字の並び（文字列）から、 意味のある字句の並び（字句）へと変換する。 字句は構文解析器に渡される。 ソース プログラム 字句解析 構文解析 ; c + b = a a=b+c; 文字列 字句

7 字句解析器と構文解析器の関係 構文解析器（Parser）からの要求に基づき、 字句を返す。
構文解析器から字句が返却される場合もあり、 そういうときはバッファする。 効率良いコンパイルのためには、字句をできるだけ返却 しないで済むように文法を決める。 ソース プログラム 字句解析 構文解析 代入文の解析 条件分岐の解析 繰り返しループの解析 文字列 字句要求 字句 字句出力

8 文字読み取り 字句解析器はファイルからソースプログラムを 一文字ずつ読みながら解析する。
字句解析器はファイルからソースプログラムを 一文字ずつ読みながら解析する。 しかし、一文字ずつファイルから読むことは効率が悪い。 最近のＯＳなら、mmapしちゃえば？と思う。 字句への分解では、その区切りとなる文字を読んだとき に初めて字句が読み取れたことになる。一文字先読み が必要、あるいは、区切り文字の ungetが必要。 そういったことから、バッファリングをする。 mmapすれば、ファイルは仮想記憶機構を通じてメモリのよう に自由に読み書きできる。実装はライブラリ依存。

9 字句読み取り 文字を読むごとに字句解析器の内部に保持する 状態遷移機械の状態が遷移する。それにより、 文字列から字句へと分解される。
文字を読むごとに字句解析器の内部に保持する 状態遷移機械の状態が遷移する。それにより、 文字列から字句へと分解される。 例：＜その他＞を読んで初めて＜名前＞が分解できる。 ＜名前＞→＜英字＞｛＜英字＞｜＜数字＞｝ 2 1 ＜英字＞ ＜数字＞ ＜名前＞ ＜その他＞

10 正規表現と有限オートマトン オートマトン内部の状態数は有限。
ひとつの入力に対する状態遷移がひとつであるものは、 決定性有限オートマトンという。 オートマトンが受理する状態遷移系列を決定的に求められる。 字句解析や構文解析には「決定性」は必須の条件。 そうでないものは、非決定性有限オートマトンといい、 入力に対する状態遷移は神のみぞ知るということ。 オートマトンが受理する状態遷移系列を決定的に求められない。 これでもプログラムは書ける。が、コンパイルできない。

11 正規表現 sed, grep, perl, awk, ruby, pythonなど、それぞれの 正規表現を実装している。活用してますか？ ここでは簡単な例を示す。 斜体は正規表現、uplight体はアルファベット。

12 正規表現の表す言語 正規表現の表す言語とは、与えられた正規表現から 生成できる文字列の集合のこと。
正規表現の表す言語とは、与えられた正規表現から 生成できる文字列の集合のこと。 これを正規言語という。 結合の優先順位は、閉含・連接・集合和の順。