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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

プログラミング言語の構文規則(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学部）

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

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

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

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

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

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

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

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

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

実行手順 $ 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: (*, 16818434, 16818436) T2: (+, 16818432, T1) 言語プロセッサ2016（東京工科大学CS学部）

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