休講通知：コンパイラ

出張のため、7/4(水)の「コンパイラ」は休講とします。

「コンパイラ」第11回

• 実施日: 2007-06-27(水) 1限
• 講義内容: S属性定義、L属性定義、実行時環境（導入）
• 配布資料あり（7〜9章）

今回は、意味解析やコード生成での重要な技術である翻訳スキームのうち、性質のいいものとしてS属性定義とL属性定義のお話をしました。これらはいずれも、プログラム断片付き解析木を深さ優先に1回走査するだけで、ある計算を行うことができる翻訳スキームです。

「解析木を深さ優先に1回走査する」ということに拘るのには理由があります。講義でもお話した通り、コンパイラでは、解析木が大きくなる可能性があるため、走査の回数はなるべく減らしたほうが効率がよくなるのです。

ただし、講義では述べなかった理由がもう1つあります。LL(1)文法に基づく予測型構文解析では、トークン列を順次読みながら、根から葉に向かって解析木を成長させていきます。このとき、非終端記号と同名の関数を再帰的に呼び出していくのでしたね。予測型構文解析の場合，この関数の呼び出しは、ちょうど解析木を深さ優先探索にたどるのと同じ順番で行われます。ということは、解析木を実際に作らなくても、関数の再帰的な呼び出しを行うことで、あたかも解析木を深さ優先探索にたどるのと同等な処理ができるということになります。この関数の中に、S属性定義やL属性定義のプログラム断片を埋め込むと、何が起こりますか？解析木を作らなくても、翻訳スキームの計算が行えることになります。しかも、構文解析と意味解析が同時に行えてしまいます。現実のコンパイラの設計では、むしろこの理由のほうが重要なのです。

今日の講義では、最後のトピックであるコード生成の話に向けた準備として、プログラム実行時にCPUやレジスタ、メモリ周辺で何が起こっているか、簡単にお話しました。この話の基本的なところは先行科目「計算機アーキテクチャA」で説明があったはずです。ただし、現実のプログラムでは、実行時の記憶領域割り付け（局所変数やmalloc()など）、関数呼び出しなど、より複雑なことを考えねばなりません。次回はこの辺の話をして、さらにコード生成について簡単にお話したいと思っています。

レポート課題：形式言語理論

「形式言語理論」の受講者は以下のレポート課題を提出して下さい。これをもって定期試験の代わりとし、成績評価を行います。

1. 課題内容：教科書の練習問題のうち、問2.5.1, 問4.4.2, 問5.3.2, 問5.4.1
2. 提出場所：2610。部屋の前に提出用の箱、もしくは袋を出しておきます。
3. 提出期限：2007/07/31(火) 17:00
4. レポート形式：A4サイズの紙を使うこと。そのほかは自由。
   

休講通知：形式言語理論

出張のため、7/3(火)の「形式言語理論」は休講とします。

「形式言語理論」第10回

• 実施日: 2007-06-26(火) 1限
• 講義内容: プッシュダウンオートマトン
• 教科書6.1節, 6.1.1〜6.1.2項

今回はプッシュダウンオートマトンを紹介しました。直観的には、プッシュダウンオートマトンはスタックを1本持つ非決定性の有限機械であり、文脈自由文法と等価な言語表現能力を持ちます。有限オートマトンと異なり，プッシュダウンオートマトンには、受理する言語の定義が2通りあります。入力を読み切ったとき(1)受理状態にたどりついていれば受理(2)スタックが空になっていれば受理、というものです。

次回はこの講義の最終回として、この2つの受理の定義が等価であること、そしてプッシュダウンオートマトンと文脈自由文法が等価であること、この2点について説明をします。

岡山県立大学「データベース」第9回

• 実施日: 2007-06-22(金) 2限
• 内容: SQL（SELECT文以外の構文）、一貫性制約、外部キー制約
• 講義ノート

今回はSQLのうち、SELECT文以外の構文の主なものについてざっとお話をしました。岡山理科大学の講義との違いはほとんどありません。VARCHAR（可変長文字列のデータ型）についてもご紹介した程度だと思います。

SQLと言えばSELECT文が最も有名なのは間違いないところで、いちばん教えやすい構文でもあります。ですが、講義の最初にお話をした通り、 SELECTだけでは関係データベースは全く使えません。私が皆さんのように大学生だった頃、やはり講義と現実のシステムとのギャップに苦しみました。そ んな経験もあって、関係データベースを実際に使う局面を想定して、必要となる構文を簡単にご紹介しました。

今回の講義では、もうひとつ、一貫性制約（integrity constraints）という考え方をお話しました。これは、関係データベース中の表がいついかなる瞬間でも満たさなければならない条件であり、定義域 制約、キー制約、外部キー制約など（他にもいくつかあります）があります。CREATE TABLE文で表を作成するときにこれらの制約を書いておくと、関係データベースが自ら、これらの制約が成立しているかどうかを検査してくれるのです。こ れは、データベースを利用するプログラムを開発する人にとっては、とても大きな利点になります。（実際にプログラムを書かないとこのご利益はなかなか実感 できないと思いますが…）

外部キー制約は、この講義で初めて登場しました。データベースの教科書では厳密さを重視して数式による定義をしがちですが、この講義では厳密さよりも分か りやすさを追求し、直観的な説明を行いました。表でデータを整理するとき、外部キーの考え方は結構頻繁に登場しますので、どのようなものか理解しておいて ほしいと思います。

岡山理科大学「データベース」第10回

• 実施日: 2007-06-21(木) 7・8限
• 内容: SQL（SELECT文以外の主要構文）、一貫性制約、外部キー制約
• 講義ノート

今回はSQLのうち、SELECT文以外の構文の主なものについてざっとお話をしました。

SQLと言えばSELECT文が最も有名なのは間違いないところで、いちばん教えやすい構文でもあります。ですが、講義の最初にお話をした通り、SELECTだけでは関係データベースは全く使えません。私が皆さんのように大学生だった頃、やはり講義と現実のシステムとのギャップに苦しみました。そんな経験もあって、関係データベースを実際に使う局面を想定して、必要となる構文を簡単にご紹介しました。

今回の講義では、もうひとつ、一貫性制約（integrity constraints）という考え方をお話しました。これは、関係データベース中の表がいついかなる瞬間でも満たさなければならない条件であり、定義域制約、キー制約、外部キー制約など（他にもいくつかあります）があります。CREATE TABLE文で表を作成するときにこれらの制約を書いておくと、関係データベースが自ら、これらの制約が成立しているかどうかを検査してくれるのです。これは、データベースを利用するプログラムを開発する人にとっては、とても大きな利点になります。（実際にプログラムを書かないとこのご利益はなかなか実感できないと思いますが…）

外部キー制約は、この講義で初めて登場しました。データベースの教科書では厳密さを重視して数式による定義をしがちですが、この講義では厳密さよりも分かりやすさを追求し、直観的な説明を行いました。表でデータを整理するとき、外部キーの考え方は結構頻繁に登場しますので、どのようなものか理解しておいてほしいと思います。

「コンパイラ」第10回

• 実施日: 2007-06-20(水) 1限
• 内容: 記号表、翻訳スキーム
• 配布資料あり（6章）

今回から意味解析に入ります。意味解析では、構文解析まででは検査できない制約を解析しますが、字句解析や構文解析のようにすべて数学的な背景があるわけではありません。変数の宣言に関する制約（使用される前に宣言されていなければならない）は、記号表というデータ構造を使うことで、プログラム技術として解決されることが多いです。

この講義では、記号表について簡単に触れた後、意味解析で用いられる理論的道具として翻訳スキームと呼ばれるものを紹介します。これは解析木にプログラムの断片を埋め込み、これを深さ優先に1回走査して順次実行することで、解析木に対する処理を実行しようというもので、属性文法と呼ばれる理論の特別な場合にあたります。意味解析ばかりでなく、コード生成にも用いられる技術です。

今回は翻訳スキームの応用例として、中置記法の式を後置記法の式に変換する方法を紹介しました。また、翻訳スキームで用いられる変数の制限についても紹介しました。次回は、これを基に、どのようなプログラム断片なら翻訳スキームに用いることができるのか、もう少し考察を加えます。なお、中置記法、後置記法については、コンパイラとは関係なく有用な考え方ですので、知っておいて下さい。

「形式言語理論」第9回

• 実施日: 2007-06-19(火) 1限
• 内容: 文脈自由文法の性質・応用、構文木との関係
• テキスト5章

講義の回数が残り少なくなってきたため、内容を選びながら駆け足でお話をしつつあります。今日は、前回に引き続き、文脈自由文法についての説明を行いました。ざっともう一度文脈自由文法を復習した後、構文木（解析木）、文法の曖昧性、応用例（構文解析系、構造化文書の構文の定義）についてお話しました。次回から、次のトピックとしてプッシュダウンオートマトンの話をします。

テクノラティプロフィール

岡山県立大学「データベース」第8回

• 実施日: 2007-06-15(金) 2限
• 内容: SQL（自己結合、ORDER BY, GROUP BY, HAVING、入れ子問合せ）
• 講義ノート

今日の講義では、SELECT文の続きとして、自己結合、表の加工、入れ子問合せについてお話しました。表の加工はあまり理論的な話ではありませんが、現実には使う頻度が高い（特にORDER BY）ので、知っておいて損はないと思います。

今日の講義ノートには、時間の関係で講義中では簡単にお話したところも説明を加えています。興味のある人は読んでみて下さい。また、集計関数COUNTの説明が少し間違っていたので直しておきました（次回の講義の最初に説明します）。

次回は、SELECT文以外のSQLの構文についてお話していきます。

岡山理科大学「データベース」第9回

• 実施日: 2007-06-14(木) 7・8限
• 内容: SQL（自己結合、SELECT文のORDER BY, GROUP BY, HAVING、入れ子問合せ）
• 講義ノート

SELECT文の最後として、関係代数には含まれない機能である表の加工について主にお話しました。今日の内容はあまり理論的なものではありませんが、実際にSQLを使う場合、並べ替えや集計は割と使う機能ですので、知っておくと便利だと思います。

なお、今回の講義ノートには、時間の関係で講義中では省略した説明を「発展的な話」として入れています。興味のある人は読んでみて下さい。また、集計関数のうちCOUNTについて、講義では少し間違った説明をしてしまいました。講義ノートでは直してあります（次回の最初に説明しようと思います）。

次回はSQLの落ち穂拾いとして、SELECT文以外の構文についてお話していきます。

「コンパイラ」第9回

• 実施日: 2007-06-13(水) 1限
• 内容: LL(1)文法（FOLLOW()関数、判定法）、構文解析プログラム
• 配布資料5.3節、5.4節（5.5節は時間の都合で割愛）

前回に引き続きLL(1)文法の説明を行い、最後にLL(1)文法に対する予測型構文解析プログラムの概略を説明しました。前回説明したFIRST()関数に比べて、FOLLOW()関数は、どういうものか、なんのために必要か、ややつかみにくいかと思います。そのため、かなり時間をかけて説明をしました（その結果、プログラムの説明の時間がなくなってしまいました…）。

講義で使った例（配布資料を作成した後に考えた例なので、資料には載っていません）を再掲します。

S→aAB, A→b|c|ε, B→d

このような文法に対して、終端記号列adの構文解析を考えてみます。最初の文字aを読んで、SをaABに展開します（Sの子節点にa, A, Bを作成して解析木を成長させる）。次の文字dを読んで、Aを展開しようとしますが、A→b|c|εについて、FIRST(b), FIRST(c), FIRST(ε)のいずれにもdは含まれません。では構文解析は失敗なのか…というと、そうではなく、Aをεに展開し、さらにBをdに展開すると、成功します。この例から分かるように、FIRST()関数だけでは、次に出現し得る終端記号を列挙し切れない場合があるわけです。これがFOLLOW()関数を導入する理由です。

FIRST()関数、FOLLOW()関数、LL(1)文法かどうかの判定は、是非自分で手を動かして計算してみて下さい。

次回から意味解析に入ります。

「形式言語理論」第8回

• 実施日: 2007-06-12(火) 1限
• 内容: DFAの状態数最小化、文脈自由文法
• 教科書4.4節、5.1節

長らくかかった有限オートマトンの話の最後として、DFAの状態数最小化アルゴリズムについてお話しました。理論的にも実用的にも興味深いものなので、アルゴリズム、これによって何が嬉しいのか、等の点について知っておくと後々役に立つこともあるかと思います。

次のトピックとして、文脈自由文法とプッシュダウンオートマトンを取り上げます。文脈自由文法については学部講義の「コンパイラ」でもお話しましたので、今回はその復習がてら、どのようなものであったかをざっとお話ししました。残り回数が少々心配になってきたので、この講義では、文脈自由文法と構文木（「コンパイラ」では解析木と言っていたもの）の関連、そして文脈自由文法と等価なオートマトンであるプッシュダウンオートマトンとの関連について、主にお話していこうと思っています。

岡山県立大学「データベース」第7回

• 実施日: 2007-06-08(金) 2限
• 講義内容: SQL(1) （SELECT文の概要）
• 講義ノート

今日の講義から、この講義の第2のヤマ、SQLの説明に入りました。SQLの構文は多岐に渡りますが、その中で最も代表的なSELECT文をまず取り上げます。SELECT文は SELECT ... FROM ... WHERE ... という形をしており（他の句がつくこともあります）、概ね「FROM句で指定した表からWHERE句で指定した条件を満たす組についてSELECT句で指定された書式の表を出力する」という意味になります。今日の講義で示した通り、これらの句の指定をいろいろ代えることで、関係代数の選択、射影、結合、自然結合（これは来週取り上げます）に相当する問合せを記述することができるようになっています。

今日の講義で説明したJOIN句は、教科書になりそうな書籍には書かれていない構文ですが、実際の関係データベースでは結合を表す構文として使われています。まずはJOIN句を使わない書き方ができるようになって頂ければよいと思いますが、実際にはJOIN句も使われますので、そのつもりで知っておいて頂ければと思います。

岡山理科大学「データベース」第8回

• 実施日: 2007-06-07(木) 7・8限
• 内容: SQL(2) （SELECT文のWHERE句）
• 講義ノート

前回に引き続き、SQLのSELECT文の説明です。今日はWHERE句の使い方について説明しました。WHERE句は組を選び分ける条件を記述する部分で、関係代数で言うところの選択条件や結合条件に相当します。1つの表を対象にすると選択条件に、2つ以上の表を対象にすると結合条件になるわけです。SELECT文は選択、射影、結合、自然結合などをすべてカバーする構文になっているのですね。

講義中でお話した通り、結合については、最近JOIN句を用いた新たな構文も使われるようになっています。教科書に使われるような書籍ではあまり触れられていない構文ですが実際に使われているので、この講義ではご紹介するようにしました。

「コンパイラ」第8回

• 実施日: 2007-06-06(水) 1限
• 内容: 構文解析(1) …文脈自由文法との関係、LL(1)文法（概要、FIRST()）
• 配布資料あり（第5章）

前回までお話した文脈自由文法を基に、構文解析の話を始めました。構文解析には大きく分けて下向き構文解析と上向き構文解析がありますが、この講義では下向き構文解析、しかもその特殊な場合である予測型構文解析についてのみ扱います。

文脈自由文法は導出を繰り返すことで終端記号列を得る仕掛けであり、一方構文解析はトークン列（終端記号列）を順次読んで解析木を得る処理です。両者は関係ありそうで関係なさそう、というように見えます。一つの解釈としては、導出により得られた記号列（文形式）を先頭から順次入力記号列と照合していき、その過程で解析木を作っていく、というものが考えられます。この講義では、この解釈に基づいて文脈自由文法と下向き構文解析を結びつけました。この解釈に従えば、予測型構文解析は、導出の際、どの規則を用いて非終端記号の展開を行うかが一意に決められるような下向き構文解析であり、対象とする文脈自由文法には制限があります。このような文法の一つがLL(1)文法です。

ある文法がLL(1)であるかどうかは機械的に判断することができます。その手法で用いられる考え方がFIRSTとFOLLOWです。今回はまずFIRSTについてお話しました。注意しなければならない点は、文脈自由文法では、非終端記号からεが導出される（つまり非終端記号から終端記号列が全く生成されない）ことがある、ということです。この事を念頭に置いて、FIRSTやFOLLOWの求め方、LL(1)文法の判定を読んで下さい。

「形式言語理論」第7回

• 実施日：2007-06-05(火) 1限
• 講義内容：閉包性を持つ正則言語の演算（4.2節）、反復補題（4.1節）、オートマトンの状態数最小化（4.4節、アイデアのみ）

有限オートマトンや正則表現に関する最後の話題として、正則言語に関する性質を取り上げます。この章で重要なのは、正則言語にどのような演算を施すと正則言語になるのか（閉包性）、どのような言語が正則ではないのか（反復補題）、それにオートマトンの状態数最小化です。

日程の都合上、閉包性に関してはほとんど事実のみを示し、共通部分の証明（直積構成法）のみ概略を示しました。また反復補題についても、正則でない言語の典型例である {0^n 1^n | n ≧ 1} についてのみ概略を示すにとどめました。学問を追究するという意味では不十分ですが、時間を考慮して、アイデアの理解を優先した結果です。興味のある方はテキストなりでより深く勉強していただければと思います。

オートマトンの状態数最小化については、実用上も重要な技術なので、時間を割いて説明するつもりです。まず今日のところは、おおざっぱなストーリーだけ示しました。次回、手法の詳細について説明します。

岡山県立大学「データベース」第6回

• 実施日: 2007-06-01(金) 2限
• 講義内容: 関係代数（商）、関係論理、SQLの導入
• 講義ノート

今回はまず練習問題の解答例を述べた後、関係代数で唯一残った演算である商を説明しました。その次に、関係データベースのもう一つの数学的理論である関係論理について、ほんのさわりだけ説明しました。関係論理は現実のデータベースシステムで使われるわけではありませんし、割と記述が難しいので、あまり深くは述べません。組についての性質を論理式で記述する、という点において、次に述べるSQLと類似性があります。その点のみ理解しておいて下さい。

SQLについては、今回は、代表的構文であるSELECT文の例を2つほど出すにとどめました。次回に述べるつもりですが、SQLは、関係データベース管理システムの構成と深く関連しています。そこで、まず関係データベース管理システムについて詳しく説明した後、SQLの話に入っていこうと思っています。

岡山理科大学「データベース」第7回

• 実施日：2007-05-31(木) 7・8限
• 内容：関係データベース管理システムの概要、SQL(1)
• 講義ノート

今日からこの講義の第2のヤマ、SQLの話に入りました。SQLというと、とかくSELECT文のみが取り上げられることが多いです。

確かにSELECT文が代表的であることは間違いないですし、講義をしていても面白い部分です。ですが、SQLはSELECT文だけではなく、そのほかに非常に多くの構文を含んでいます。そして、それらの構文は一般的な関係データベース管理システムの構成、使われ方に深く関わりがあります。そのためこの講義では、SQLに入る前に関係データベース管理システムの構成、使われ方等についてかなり時間をかけて説明しました。その後、SELECT文のお話を始めました。

今回はまずSELECT句、FROM句の役割についてのみ、例を用いて説明しました。次回はWHERE句の役割から話を始める予定です。