☆プログラミング言語
◎形式言語理論
※形式言語の規定
生成文法による
文を受理する装置による（オートマトン）
◆チョムスキー階層
Chomsky hierarchy
生成文法を言語学に適用した
句構造文法の書き換え則に３段階の制約を与え、階層的に規定する
０型 句構造
１型 文脈依存 自然言語
２型 文脈自由 プログラミング言語
３型 正規
⇒制約のない０型から制約の強い３型まで
⇒０から３に包含関係
◆言語の定義と種類
文字集合の定義
語の定義
任意の記号の並びの集合
任意の記号の並びの「文法規約を満たす」部分集合を言語と規定する
◆句構造文法
句構造文法のグラマーＧ
G=(N,T,P,S)
N non-terminal symbol 非終端記号の集合、Gによる文を表す
T terminal symbol 終端記号の集合、Nの部分集合、個々の記号。置換不可
P production rule 書き換え規則。N,T間の書き換え規則。
⇒句構造文法ではPの制約はない。
S start symbol 開始記号。最初の非終端記号
◆文脈依存文法
書き換え規則が前後の文脈に依存する
◆文脈自由文法
書き換え規則は前後の文脈に依存しない
＿◇BNF
Backus-Naur Form
①<> <>内の記号列はメタ変数
②::= 左辺は右辺のように定義される
③| または
④その他の記号 記号そのもの
⑤要素の並び 各記号の順に並べられた列
※メタ言語。ある言語の文法を説明するための言語
※対象言語。説明の対象となる言語そのもの
※拡張BNF
{}もしくは[]を使って繰り返しを表現する
◎オートマトン理論
automaton
※アルゴリズムをモデリング化し、定式化したもの
※入出力テープと有限状態制御装置から構成される
→状態遷移にもとづき問題解決手順をモデル化する
◆有限オートマトン
FNA(Finite Automaton)
※正規言語を受理できる
※入力テープと有限状態制御装置からなる。出力はない。
FNA=(Q,Σ,δ,q0,F)
Q 有限個の状態の集合
Σ 入力される有限個の記号
δ 状態遷移関数
q0 初期値状態
F 最終状態
Q={q0, q1, q2, q3}
Σ={s1,s2}
δ{q0,s1}=q2, …
F={q3}
※状態遷移図がかける
◆プッシュダウンオートマトン
※文脈自由言語を受理できる
※有限オートマトンに、プッシュダウンストア（スタック）を加えたもの
◆線形有限オートマトン
※文脈依存言語を受理できる
◆チューリングマシン
※句構造言語を受理できる
※入力だけでなく出力もある
※あらかじめ内部状態が記憶されている
⇒任意のTMとそのデータの入力により、どんなTMの動作も模倣できるチューリング機会を万能機械(UM:Universal Machine)と呼ぶ。
….◎各種プログラミング言語
◎各種プログラミング言語
※プログラミング・パラダイム
◆手続き型
◆関数型
◆論理型
◆オブジェクト指向型
◎トランスレータとインタプリタ
◆コンパイラ
＿◇解析
①字句解析
字句に分解し記号表に格納
②構文解析
文の構成と文法の検査
算術式
ポーランド記法（前置記法）
逆ポーランド記法（後置記法）
＿◇最適化
＿◇コード生成
☆言語プロセッサ
◎概要
◆処理ステップ
＿◇言語の定義、文法の記述
※字句解析も構文解析も文法が定義されていなければ行えない。
※BNF
Backus-Normal Form
Backus-Naur Form
ALGOL60の報告書で初めて用いられた文法表現法
⇒通常、この拡張記法を用いる
定義例）
<変数名>::=<英字>
<英字>::=A|B|C|D|E|F|G|
H|I|J|K|L|M|N|
O|P|Q|R|S|T|U|
V|W|X|Y|Z
※| は「または」
再帰的定義例）
<変数名文字列>::=<変数名>|
<変数名文字列><英字>
※{} 繰り返し
例）
{<英数字>}99
⇒英数字０～９９個
※[] 省略可能
例）
[STEP <式>]
⇒中かっこの後の数字が1と同じ
＿◇字句解析
lexical analysis
lexical scan
①プログラム文字列がどこで区切られるのか知る
②固定長のシンボルに直して並べる
⇒変数名ならば変数名表のインデックスに変換する
＿◇構文解析
syntax analysis
※算術式の構文解析
⇒つぎにどの演算を行うか優先順位の決定のために先読みが必要
２項演算
左から評価していって発見した演算子α1
左側の被演算子はその時点で定義済みβ1
右側の被演算子β２
単純変数
定数
算術式
⇒β２に続く演算子α２の優先順位が高ければ、
α１の実行は保留
β３を見つける作業に入る必要がある
⇒内部表現形式への変換の必要性
①逆ポーランド記法
⇒非常に簡単なアルゴリズムで行える。
⇒演算子の優先順位表を用いる
β１α１β２α２β３の形でα１を先にするか、α２か判断するスイッチ表
優先順位には（と）も含める
逆ポーランド記法への変換
スタック初期化
S） ソースを走査 無ければ⇒ 終了
ｘは変数か？ 変数ならｘを出力しS)へ
ｘは（か？ （をスタックに積んでS)へ
A) ｘは演算子か？
演算子のときはスタックトップのｙを見る）
ｙは（か？ ｘをスタックに積んでS)へ
ｘとｙではｘ優先 ｘをスタックに積んでS)へ
ｙ優先 ｙをスタックから降ろして出力、A)へ
演算子でないときは）
B)
ｘは）か？
ｙが演算子） ｙを出力、Bへ
ｙは（である ｘの）とｙの（を相殺し、S)へ
ｙが（でない エラー、S)へ
②木構造表現
⇒より効率のよいオブエジェクトを作りやすい
コーディング規約
◎Indian Hill C Style and Coding Standard
◎indent
①/*- */
生計プログラムindentに対して、そのコメントの内容の書式を変えないように指示する働きがある。
◎コメント
①FALLTHROUGH
lintに対して、意図的なcase文のスルーであると知らる
②NOTREACHED
プログラムの制御フローが決してその点に到達しないことを示す（警告を避けるため）
③リビジョン管理システムのタグ
$識別子$
%文字%
④コメント用の慣用語
XXX ただしくないが、ほぼ機能するコード
FIXME 間違っていて修正の必要のあるコード
TODO 将来機能拡張を図る場所
☆Tips
◆古いC言語処理系の互換性
＿◇VAX C
malloc(), free()
ヘッダファイル無し
※ANSI-C stdlib.h
＿◇Microsoft C（旧）
malloc(), free()
malloc.h
※ANSI-C stdlib.h
☆Algorithm
曖昧性なく定義された基本操作の有限系列として記述される。
※必ずしも有限停止が保証されていない場合
⇒手続き(procedure)
※有限停止が保証されている場合
⇒アルゴリズム
アルゴリズムは対象とする問題(problem)を解くという目的で書かれる。
⇒一つの問題は、通常、無限個の問題例(problem instance)からなる
⇒問題例は問題の記述に含まれるパラメタの値を具体化することで定義される。
⇒アルゴリズムは入力されるどのような問題例に対しても有限ステップで正しい解を求めて停止するものでなければならない。
※答えがあるかないかわからない／いつ結果が出るかわからない問題
⇒答えではなく最良の解／近似解を求める
☆OpenCL
Open Common Language
ヘテロジニアスコンピューティング環境
GPUが念頭にある
ロイヤリティフリー
クロノスグループが標準化
（⇒OpenGLも同様。OpenGLとの連携も考慮されている）
◆４つのモデル
＿◇プラットフォームモデル
＿◇実行モデル
＿◇メモリモデル
＿◇プログラミングモデル
☆GNUコーディング標準
◎書式
中カッコを別個の行に書く
if (ia-ia_maddr !_ MADDRUNK)
{
sc->pPacketPagePhys = ia->ia_maddr;
}
☆BSDスタイルガイド(apache,Perl準用）
◎記述順序
◆インクルード
①カーネルヘッダファイル
②/usrヘッダファイル
③ユーザーヘッダファイル
◎インデント
８文字幅のタブ
継続行はスペース４個でインデント
制御ブロック要素はスペース８個でインデント
◎書式
ステートメントと同じ行で中カッコを開き、そのインデントレベルで中カッコを閉じる
if ((cp = strchr(*argv,’:’) != NULL) {
*cp++ = ‘\0’;
a_gid(cp);
}
☆Javaコーディング規約
◎記述順序
①クラス変数
②インスタンス変数
③コンストラクタ
④メソッド
※変数とメソッドは、以下の順で定義する
private
protected
public
◎インデント
４個のスペース
もしくは８文字幅のタブ
◎コメント
①/** */
javadocツールに対してソースコードドキュメントを生成するように指示する。javadocキーワードは@文字で始まる
☆ハンガリアン記法
☆一般的なファイル名
README
プロジェクトの概要
MANIFEST
簡単な説明の付いたプロジェクトファイルのリスト
INSTALL
インストール手順
LICENSEまたはCopying
ライセンス情報
TODO
将来の拡張についての「欲しい物リスト」
NEWS
ユーザの目に見える変更に関するドキュメント
ChangeLogまたはChanges
コード変更サマリ
configure
プラットフォーム設定スクリプト
Makefile
ビルド指定
Makefile.SH
上記のものを生成するシェルスクリプト
config.h
プラットフォーム設定定義
config.h.SH
上記のものを生成するシェルスクリプト
version.hまたはpatchlevel.h
プロジェクトリリースバージョン
☆Seiwaldのプリティコードの７か条
①「本のよう」であること
②似たものは似て見えるようにすること
③字下げを克服すること
④コードをもつれさせないこと
⑤コードにコメントをつけること
⑥ごちゃごちゃにしないこと
⑦既存のスタイルに融け込むこと
◆プログラミング
＿◇手続き型プログラミング
FORTRAN, COBOL, Cなど
①データと処理が分かれている
②アルゴリズムで決められた順にデータを処理する
※発展
機械語 Machine Language
アセンブリ語 Assembly Language
高級言語 High-Level Language
＿◇オブジェクト指向
object oriented
※オブジェクトを使ってデータ処理をおこなう考え方
※プログラミング技法⇒オブジェクト指向プログラミング(Object Oriented Programming)
※オブジェクト
状態
ふるまい
識別性
※分散オブジェクト
Distributed Object
オブジェクトをネットワーク上のコンピュータに配置して連携動作させる
⇒例：クライアント側の代理オブジェクト（プロキシ）を通じてサーバ側のオブジェクトと通信する
※主な分散オブジェクト技術
DCOM, COM+, CORBA, JavaRMI, HORB
①クラスというオブジェクトの「型」
Class
⇒オブジェクトの実体であるインスタンス
Instance
C#: newによるインスタンスの作成
参照変数へnull代入による参照の解放
②オブジェクト
フィールド Field
プロパティ Property
メソッド Method
イベント Event
インタフェースを使った呼び出し方の定義
Interface
シグネチャを定義するだけ
③クラスの継承
Inheritance
基本クラス（基底クラス、スーパクラス）
派生クラス（サブクラス）
再定義によるポリモーフィズム
Polymorphism（多態性）
派生クラスで継承したメンバを再定義
Override
④カプセル化による隠蔽
Encapsulation
＿◇バリアント（variant)
ループインバリアント
ループの開始時と終了時の両方で成り立つもの
バリアント
ループの繰り返しごとにゴールに向かって変化するもの
☆デザインパターン
◆マルチスレッド
＿◇Single Threaded Execution
＿◇Immutable
＿◇Guarded Suspension
＿◇Balking
＿◇Producer-Consumer
＿◇Read-Write Lock
＿◇Thread-Per-Message
＿◇Worker Thread
＿◇Future
＿◇Two-Phase Termination
＿◇Thread-Specific Storage
＿◇Active Object
☆デバッグ
①失敗を観察する
②その失敗の原因について仮説を提案する
③予測をする。
④その予測をテストする
⑤適切な結論を出す
※過程は明示的に述べること。仮定と観察の記録を書き留めること。
※系統立っている。明確な仮設や仮説に基く予測がないまま、ランダムに何かを変えてはいけない。
※一番可能性の高い原因から調べる。
☆中間コード
◆Javaバイトコード
ドキュメントに書かれた命令順に１番から順にOPコードが割り振られている