東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

1 東京工科大学 コンピュータサイエンス学部 亀田弘之
ネットワークの準備お願いします！ 言語プロセッサ2015　No.8 東京工科大学 コンピュータサイエンス学部 亀田弘之 言語プロセッサ2015（東京工科大学CS学部）

2 今日から演習 言語プロセッサ2015（東京工科大学CS学部）

3 分析 合成 ソース言語 読み込み 字句解析 構文解析 中間語生成 コード生成 目的言語 #include <stdio.h>
main(){ float kingaku = 0, teika = 100; float shouhizei = 0.10; kingaku = teika + teika*shouhizei; printf("kingaku=%f\n", kingaku); } 読み込み 字句解析 分析 構文解析 .file "test2.c" .def ___main; .scl 2; .type 32; .endef .section .rdata,"dr"LC3: .ascii "kingaku=%f\12\0" .text.globl _main .def _main; .scl 2; .type 32; .endef_main: pushl %ebp movl %esp, %ebp andl $-16, %esp subl $32, %esp call ___main movl $0x , %eax movl %eax, 28(%esp) movl $0x42c80000, %eax movl %eax, 24(%esp) movl $0x3dcccccd, %eax movl %eax, 20(%esp) flds 24(%esp) fmuls 20(%esp) fadds 24(%esp) fstps 28(%esp) flds 28(%esp) fstpl 4(%esp) movl $LC3, (%esp) call _printf leave ret .def _printf; .scl 2; .type 32; .endef 中間語生成 合成 コード生成 目的言語 言語プロセッサ2015（東京工科大学CS学部）

4 Flexの復習（確認） (いくつか実例をやります。) 言語プロセッサ2015（東京工科大学CS学部）

5 Flexの復習 確認1 (いくつか実例をやります。) 言語プロセッサ2015（東京工科大学CS学部）

6 数式をトークンに分解する！ 練習１ 練習２ 練習３ 入力： teika + teika * zei
確認2 練習１ 入力： teika + teika * zei 出力： var(teika) op(+) var(teika) op(*) var(zei) 練習２ 入力： a123 * xyz * h 出力： var(a123) op(*) var(xyz) op(+) num(120) … 練習３ 入力： x1 + x2 * ( y1 + y2) 出力： var(x1) op(+) var(x2) op(*) lpa(() var(y1) … 言語プロセッサ2015（東京工科大学CS学部）

7 手順 Flexのプログラムを書く。 Flexのプログラムをflexにかける。
確認3 Flexのプログラムを書く。 Flexのプログラムをflexにかける。 出力ファイルlex.yy.cをgccでコンパイルする。この際，ライブラリーを忘れずに！ 出力a.exeを実行する。 さまざまな文字列を入力する。 言語プロセッサ2015（東京工科大学CS学部）

8 手順 確認4 ライブラリ（ｆｌ） Flex Lex.yy.c gcc Flex Program a.exe 文字列入力 出力
言語プロセッサ2015（東京工科大学CS学部）

9 実際の手順 C:\> flex sample01.l C:\> gcc lex.yy.c –lfl C:\> a.exe
確認5 実際の手順 C:\> flex sample01.l C:\> gcc lex.yy.c –lfl C:\> a.exe それでは、実際にやってみよう。 言語プロセッサ2015（東京工科大学CS学部）

10 数式をトークンに分解する！（再） 練習１ 練習２ 練習３ 入力： teika + teika * zei
確認6 練習１ 入力： teika + teika * zei 出力： var(teika) op(+) var(teika) op(*) var(zei) 練習２ 入力： a123 * xyz * h 出力： var(a123) op(*) var(xyz) op(+) num(120) … 練習３ 入力： x1 + x2 * ( y1 + y2) 出力： var(x1) op(+) var(x2) op(*) lpa(() var(y1) … 言語プロセッサ2015（東京工科大学CS学部）

11 構文解析の実装 〜BisonとFlaxの応用〜
最終目標： PL/0 言語の構文解析器を自作する。 （注） PL/0言語とは、Niklaus Wirth がコンパイラ教育のために考案した 　　　プログラミング言語。 言語プロセッサ2015（東京工科大学CS学部）

12 準備をしましょう！ 言語プロセッサ2015（東京工科大学CS学部）

13 BNFとEBNF（文法の記述法） How to describe a grammar of a programming language, especially syntactic rules. （注）前回までは、文脈自由文法の記法を 使っていた。もちろん、それでもいい のだが、… （参考）教科書29ページ参照の事。 言語プロセッサ2015（東京工科大学CS学部）

14 BNFの例 文脈自由文法 BNF(Backus Naur Form)
文 → 主語 述語 主語 → 名詞 助詞 述語 → 副詞 動詞 名詞 → 子犬 | アヒル | 子供 助詞 → が | も | は 副詞 → ゆっくりと | よたよたと |素早く 動詞 → 歩いている | 移動する <文> ::= <主語> <述語> <主語> ::= <名詞> <助詞> <述語> ::= <副詞> <動詞> <名詞> ::= 犬 | アヒル | 自動車 <助詞> ::= が | も | は <副詞> ::= ゆっくりと | のんびりと |素早く <動詞> ::= 歩いている | 移動する 言語プロセッサ2015（東京工科大学CS学部）

15 BNFの例(続き) 文 ＝＞ 主語 述語 ＝＞ 名詞 助詞 副詞 動詞 ＝＞ 子犬 が ゆっくりと 移動する <文> ＝＞ <主語> <述語> ＝＞ <名詞> <助詞> <副詞> <動詞> ＝＞ 子犬 が ゆっくりと 移動する 言語プロセッサ2015（東京工科大学CS学部）

16 BNFの例（２） <数字> ::= 0|1|2|3|4|5|6|7|8|9 <英字> ::= 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|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 <名前> ::= <英字>|<名前> <英字>|<名前> <数字> 言語プロセッサ2015（東京工科大学CS学部）

17 BNFの例（２）（続き） 名前の例 hensuu, KoukaDai, university, smart, OK など <名前>＝＞ <名前><英字> ＝＞ <英字> K ＝＞ OK 言語プロセッサ2015（東京工科大学CS学部）

18 Bisonでの記述 Bisonのコード 元のBNF <名前> ： <英字> |<名前> <英字> |<名前> <数字> ； <数字> ::= 0|1|2|3|4|5|6|7|8|9 <英字> ::= 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|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 <名前> ::= <英字> |<名前> <英字> |<名前> <数字> 言語プロセッサ2015（東京工科大学CS学部）

19 実際のコード Bisonのコード Flexのコード id : character | id character | id number ;
[a-zA-Z]+ return(CHARACTER); [0-9]+ return(NUMBER) 言語プロセッサ2015（東京工科大学CS学部）

20 EBNF 実際にプログラミング言語やXMLなどの形式言語を記述する場合、BNFでは書きにくい場合もあるため、BNFを拡張したものが使われる。それがEBNF(extended BNF)である。 言語プロセッサ2015（東京工科大学CS学部）

21 数式の文法（BNF） <expression> ::= <term> | <expression> "+" <term> <term> ::= <factor> | <term> "*" <factor> <factor> ::= <constant> | <variable> | "(" <expression> ")" <variable> ::= "x" | "y" | "z" <constant> ::= <digit> | <digit> <constant> <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 言語プロセッサ2015（東京工科大学CS学部）

22 ENFの例（３）　数式 expression = term | expression, "+" , term; term = factor | term, "*" , factor; factor = constant | variable | "(" , expression , ")"; variable = "x" | "y" | "z"; constant = digit , {digit}; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 言語プロセッサ2015（東京工科大学CS学部）

23 Syntax Diagram(構文図) こちらで書いた方がわかりやすい！ 積極的に利用しましょう。 （図は別途紹介します）
こちらで書いた方がわかりやすい！ 積極的に利用しましょう。 （図は別途紹介します） 言語プロセッサ2015（東京工科大学CS学部）

24 （今後の予定） 数式を中間言語へ変換するプログラムの作成
（配布資料を配ります。） 言語プロセッサ2015（東京工科大学CS学部）

25 出題および提出日は、後日お知らせします。
（予告）レポート課題 数式を中間言語へ変換するプログラムに対して、５種類の計算式を 入力し実行せよ。 レポートには、入力した式とその出力を記せ。下記に書き方の例を示 しておく。 入力 出力 ① a + b*c T1: ( *, b, c ) T2: ( +, a, T1 ) ② abc + xy T1: ( +, abc, xyz) 出題および提出日は、後日お知らせします。 言語プロセッサ2015（東京工科大学CS学部）