コンパイラ 2012年10月11日 酒居敬一＠Ａ４６８(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/COMP/2012/index.html
構文図式 ＢＮＦと記述力は変わらない。 直感的でわかりやすい。 [プログラム] 関数定義 変数宣言 ; 返戻型 ブロック 識別子 ( ) , [関数定義] [変数宣言] 要素型 識別子 文 { } [ブロック]
[文] 式 return 条件式 ブロック 文 識別子 変数宣言 ; ( = if while ) 関数呼出し 識別子 式 ( ) , [関数呼出し] [式] 項 加減演算子 [項] 因数 乗除演算子
[条件式] 式 == != > < >= <= [加減演算子] [乗除演算子] + - ＊ / 要素型 void [数字]と[英字]は非終端記号なので、 本来はそれらも終端記号に至るまでの 定義が必要。しかし、省略されている。 前回のＢＮＦの例でも省略されている。 [返戻型] 数字 英字 [識別子] [整数] 数字 int [要素型]
字句解析(Lexical Analysis) 文字や文字の並びを、意味の有る字句として認識する。 自然言語では単語に分解することに相当する。 文法に基づき、予約語・識別子・演算子などに分解する。 識別子が関数名なのか変数名なのかは区別しない。 あくまで、単語に分解するだけである。 分解されたものは、文法上の構成単位である。 構文解析器の要求により動作する。 字句の要求に対する、字句への分解と字句の出力。 ソースプログラムからの文字の読み取り。 ファイルからのソースプログラムの読み込み。 読み込んだソースプログラムのバッファリング。
字句解析の位置づけ ソースプログラムという文字の並び（文字列）から、 意味のある字句の並び（字句）へと変換する。 ソースプログラムという文字の並び（文字列）から、 意味のある字句の並び（字句）へと変換する。 字句は構文解析器に渡される。 ソース プログラム 字句解析 構文解析 ; c + b = a a=b+c; 文字列 字句
字句解析器と構文解析器の関係 構文解析器（Parser）からの要求に基づき、 字句を返す。 構文解析器から字句が返却される場合もあり、 そういうときはバッファする。 効率良いコンパイルのためには、字句をできるだけ返却 しないで済むように文法を決める。 ソース プログラム 字句解析 構文解析 代入文の解析 条件分岐の解析 繰り返しループの解析 文字列 字句要求 字句 字句出力
文字読み取り 字句解析器はファイルからソースプログラムを 一文字ずつ読みながら解析する。 字句解析器はファイルからソースプログラムを 一文字ずつ読みながら解析する。 しかし、一文字ずつファイルから読むことは効率が悪い。 最近のＯＳなら、mmapしちゃえば？と思う。 字句への分解では、その区切りとなる文字を読んだとき に初めて字句が読み取れたことになる。一文字先読み が必要、あるいは、区切り文字の ungetが必要。 そういったことから、バッファリングをする。 mmapすれば、ファイルは仮想記憶機構を通じてメモリのよう に自由に読み書きできる。実装はライブラリ依存。
字句読み取り 文字を読むごとに字句解析器の内部に保持する 状態遷移機械の状態が遷移する。それにより、 文字列から字句へと分解される。 文字を読むごとに字句解析器の内部に保持する 状態遷移機械の状態が遷移する。それにより、 文字列から字句へと分解される。 例：＜その他＞を読んで初めて＜名前＞が分解できる。 ＜名前＞→＜英字＞｛＜英字＞｜＜数字＞｝ 2 1 ＜英字＞ ＜数字＞ ＜名前＞ ＜その他＞
正規表現と有限オートマトン オートマトン内部の状態数は有限。 ひとつの入力に対する状態遷移がひとつであるものは、 決定性有限オートマトンという。 オートマトンが受理する状態遷移系列を決定的に求められる。 字句解析や構文解析には「決定性」は必須の条件。 そうでないものは、非決定性有限オートマトンといい、 入力に対する状態遷移は神のみぞ知るということ。 オートマトンが受理する状態遷移系列を決定的に求められない。 これでもプログラムは書ける。が、コンパイルできない。
正規表現 sed, grep, perl, awk, ruby, pythonなど、それぞれの 正規表現を実装している。活用してますか？ ここでは簡単な例を示す。 斜体は正規表現、uplight体はアルファベット。
正規表現の表す言語 正規表現の表す言語とは、与えられた正規表現から 生成できる文字列の集合のこと。 正規表現の表す言語とは、与えられた正規表現から 生成できる文字列の集合のこと。 これを正規言語という。 結合の優先順位は、閉含・連接・集合和の順。