Microsoft PowerPoint - プログラムとは.pptx

Transcription

1 Formal Method Group 13:20~14:30 プログラムとは プログラミングとは 1. プログラミングとは 2. プログラムの構文論 3. プログラムの意味論 情報システム開発プログラム開発 IS-FMG, T.I.T. All Rights Reserved, 2008 IS-FMG, T.I.T. All Rights Reserved, 2008 Formal Method Group 情報システム開発 プログラム開発 外部設計仕様 要求仕様 自然言語による表現 高級言語プログラム 外部設計 要求分析 顧客 コーディング 図式化 定式化 図による表現 記号による表現 自然言語による表現 内部設計 これから学ぶところ コンパイラ 内部設計仕様 コーディング ソースプログラム 統合 統合されたシステム 稼動 テスト 完成したシステム アセンブリ言語プログラム アセンブラ 再配置可能機械語プログラム リンカーローダ 機械語プログラム CPU

2 自然言語表現 記号による表現 ソートの対象となっている配列の右端から順に一対比較をする もし大きいものが左にあるときには,2つの要素の順序を入れ替える これをまだ整列していないところまで, 繰り返す 整列したところまで行ったら, また右端から順に一対比較をする すべて整列したら終了する 1. i=0 とする 2. i=n であれば, 終了 そうでなければ 3 へ進む 3. j=n とする 4. j=i であれば ( パスの終了 ), i を 1 増やし,2 へ戻る そうでないときは,5 へ進む 5. X[j]<X[j-1] であるとき ( 大きさの順序が逆 ) には, X[j] と X[j-1] を入れ替える 6. j を 1 減らし,4 へ戻る 例 : バブルソートのフローチャート 開始 i:=0 Yes i=n? No j:=n Yes j=i? No Yes X[j]<X[j-1]? No Swap(X[j],X[j-1]) j:=j-1 終了 i:=i+1 高級言語プログラム : ソートの場合 Program Sort(input,output) Var i,j,n:integer; X:array[0..9] of integer; Begin write( 配列の長さを入力してください : ); readln(n); write( 配列を入力してください ); For i:=0 to n-1 do Begin Write( X[,I, ]= ); Readln(X[i]); End; i:=0; While i < n do Begin j:=n; While i<j do Begin If X[j] < X[j-1] Then Begin Temp:=X[j]; X[j]:=X[j-1]; X[j-1]:=Temp; End; j:=j-1; End; i:=i+1; End; End.

3 アセンブリ言語プログラム : ソートの場合 L0 L1 L2 L3 L4 START LEA GR1,0 ST GR1,i LD GR1,i CPA GR1,N JMI L2 EXIT LD GR1,N ST GR1,j LD GR1,i CPA GR1,j JMI L4 JMP L7 LD GR2,j LD GR0,X,GR2 LD GR3,j SUB GR3,ONE CPA GR0,X,GR3 JMI L5 JMP L6 L5 LD GR2,j LD GR0,X,GR2 LD GR3,j SUB GR3,ONE LD GR1,X,GR3 ST GR0,X,GR3 ST GR1,X,GR2 L6 LD GR1,j SUB GR1,ONE ST GR1,j JMP L3 L7 LD GR1,i ADD GR1,ONE ST GR1,i JMP L1 ONE DC 1 i DS 1 j DS 1 N DC 2 X DC 1 DC 7 DC 4 END 機械語プログラム : ソートの場合 プログラムの構文論 (syntax) 形式言語の構造 文法はいくつかの記号の集合と生成規則の集合からなる : G=<V N,V T,S,P> ある文法にしたがう文とは, 開始記号 S から生成規則を使ってできた, 終端記号だけからなる記号列のこと. 構文木 S Np Vp Np Det N V Det N the cat caught a bird IS-FMG, T.I.T. All Rights Reserved, 2008 Formal Method Group

4 文法の定義 G=<V N,V T,S,P> V N : 非終端記号の集合, V T : 終端記号の集合, V N V T =Φ S V N : 開始記号, P: 生成規則の有限集合, PgQ Pg Q どれが終端記号でどれが非終端記号化か判別できる ただし, P,Q,g,g (V N V T )* & g V T *. 終端記号は書換えられない 生成規則の表現 先の言語は, 次の生成規則からなる : S Np Vp Np Det N Vp V Np Det the Det a V caught N cat N bird 文法記述言語 ( 文法を記述するためのメタ言語 ) BNF(Backus Naur Form, Backus Normal Form) 記法による表現 メタ記号 ::=,, <, > がメタ記号 <> で囲まれた者はメタ言語変数 ::= で左辺を右辺で定義することを表している は または を意味している 先の生成規則は, 次のように表現される : <S>::=<Np> <Vp> <Np> ::= <Det> <N> <Vp> ::= <V> <Np> <Det> ::= the a <V> ::= caught <N> ::= cat bird 文法によって生成される言語 α * β とは, α β( ある PgQ とPg Qが, 各々 αとβに存在して,pgq Pg Q がPに存在する ) α * β,β β となるβ が存在する ( 帰納的定義!) このとき, 文法 Gで生成される言語を, L(G)={α S *α & α V T *} で表す

5 Q1:a,aa,aaa,aaaa, の生成 L(G)={a,aa,aaa,aaaa, } となる文法 G はどのようなものか G を明示するとともに 生成規則を BNF 記法で表せ プログラムの意味論 (semantics) 流れ図プログラム計算機械流れ図プログラムの計算プログラムの同値性 IS-FMG, T.I.T. All Rights Reserved, 2008 Formal Method Group プログラムに対する一つの見方 流れ図プログラム プログラムとは 基本的な操作と判定を計算機械に行わせる命令の構造を持った集合 である 操作名 :F,G,H,... 判定名 :T,U,V,... 代表的なプログラム 流れ図プログラム Whileプログラム 手続きプログラム 開始, 停止, 操作, 判定の 4 つの要素をある規則にしたがって組み合わせてできる幾何的な図式 開始 停止 操作 判定 F T 流れ図プログラムの例 F 開始 F T 1 F G T 2 T 停止 T

6 名札付き命令の集合としての流れ図プログラム 名札付き命令 名札 (label) とジャンプ (jump) を用いた, 名札付き命令の 集合として 流れ図プログラムを表現 例 1:do F then goto 2 開始 2:if T1 then goto 1 else goto 3 1 F 2 T 3:do G then goto 4 T 1 4:if T2 then goto 5 else goto1 F F 3 G 4 T 2 5 T 停止 構成要素 L:label の集合 F: 操作名の集合 T: 判定名の集合 名札付き命令 i I=(L {:} {do} F {then goto} L) (L {:} {if} T {then goto} L {else goto} L) λ:i L, λ(i) は左端のラベル 流れ図プログラムの定義 計算機械 定義 : 流れ図プログラム P I が流れ図プログラム ( i,j P)(λ(i)=λ(j) i=j) ( ( i,j P)(i j λ(i) λ(j))) 同じラベルの命令は一つしかないという性質を持つ 名札つき命令の集合 P(L): 流れ図プログラム P に出現するラベルの集合 l P(L) を一つ固定し, 始端ラベルと呼ぶ. l P(L) が終端ラベル ( i P)(l λ(i)) 計算機械はプログラムにおける操作と判定の意味を与える対象 M=<A,B,C,I M,O M,{F M F,G, },{T M T,U, }> が計算機械であるとは A: 入力集合 B: 出力集合 C: メモリ集合 I M :A C, 入力関数 O M :C B, 出力関数 F M :C C, 操作はメモリの変換 T M :C {T,F}, メモリの内容を判定 Tはtrue,Fはfalseを表す

7 計算機械の例 記憶の集合を AとBの2つのレジスタからなっているとし 操作と判定を各々 F A:=A-1 G B:=B+1 T A=0 とする計算機械 M=<A,B,C,I M,O M,{F M,G M },{T M }> は 次のように定めることができる : A=Z, B=Z, C=Z Z, I M :Z Z Z, I M (x)=(x,0), O M : Z Z Z, O M (x,y)=y, F M : Z Z Z Z, F M (x,y)=(x-1,y), G M : Z Z Z Z, G M (x,y)=(x,y+1), T M : Z Z {T,F}, true x=0 T M (x,y)= false o.w. 流れ図プログラムにおける計算 Pを流れ図プログラムとし Mを機械とするとき M 上でのPの停止する計算とは L Cの要素の有限列 (l 1,v 1 ),,(l n,v n ) で 次の条件を満足するものである : 1) l 1 は P の指定された始端ラベルで l n は P の終端ラベルの一つである 2) 1 j < nである任意のjに対して 次のいずれかが成立する : a) あるFおよびlに対して Pに命令 l j :do F then goto lが存在し l j+1 =lかつ v j+1 =F M (v j ) である b) あるT l l に対して Pに命令 l j :if T then goto l else goto l が存在し l T M (v j )=T l j+1 = l o.w. かつv j+1 =v j である 機械 M 上でプログラム P によって計算される関数 (l 1,v 1 ),,(l n,v n ) を機械 M 上でのプログラムPの停止する計算とする このとき 機械 M 上でプログラムPによって計算される関数 mp:x Yは mp(x)=o M (v n ) ( ただし v 1 =I M (x)) で定められる ( 停止しない計算に対しては mpは定義されない ) すなわち mp(x) は l 1 を始端ラベル v 1 =IM(x) としたとき (l 1,v 1 ) から始まる停止する計算 (l 1,v 1 ),,(l n,v n ) に対して定義され mp(x)=o M (v n ) である プログラムの同値性の定義 プログラムP,Qに対して, mp=mq が成立するならば,PとQは機械 Mに関して同値 (M- 同値 ) であると呼ぶ P,Qをプログラムとするとき, 任意の計算機械 Mに対して, M- 同値 すなわち mp=mqが成立するならば,pとqは強同値 (strongly equivalent) であると呼び,P Qで表す

8 機械の同値性 機械 M,M に対して, 任意のプログラムPを与えたとき,m Q=mPとなるプログラムQが存在するならば, 機械 M は機械 Mをシミュレートするという. M,M が互いにシミュレートするとき,MとM は互いに同値であるという. Q2: 強同値性の証明 ホワイトボードに描かれた 2 つの流れ図プログラムが強同値であることを示してみよう FYI [1] R. バード著 土居範久訳 プログラム理論入門 培風館 [2] 伊藤貴康 ソフトウェア工学基礎論 丸善 [3] B. メイヤー著 二木他訳 プログラミング言語理論への招待 アスキー出版局 1995.

9 本日の内容 情報システム基礎実験 第 3 回演習 : PHP の基礎 1. WebアプリケーションとHTMLの概要 2. PHP 演習 (Hands on) 3. これからグループで作っていくGoogleガジェットに関する説明 参考文献 : 山田和夫 ( 著 ) 基礎からの PHP ( ソフトバンククリエイティブ, 2007) 2 WWW とは 1.Web アプリケーションの仕組みと HTML の概要 World Wide Web ( 通常 WWW, Web などと略される ) はインターネットやイントラネットで標準的に用いられるドキュメントシステム.HTML という言語で文書の論理構造や見栄えを記述し 文書の中に画像や音声など文字以外のデータや 他の文書の位置 ( ハイパーリンク ) を埋め込むことができる サーバ A サーバ B サーバ C プログラム データベースエンジン 4 1

10 <HEAD> <TITLE> </TITLE> </HEAD> <H1> </H1> <P> </P> <UL> <LI> <LI> <LI> </UL> </HTML > HTML とは HTML(Hyper Text Markup Language) は文書の性格を表す タグ と呼ばれる記号を付けて記述する方法を定めた標準である タグ を使って, 文書のタイトルやレイアウト, 文字の色など表せる 5 <HEAD> <TITLE> </TITLE> </HEAD> <H1> </H1> </HTML > ハイパーリンクの仕組み <A HREF= " ここをクリック </A> <A> タグのなかで リンク先の Web ページの URL を書くと ブラウザ上で リンクが表示されれる URL は Web 上のドキュメントの住所に相当するもの 6 URL( Uniform Resource Locator ) scheme://host.domain[:port]/path[#anchor][?keyword] どのプロトコルで情報をやりとりするか例 : http ftp telnet サーバの 住所 であるドメイン名 例 : ドキュメントの 住所 例 : /files/paper.htm は Files フォルダーの下の paper.htm というファイル HTML (Hyper Text Markup Language) <TITLE>HTML example page</title> <H4>Example Page</H4> Click <A HREF=" to go to Iijima Lab Web site.<br><br> Laboratory Member<BR> <IMAGE SRC="picture.jpg" width="200"> IP アドレスを電話番号に喩えるなら ドメイン名は電話帳に登録されている名前に相当する 7 8 2

11 HTTP (Hyper Text Transfer Protocol) で Web ページを取得 Step 1 [ クライアントからサーバへの要求 ] GET /test.html HTTP/1.0 <CR> [ サーバからクライアントへの返答 ] HTTP/ OK^M Date: Tue Jan 18 16:19: GMT^M Server: NCSA/1.0a^M MIME-version: 1.0^M Content-type: text/html^m ^M <HEAD>^M <TITLE>HTML example page</title>^m </HEAD>^M ^M <H4>Example Page</H4>^M Click ^M <A HREF=" to go to Iijima Lab Web site.<br><br>^m Laboratory Member<BR>^M <IMAGE SRC= picture.jpg">^m ^M ^M 9 Web アプリケーションの仕組み クライアント 例 : : POST POST /register.php /register.php name name = = 花子花子 name_kana= name_kana= はなこはなこリクエスト レスポンス HyperText Transfer Protocol Daemon WWW で クライアントとサーバ間で通信するための約束事 ネットワークリクエストを受け 必要な処理を行う 裏 で動くプログラム HTTPD サーバ プログラムエンジン プログラム データベースエンジン 10 2.PHP 演習 準備 1. PC を起動し ログインする 2. ブラウザを起動し にアクセスし この URL をブラウザの お気に入り に追加する 3. 次に 下記レンタルサーバのホームページにアクセスし この URL をブラウザの お気に入り に追加する 4. ホワイトボードに書かれているユーザ ID/ パスワードを使って レンタルサーバにログインする 5. ログイン後 画面左下にあるリンク [ ファイルマネージャー ] をクリックし ファイルマネージャ画面で 自分のチームナンバー ( 二人一組の演習用 ) のフォルダーをクリック 注意 : サーバにログイン後 ファイルマネージャー以外の機能は 一切使わないようにしてください ファイルマネージャー以外の機能を使って 操作を誤った場合 クラス 12 全員が演習を続けられなくなる可能性がありますので 十分注意してください 3

12 ファイルマネージャの使い方 重要 : 各自 自分のチームナンバーのフォルダーの下に作ったファイルを置く それ以外のところでファイルを置いたり 変更したりしてはいけない 誤って 他の人のフォルダーを操作しないよう よく確認してから作業してください ファイル作成後 ファイル一覧からそれを探し出し [ 内容の編集 ] をクリックすると 中身を作成 変更できる ファイル名を入力し [ ファイル作成 ] をクリックすると ファイルが作成され 画面上部のファイル一覧に表示される 最初の PHP プログラム プログラムの説明 自分のフォルダのしたで helloworld.php というファイルを作り 以下の内容を入力し 保存してください <HEAD><TITLE>Hello</TITLE></HEAD> <?php echo Hello, world!;?> 紙版配布資料参照 <?php echo Hello, world! ; モード開始記号 PHPの命令?> モード終了記号 他の形のモード開始 終了記号も幾つかある ( いずれもPHPプログラムの開始と終了を意味する ) <? ~?> <?= ~?> <% ~ %> <%= ~ %> <script language= php>~</script>

13 ブラウザで結果確認 ブラウザの [ 表示 ]-[ ソース ] 機能 ブラウザを起動し 作った helloworld.php にアクセスして 結果を確認する 自分のフォルダーの番号をここに入れる 無事 Hello, world! が表示されたら ブラウザのメニューから [ 表示 ]-[ ソース ] をクリックし ブラウザがサーバから受信ファイルの中身を確認しよう 17 質問 : 皆さんが作ったPHPファイルとブラウザが受信したファイルは どこが違うか? なぜこのような違いが出るか? 18 重要 : エラーメッセージが出たら その内容をよく読む エラーが出たら 慌てずに エラーメッセージの内容を読んで 原因を考える 右の例は syntax error( 文法のエラー ) があり 6 行目前後で, または ; が抜けている というメッセージですので 指摘されたことをプログラムで確認して 修正すれば 解決です 2 つ目のプログラム 今度は自分のフォルダーのなかで showdatetime.php を作り ブラウザから確認してみよう <HEAD><TITLE>2つ目のサンプル </TITLE></HEAD> <?php echo "<H1>". date('y-m-d') 紙版配布資料参照. " ". strftime("%h:%m:%s", time()). "</H1>";?>

14 プログラムの説明 echo "<H1>". date('y-m-d'). " ". strftime("%h:%m:%s", time()). "</H1>"; はHTMLの <H1> タグ ( このタグで括られた文字列は 表題の大きい文字として表示される ) 3の はHTMLで半角スペースを意味する記号 2 4はPHPの関数を呼び出し その関数が出力した結果 21 5 フォーム送信プログラム フォームでデータを送信し そのデータを表示するプログラムを作って ブラウザで試してみよう データを入力するためのフォーム画面 ( 単純な HTML) とそれを受信して表示するための画面 (PHP で作る ) を作る必要がある 22 form1.html <HEAD><TITLE> フォームサンプル </TITLE></HEAD>./form1.php は同じフォル ダの下のform1.phpという <FORM action="./form1.php" method="post"> <H1> 挨拶の確認 </H1> 1 ファイルを意味します この一行の意味は 同じフォルダの下のform1.phpに POSTという方法で 入力さ <P> 以下の人に挨拶します 紙版配布資料参照 </P> <INPUT type="text" name="myname" value="" /> 2 れたデータを送信する <INPUT type="submit" name="buttonname" value=" 送信する " /> </FORM> このテキストフィールドの name 属性が myname となっているので ここに入力されたデータは myname として サーバに 23 送信される form1.php <HEAD><TITLE> フォームサンプル </TITLE></HEAD> <H1> こんにちわ <?= $_POST["myName"] 紙版配布資料参照?> さん 1 </H1> フォームから送信されたデータを参照するときは $_POST[ ~ ] を使う (~の部分は name 属性で指定した名前 ) 24 6

15 配列について PHP の配列は変数の集合体のようなもので 下記書式で利用する $< 配列名 >[< キー >] PHP では 数字も 文字列も配列のキーとして使うことができる 例 : $month[1] = 31; $month[2] = 28; $iijima[ name ] = Iijim Junichi ; $iijima[ office ] = W9522 ; $iijima[ mailbox ] = W9-66 ; $iijima[ ] = iijima.j.aa@m.titech.ac.jp ; 各月の日数を出力するプログラム form2.html, form2.phpを 25 作成し ブラウザで結果を確かめてみよう form2.html ( 配列とフォームを使うプログラム ) <HEAD><TITLE> フォームサンプル 2</TITLE></HEAD> <FORM action="./form2.php" method="post"> <H1> 配列を使うプログラムです </H1> <P> この月は何日あるか?</P> <INPUT type="text" name="month" value="" /> <INPUT type="submit" name="buttonname" value=" 送信する " /> </FORM> 紙版配布資料参照 26 form2.php ( 配列とフォームを使うプログラム ) <HEAD><TITLE> 配列の基本のサンプル </TITLE></HEAD> <?php $month[1] = 31; $month[2] = 28; $month[3] = 31; $month[4] = 30; $month[5] = 31; $month[6] = 30; $month[7] = 31; $month[8] = 31; $month[9] = 30; $month[10] = 31; $month[11] = 30; $month[12] = 31; $thismonth = $_POST["month"]; echo $thismonth. " 月は ". $month[$thismonth]. " 日まであります ";?> 紙版配布資料参照 27 分岐処理について : if~else 文 If 文の書式 if (< 条件 >) { 条件が成立するときに実行する処理ブロック } else { 条件が成立しないときに実行する処理ブロック } さて if 文を使って 先ほど作った form2.php に入力ミスのチェック機能を追加しましょう 28 7

16 form3.html ( 配列とフォームを使うプログラム ) form3.php (if 文 配列とフォームを使うプログラム ) <HEAD><TITLE> フォームサンプル 2</TITLE></HEAD> <FORM action="./form3.php" method="post"> <H1> 配列を使うプログラムです </H1> <P> この月は何日あるか?</P> <INPUT type="text" name="month" value="" /> <INPUT type="submit" name="buttonname" value=" 送信する " /> </FORM> 紙版配布資料参照 29 <HEAD><TITLE> 配列の基本のサンプル </TITLE></HEAD> <?php $month[1] = 31; $month[2] = 28; $month[3] = 31; $month[4] = 30; $month[5] = 31; $month[6] = 30; $month[7] = 31; $month[8] = 31; $month[9] = 30; $month[10] = 31; $month[11] = 30; $month[12] = 31; $thismonth = $_POST["month"]; 紙版配布資料参照 if ( $thismonth >= 1 and $thismonth <= 12 ) { echo $thismonth. " 月は ". $month[$thismonth]. " 日まであります "; } else { echo "1 から 12 の整数を入力してください "; }?> 30 Google ガジェットと一般の Web ページの違い 3.iGoogle ガジェットについて 基本的に 一般のWebページで出来ることが Googleガジェットのなかでも出来る ただし 以下のことに気をつける必要がある : 小さい枠 ( インラインフレーム ) の中で表示する必要がある JavaScript 機能のほどんとが利用できるが 一部利用できないものもある 通常 ユーザがフォームから サーバ側のプログラムにリクエストを送信した場合 そのレスポンスを返すとき 別の Windowを開いて表示することになる ( 例 : Wikipedia 検索ガジェット ) 工夫をすれば 別 Windowにしないことも可能 32 8

17 プログラムエンジンGoogle ガジェットを使うには このガジェットの URL は wikipediasearchbox.xml wikipediasearchbox.xml という XML 形式のドキュメントの中で ガジェットの基本情報 ( ガジェット名 作者 作者のメールアドレスなど ) が記述されている また wikipediasearchbox.html というド Web ページを読み込んで表示するように指示している 簡単なガジェットの例を見てみよう 1. igoogle( にアクセスし googleアカウントをつくり ログインする 2. [ コンテンツを追加 ] ページで 使いたいガジェットを選ぶか [ フィードやガジェットを追加 ] をクリックして ガジェットのURLを入力して追加する 33 <?xml version="1.0" encoding="utf-8"?> - <Module> <ModulePrefs title="wikipedia 検索 " title_url=" directory_title="wikipedia 検索 " description=" フリー百科事典 ウィキペディア (Wikipedia) 検索ボックス " screenshot=" thumbnail=" author="g-fan" author_ ="g.introducer+ghome@gmail.com" author_location="japan" height="40" scrolling="0" render_inline="optional" /> <Content type="url" href=" /> </Module> 34 Google ガジェットの仕組み Google ガジェットを作るための技術 Google のサーバ ガジェットを作るのに HTML と簡単な XML を書く必要がある その他に使う技術は 必要な機能によって変わる 必要な機能 使う技術 クライアント H T T P D Google のシステム H T T P D プログラム データベースエンジン 沢山の情報を 自分のサーバー上で蓄積 管理する ユーザに 情報を登録してもらい それを蓄積 管理する 動きのあるユーザインタフェースを実現する ( 例 : マースで通過すると絵が変わる ) ユーザが入力した情報を元に 他のWebサイドから情報を収集し 集めた情報の形を整えて ユーザに返すユーザの設定にもとづいて 他のWebサイトからリアルタイムに情報を集め 形を整えて表示する データベース PHP データベース PHP JavaScript, 場合によってはスタイルシート JavaScript, 場合によっては PHP JavaScript, 場合によっては PHP 35 文字の色 行間など きめ細かい書式を設定して きれいなユーザインターフェースを作る スタイルシート 36 9