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

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

分析 合成 ソース言語 読み込み 字句解析 構文解析 中間語生成 コード生成 目的言語 #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 $0x00000000, %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学部）

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

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

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

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

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

実際の手順 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学部）

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

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

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

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

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

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

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学部）

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

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学部）

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

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

数式の文法（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学部）

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学部）

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

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

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