言語工学 (Theory of Formal and Programming Languages)

Table of Contents

概要

プログラミング言語などの人工言語を処理する理論・技術は,コンパイラなどのプログラ ミング言語処理系の実現に限らず,計算機科学の様々な分野で必要なトピックである. 本講義では,人工言語を取り扱う理論であるオートマトンおよび形式言語について学び, またプログラミング言語処理系に関して学習する.

時限,教室,担当者

  • オートマトンと形式言語 (略称 FL)
    • 時限: 月曜日5限 (17:00〜18:30)
    • 教室: LR301
    • 担当者: 酒井拓史
    • オフィスアワー: 随時 (事前に連絡のこと)
  • プログラミング言語処理系 (略称 PL)
    • 時限: 水曜日2限 (10:40〜12:10)
    • 教室: 情報基盤センター分館 1F 第1演習室 (工学部教室棟の北側の建物)
    • 担当者: 田村直之, 番原睦則
    • オフィスアワー: 随時 (事前に連絡のこと)

担当者の連絡先は, http://www.csi.kobe-u.ac.jp/gaiyou/staff.html を参照のこと.

時間割コード

正しいコードで履修登録すること.

  • 1T307 (◎3 必修): 2016年度以降の入学生
  • 1N307 (○A 選択必修): 2015年度以前の入学生 (旧カリキュラムの言語工学の単位読替え科目)

成績評価方法

以下を総合して成績を評価する.

  • オートマトンと形式言語 (FL): 50点
    • 定期試験
  • プログラミング言語処理系 (PL): 50点
    • 出席状況 (必ず出席すること)
      • 病欠,忌引等の場合,病院の領収書など証拠となる書類を準備して,担当教員に相談すること.
    • 課題

成績は「うりぼーネット」を通じて発表する (BEEFでは発表しないので注意).

BEEF

注意

  • 授業をよりよくするための皆さんの提案・アイディアを歓迎します.
  • 授業の内容が理解できないときは遠慮無く質問してください.
  • Webテキスト等の内容は,更新のタイミング等により,講義中のものとは異なることがあります. また,他に転載はしないでください.

オートマトンと形式言語 (FL)

  • 毎週月曜日5限
  • 担当者(酒井)の指示にしたがって受講すること.

講義スライド

  • BEEF上で配布する.

プログラミング言語処理系 (PL)

  • 毎週水曜日2限
  • 担当者(田村,番原)の指示にしたがって受講すること.

BEEF

  • 出欠,課題提出などはBEEF上で行う.

この講義で学習するトピック

  • 関数型プログラミング
    • 基礎的な概念
    • Scala によるプログラミングの初歩
      • リスト処理 (collection)
      • (自由学習: 再帰プログラミング)
  • 正規表現
    • Scalaにおける 正規表現 の記述方法と利用方法
  • 文脈自由文法
    • 文脈自由文法の記述言語である EBNF (BNF の拡張)
      • 構文 (syntax), 構文規則, 対象言語, メタ言語
    • 字句解析, トークン
    • 構文解析, 構文解析器 (パーサー, parser), 構文木
    • Scalaで構文解析器を実現するための parser combinator, トップダウン構文解析
    • 前置記法 の構文解析
    • (自由学習: 挿入記法の構文解析)
    • (自由学習: 抽象構文木 (AST)の利用)

この講義で(残念ながら)触れていないトピック

  • Scalaのより進んだプログラミング
  • 構文解析のその他のトピック
    • ボトムアップ構文解析 (LR法など)
  • プログラミング言語処理系のその他のトピック
    • パーサジェネレーター(bisonなど)
    • 意味解析,コード生成,最適化など
    • 型検査,型推論など
    • 実行時ライブラリ,動的メモリ管理など

関連する概念や技術

  • 形式言語とオートマトン
    • 計算可能性理論 (チューリング機械など)
  • プログラミング言語処理系
    • コンパイラ,インタープリタ
  • 自然言語処理
    • 英語や日本語の処理など
  • データ処理
    • Webスクレイピングなど

Webテキスト

スケジュール(予定)

  1. DONE 2018-04-11 Wed
  2. DONE 2018-04-18 Wed
  3. DONE 2018-04-25 Wed
  4. DONE 2018-05-02 Wed
    • 課題1の説明
    • Scalaで言語処理: 4. 前置記法の電卓
      • 4.3 構文解析結果の表現
      • 4.4 構文解析結果の利用
      • 4.5 練習問題
    • (自習) 課題1に取り組む (提出締切 5/15)
  5. DONE 2018-05-09 Wed
    • Scalaで言語処理: 4. 前置記法の電卓
      • 4.6 複数引数への拡張
      • 4.7 練習問題
    • (自習) 課題1に取り組む (提出締切 5/15)
      • 課題1のヒントに説明を追加しました.
  6. DONE 2018-05-16 Wed
    • Scalaで言語処理: 6. 文法の拡張
    • 課題2の説明
    • (自習) 課題2に取り組む (提出締切 5/30 中)
  7. DONE 2018-05-23 Wed
    • (自習) 課題2に取り組む (提出締切 5/30 中)
      • 課題2のヒントに説明を追加しました.
      • IntelliJでの実行方法の説明を追加しました.
    • まとめ
  8. 自習 2018-05-30 Wed (予備日)
    • (自習) 課題2に取り組む (提出締切 5/30 中)
    • 出欠は取りません

課題1

  • Work1.scala の文字コードがUTF-8でない場合がありました. こちらで変換して採点しますが,気をつけてください. 以下のコマンドで文字コードをUTF-8にできます.
    $ mv Work1.scala Work1old.scala
    $ nkf -w <Work1old.scala >Work1.scala
    
  • 「対応した拡張の番号」が正しく記載されていない場合が多数見られました. この部分の記載は無視して採点します.
  • out1.txt がない場合,正しく作成されていない場合がありました. こちらで作成して採点しますが,気をつけてください.

2018-05-16 Wed 01:37 時点で103名提出. 正答数の分布,各入力行に対する正答者数は以下の通り.

正答数人数
06******
10
21*
30
40
51*
60
70
85*****
92**
1019*******************
116******
1211***********
1311***********
146******
1535***********************************
正答者数正答者の割合 (113名中)
19483%
29180%
39483%
49483%
59483%
69382%
79180%
89281%
97969%
107869%
115952%
124943%
134338%
146658%
156658%

Date: 2018-06-13 13:20:23 JST

Author: 田村直之,番原睦則,酒井拓史

Validate XHTML 1.0