言語プロセッサ2015 第10回目 〜資料番号 H28NoA〜

Presentation on theme: "言語プロセッサ2015 第10回目 〜資料番号 H28NoA〜"— Presentation transcript:

1 言語プロセッサ2015 第10回目 〜資料番号 H28NoA〜
ネットワークの準備お願いします！ 言語プロセッサ2015　第10回目 〜資料番号 H28NoA〜 東京工科大学 コンピュータサイエンス学部 亀田弘之 言語プロセッサ2016（東京工科大学CS学部）

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

3 今日も皆でわいわいがやがや、 楽しく演習をやっていきましょう。
まずはグループ（相談相手）を作ってください。 何も見てもいいです。 仲間と相談しながらやってください。 ただし、やったことを人に説明できるようにしてください。 各自メモを残してください。 言語プロセッサ2016（東京工科大学CS学部）

4 参加する（Participation） 議論する（Discussion） 奉仕する（Altruism） 行動指針
言語プロセッサ2016（東京工科大学CS学部）

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

6 準備をしましょう！ まずは、BNFとEBNFの説明 次に、構文図の説明 言語プロセッサ2016（東京工科大学CS学部）

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

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

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

10 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 <名前> ::= <英字>|<名前> <英字>|<名前> <数字> 言語プロセッサ2016（東京工科大学CS学部）

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

12 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 <名前> ::= <英字> |<名前> <英字> |<名前> <数字> 言語プロセッサ2016（東京工科大学CS学部）

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

14 参考　BNF のシンタックス定義 <syntax> ::= <rule> | <rule> <syntax> <rule> ::= <opt-whitespace> “<” <rule-name> “>” <opt-whitespace> "::=" <opt-whitespace> <expression> <line-end> <opt-whitespace> ::= " " <opt-whitespace> | "” <expression> ::= <list> | <list> "|" <expression> <line-end> ::= <opt-whitespace> <eol> | <line-end> <line-end> <list> ::= <term> | <term> <opt-whitespace> <list> <term> ::= <literal> | "<" <rule-name> ">" <literal> ::= '"' <text> '"' | "'" <text> "'" 言語プロセッサ2016（東京工科大学CS学部）

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

16 数式の文法（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" 言語プロセッサ2016（東京工科大学CS学部）

17 EBNFの例（３）　数式 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” ; 言語プロセッサ2016（東京工科大学CS学部）

18 参考　EBNF のシンタックス定義 letter = "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" ; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; symbol = "[" | "]" | "{" | "}" | "(" | ")" | "<" | ">" | "'" | '"' | "=" | "|" | "." | "," | ";" ; character = letter | digit | symbol | "_" ; identifier = letter , { letter | digit | "_" } ; terminal = "'" , character , { character } , "'" | '"' , character , { character } , '"' ; lhs = identifier ; rhs = identifier | terminal | "[" , rhs , "]" | "{" , rhs , "}" | "(" , rhs , ")" | rhs , "|" , rhs | rhs , "," , rhs ; rule = lhs , "=" , rhs , ";" ; grammar = { rule } ; 言語プロセッサ2016（東京工科大学CS学部）

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

20 （今後の予定） 数式を中間言語へ変換するプログラムの作成
今日の資料として第１版を配布します。 言語プロセッサ2016（東京工科大学CS学部）

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

22 プログラミング言語の構文規則(EBNF形式)例
Program ::= module Id ; Block Id . Block ::= DeclList begin StmtList end DeclList ::= { Decl ; } Decl ::= ConstDecl | ProcDecl | VarDecl ConstDecl ::= const ConstDeclItem { , ConstDeclItem } ConstDeclItem ::= Id : Type = ConstExpr ConstExpr ::= Id | Integer VarDecl ::= var VarDeclItem { , VarDeclItem } VarDeclItem ::= Id : Type ProcDecl ::= procedure Id ([ FormalDecl {, FormalDecl} ] ) ; Block Id FormalDecl::= Id : Type Type ::= int StmtList ::= { Stmt ; } Stmt ::= CallStmt | AssignStmt | OutStmt | IfStmt | WhileStmt CallStmt ::= Id ( [ Exprs ] ) AssignStmt::= Lvalue := Expr Lvalue ::= Id OutStmt ::= output := Expr IfStmt ::= if Test then StmtList end WhileStmt ::= while Test do StmtList end Test ::= odd Sum | Sum Relop Sum Relop ::= <= | <> | < | >= | > | = Exprs ::= Expr {, Expr } Expr ::= Sum Sum ::= Term { (+ | -) Term } Term ::= Factor { (* | /) Factor } Factor ::= - Factor | LValue | Integer | input | ( Expr ) 言語プロセッサ2016（東京工科大学CS学部）

23 PL/0言語の構文規則 program = block "." . block = [ "CONST" ident "=" number { "," ident "=" number } ";" ] [ "VAR" ident { "," ident } ";" ] { "PROCEDURE" ident ";" block ";" } statement . statement = [ ident ":=" expression | "CALL" ident | "?" ident | "!" expression | "BEGIN" statement { ";" statement } "END" | "IF" condition "THEN" statement | "WHILE" condition "DO" statement ] . condition = "ODD" expression | expression ( "=" | "#" | "<" | "<=" | ">" | ">=" ) expression . expression = [ "+" | "-" ] term { ( "+" | "-" ) term } . term = factor { ( "*" | "/" ) factor } . factor = ident | number | "(" expression ")" . 言語プロセッサ2016（東京工科大学CS学部）

24 P ::= A. P ::= A B. A A B P ::= [A]. P ::= {A}. A A 構文図で描くともっとわかりやすい
言語プロセッサ2016（東京工科大学CS学部）

25 構文図の例（１） ident number expression factor ) (
factor = ident | number | "(" expression ")" . factor ident number expression ( ) 言語プロセッサ2016（東京工科大学CS学部）

26 構文図の例（２） + + expression term term
ー term ー 言語プロセッサ2016（東京工科大学CS学部）

27 PL/0言語の構文規則 練習 構文図で書いてみよう！
練習　構文図で書いてみよう！ PL/0言語の構文規則 program = block "." . block = [ "CONST" ident "=" number { "," ident "=" number } ";" ] [ "VAR" ident { "," ident } ";" ] { "PROCEDURE" ident ";" block ";" } statement . statement = [ ident ":=" expression | "CALL" ident | "?" ident | "!" expression | "BEGIN" statement { ";" statement } "END" | "IF" condition "THEN" statement | "WHILE" condition "DO" statement ] . condition = "ODD" expression | expression ( "=" | "#" | "<" | "<=" | ">" | ">=" ) expression . expression = [ "+" | "-" ] term { ( "+" | "-" ) term } . term = factor { ( "*" | "/" ) factor } . factor = ident | number | "(" expression ")" . 言語プロセッサ2016（東京工科大学CS学部）

28 必死に演習するステージ 課題：次のようなプログラムを作れ。 入力： 数式 例： a+b*c 出力： 三つ組形式の中間表現 例： T1: (*, b, c) T2: (+, a, T1) 言語プロセッサ2016（東京工科大学CS学部）

29 Bisonプログラムの例 #include <stdio.h> #include <stdlib.h> int make_tuple(char*, int, int); int yyerror(char*); int yylex(); char var[100]; %} %token PLUS TIMES LP RP ID %% E: E PLUS T { $$=make_tuple("+", $1, $3); } | T { $$=$1; } T: T TIMES F { $$=make_tuple("*", $1, $3); } | F { $$=$1; } F: LP E RP { $$=$2; } | ID { $$=$1; } 言語プロセッサ2016（東京工科大学CS学部）

30 Bisonプログラムの例（続き） %% int prev_tuple = 0; //var[0]='\0'; int make_tuple(char *op, int arg1, int arg2){ printf("T%d: (%s, ", ++prev_tuple, op); if(arg1 > 0){ //itoa(arg1, var,2); printf("%s", var); printf("%d, ", arg1); } else { printf("T%d, ", -arg1); if(arg2 > 0){ printf("%d",arg2); //iota(arg2,var,2); printf("%s", var); printf("T%d", -arg2); printf(")\n"); return -prev_tuple; int main(){ yyparse(); } int yyerror(char *msg){ printf("error=(%s)\n", msg); return 0; 言語プロセッサ2016（東京工科大学CS学部）

31 Flexプログラムの例 %{ #include "parser.tab.h" extern int yylval; int copy_lexeme(); %} %% [\t ]+ { } "+" { return PLUS; } "*" { return TIMES; } "(" { return LP; } ")" { return RP; } [a-z][a-z0-9]* { yylval = copy_lexeme(); return ID; } \n { return 0; } . { printf("lexical error: '%c'\n", yytext[0]); return 0; } %% char StringTable[1000]; char *ST = StringTable; int copy_lexeme(){ int p = (int)ST; strcpy(ST, yytext); ST += strlen(yytext)+1; return p; } 言語プロセッサ2016（東京工科大学CS学部）

32 実行手順 $ ls parser.y scanner.l $ bison -d parser.y parser.tab.c parser.tab.h parser.y scanner.l $ flex scanner.l lex.yy.c parser.tab.c parser.tab.h parser.y scanner.l $ gcc *.c -ll a.out lex.yy.c parser.tab.c parser.tab.h parser.y scanner.l $ ./a.out a+b*c T1: (*, , ) T2: (+, , T1) 言語プロセッサ2016（東京工科大学CS学部）

33 次週も演習をします 練習課題１ 今日のプログラムを実際に実行して みてください。 練習課題２ PL/0の構文規則を構文図で書いて みてください。 以上 言語プロセッサ2016（東京工科大学CS学部）