「コンパイラ」第7回

• 実施日：2007-05-30(水) 1限
• 内容：最左導出、最右導出、文法の曖昧性、左再帰とその除去方法、文脈自由文法の限界（４章最後まで）

早いもので、もう前期の講義の折り返し点なんですね。果たしてコード生成まで行くのか、かなり不安が残りますが、まあそれはともかく。

今日は、配布資料の4章の最後までをお話ししました。次週から構文解析の手法に入りますが、その際に最左導出がひじょうに関係してきます。また、曖昧でなく左再帰のない文法を対象とします。その意味で、今日の話は次週以降に関連してきますので、理解しておいてほしいと思います。

最後にお話しした文脈自由文法の限界はどう感じられたでしょうか。コンパイラで用いられる手法には、正則表現や文脈自由文法といった理論的なものの他に、かなり泥臭いものもあります。それは、ここでお話ししたように理論的な手法に限界があって、現実的な手法で解決したほうが楽である、という理由によることも多いです。こういう「清濁合わせ飲む」みたいなところが、コンパイラの話をややこしくしている一つの原因のような気がしているのですが、なるべく整理をしてお話ししていきたいと思っています。

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

• 実施日: 2007-05-25(金) 2限
• 内容: 関係代数(2)…直積、結合、自然結合
• 講義ノート

今日は関係代数の2回目として、直積、結合、自然結合という演算について述べました。これらが2つの表から1つの表を作り出す基本的な演算であり、特に自然結合は頻繁に用いられます。講義の最後に、どう自然結合を使うかという例を一つ示しました。この使い方が典型例ですので、よく理解しておいて下さい。

ところで、今日の最後に出した練習問題のうち、(1)がどうも間違っていたような気がします。正しくは「県大生がアルバイトをしている会社名」です。「名前」と書いたような気がして仕方ないのですが、名前では何のことやら分かりませんよね。正しい問題を講義ノートのほうに書いてありますので、参考にして下さい。

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

• 実施日：2007-05-24(木) 7・8限
• 内容：関係代数（商）、練習問題の解説
• 講義ノート

今回は、関係代数の演算のうち説明できていなかった商について説明した後、前回お配りした練習問題についての解説を行いました。今日の解説で分かる通り、関係代数による問合せは多くの場合以下のような形になります。

• 入力となる表が1つの場合：選択で組を絞り込み→射影で必要な属性を残す
• 入力となる表が2つ以上の場合：自然結合で1つの表にまとめ→選択で組を絞り込み→射影で必要な属性を残す

今回の練習問題の大半はこのパターンです（一つだけ、これにあてはまらない問題が含まれています）。

ただし、問題を解くには（そして実際にデータベースを操作するときには）まず日本語で書かれた問合せの意味を読み取る必要があります。また、今日の解説では具体的な表の例を出して説明をしましたが、実際の問題では、表の例は示さず、表のスキーマだけ示して問合せを書いてもらうことになると思います。関係の操作に慣れていない場合は、表のスキーマから具体的な表の例を作り、それを基に問合せを考えるようにして下さい。

休講：形式言語理論

5/29(火)は創立記念日のため、「形式言語理論」の講義は休講とします。

「コンパイラ」第6回

• 実施日: 2007-05-23(水) 1限
• 内容: 文脈自由文法（4.1〜4.2節あたり）
• 配布資料あり（第４章）

今日から次のトピックである構文解析の話に入りました。今回はまず、構文解析とはどのようなものなのか復習がてらお話しした後、その理論的背景になっている文脈自由文法について、定義、意味をお話ししました。ポイントは、文脈自由文法は文字列を導出する道具であり、導出の過程が木で表現できること、導出の過程を表す木（解析木）が構文解析の出力になること、トークン列を順次読みながら解析木の生成を行うことが構文解析であること、などです。

文脈自由文法に関する性質のうち、構文解析で必要ないくつかについては次週に、そのほかの詳細については、大学院の講義「形式言語理論」でお話しする予定です。

「形式言語理論」第6回

• 実施日: 2007-05-22(火) 1限
• 内容: 3.2節（正則表現とFAの等価性）、4.2.1節（正則言語の集合和、補集合に関する閉包性）

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

• 実施日: 2007-05-18(金) 2限
• 講義内容: 関係代数(1)…集合演算、選択、射影
• 講義ノート

今回から2回程度をかけて、この講義の最初のヤマである関係代数の紹介をします。関係代数を構成する演算はいずれも表に対するものであり、閉包性があります。今回お話した選択、射影は特に重要な演算ですので、どういうものか充分理解しておいて下さい。

定期試験には、最後に出した練習問題のような形の問題を出すつもりです。次回の最初に解答例を示しますので、今日の講義の内容の確認のつもりで考えてみて下さい。

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

• 実施日: 2007-05-17(木) 7・8限
• 講義内容: 関係代数(2) … 射影、直積、結合、自然結合
• 講義ノート

前回に引き続き、関係代数の演算を紹介しました。これで、残るはあと1つ（商）となりました。次回はこの紹介と、具体的に表に対してある操作を行いたいとき、関係代数でどのように表現すればよいか、練習問題を通してお話ししたいと思います。

最後のほうのお話はあまりうまくしゃべれませんでした。直積や結合、自然結合では、異なる表2つを対象とするとは限りません。同じ表に対して直積や結合、自然結合を適用することも可能である、ということがお話ししたかったのでした。もう少しいい例を考えて、改めて皆さんに示したいと思っています。

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

• 実施日：2007-05-11（金） 2限
• 内容：キー（超キー、候補キー、主キー）
• 講義ノート

今日は「関係中の組を識別する」というテーマで、キーという考え方について説明しました。前回にも述べた通り、関係は組の集合であり、組の出現順、属性の出現順は任意です。したがって、行数や列数に頼らずに組を指し示す必要があります。そのための概念がキー（key）です。関係データベースではよく用いられる概念なので、どういうものか、超キー／候補キー／主キーの区別、キー制約などについて理解しておいて下さい。

次回から関係代数の説明に入ります。

休講：形式言語理論

5/15(火)の形式言語理論は休講とします。

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

• 実施日：2007-05-10(木) 7・8限
• 内容：関係代数(1)…集合演算、選択
• 講義ノート

今日から、本講義のヤマの一つ、関係代数の話を始めました。関係代数を構成する演算はいずれも表を入力として表を出力するものであり、閉包性を持っています。そのため、表に加工を繰り返し、目的となる表を得るという操作ができるわけです。

今日はまず、表に対して演算（操作）をするとはどういうことか、慣れてもらうために、ひじょうに丁寧にお話をしました。特に選択は関係代数の中でも極めて重要な演算の一つです。次回は続きとして、関係代数の残りの演算についてお話をする予定です。

休講：「コンパイラ」

5/16(水) のコンパイラの講義は休講とします。

「コンパイラ」第5回

• 実施日：2007-05-09(水) 1限
• 内容：字句解析プログラム（配布資料3.4.1〜3.4.3節）
• 資料の訂正
• p.21 1行目：int initial_state; → int start;
  

今日は、実際の字句解析プログラムの中身についてかなり丁寧にお話ししました。学生さんの傾向として、アルゴリズムを考えることはできても、それを実際のプログラムに直すことができない、という例をたくさん見てきました。そのために、アルゴリズムからプログラムに直す例としてお話を進めたつもりです。

3.4.4節、3.5節は省略し、次回から構文解析に入ります。

「形式言語理論」第5回

• 実施日：2007-05-08(火) 1限
• 内容：ε-NFA, 正則表現とその代数的性質
• 教科書2.5節、3.1節、3.4節

来週の講義は休講にするかもしれません（まだ未定）。休講の場合は、掲示を出すとともにここのブログにその旨投稿しますので、注意しておいて下さい。

「コンパイラ」第4回

• 実施日: 2007-05-02（水）1限
• 講義内容：字句解析(1)　（配布資料3.3節まで）
• 配布資料あり

今日は字句解析の話を始めました。まず基本的な枠組について述べた後、正則表現／有限オートマトンを利用した字句解析の方法、考慮しなければならない問題と解決策（オートマトンの優先順位、先読み）についてお話ししました。次週は続きとして、具体的な字句解析プログラムについて述べる予定です。

「形式言語理論」第4回

• 実施日: 2007-05-01(火) 1限
• 内容: DFAとNFAの等価性、FAの応用(テキスト検索)
• 教科書2.4.3節まで

前半では、言語クラス、等価性、模倣（simulation）の話をしました。いずれも教科書ではあまりはっきり書かれていませんが、この講義の内容を理解する上で基本となる考え方なので、丁寧に話してみました。「ある」言語／DFA／NFA／…と「すべての」言語／DFA／NFA／…の違いに充分注意しておいて下さい。

教科書を申し込まれた方は、次回の講義時に2,734円を釣り銭のないように持ってきて下さい。