東京工科大学 コンピュータサイエンス学部 亀田弘之 言語プロセッサ2016 第１１日目 東京工科大学 コンピュータサイエンス学部 亀田弘之

(E）BNFを構文図に書き直してみよう！ 「PL/0 の処理系を作ろう！」の続き Bisonの復習を中心に (E）BNFを構文図に書き直してみよう！ ツールの紹介もします。 （でも自力で描き直せるようにしましょう。） 言語プロセッサ2016（東京工科大学CS学部）

「PL/0 の処理系を作ろう！」の続き （復習でもあるので、大分わかるようになったのではないでしょうか？） 言語プロセッサ2016（東京工科大学CS学部）

Bisonの構造 %{ // C言語の諸定義 %} // トークンなどの定義 %% // 構文規則群 // C言語の関数など 言語プロセッサ2016（東京工科大学CS学部）

Bisonはトークンの情報が必要になると int yylex() を呼び出す。 トークンは、数値として内部的には取り扱われる。 トークンの値は、変数yylvalを介して受け渡される。 変数yylvalはデフォールトではint型のため、異なるデータ型を取り扱うためには、union型を使う。 言語プロセッサ2016（東京工科大学CS学部）

定義部 %{と%}の間に、include文、define文、prototype文、変数宣言を記述する。 Bison宣言部 トークンの定義　%token number PLUS トークンの値は、bison –d dummy.y と実行することで自動生成され、dummy.tab.h という名前のインクルードファイルに書き込まれる。 演算の優先順位の定義 言語プロセッサ2016（東京工科大学CS学部）

構文規則部 BNF風に規則を記述する。 選択記号は｜を使う。 規則記述に続けて動作を記述する。 規則右辺の各記号の値は、左から順に$1, $2, $3, … で参照できる。 規則の戻り値は変数$$に代入される。 各規則の末尾は；。 言語プロセッサ2016（東京工科大学CS学部）

例 %{ #include <stdio.h> int yylex(void); void yyerror(char *); %} %token INTEGER %% program: program expr '\n’ { printf( "%d\n”, $2 ); } | ; expr: INTEGER | expr '+’ expr { $$ = $1 + $3; } | expr '-’ expr { $$ = $1 - $3; } void yyerror( char *s ) { fprintf( stderr, "%s\n”, s ); } int main( void ) { yyparse( ); return 0; 言語プロセッサ2016（東京工科大学CS学部）

cal1.tab.h ( bison –d cal1.y で生成) #ifndef YYTOKENTYPE #define YYTOKENTYPE /* Put the tokens into the symbol table, so that GDB and other debuggers know about them. */ enum yytokentype { INTEGER = 258 }; #endif /* Tokens. */ #define INTEGER 258 #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; #define yystype YYSTYPE /* obsolescent; will be withdrawn */ #define YYSTYPE_IS_DECLARED 1 #define YYSTYPE_IS_TRIVIAL 1 extern YYSTYPE yylval; 言語プロセッサ2016（東京工科大学CS学部）

lexer.l %{ #include "y.tab.h" #include <stdlib.h> void yyerror(char *); %} %% [0-9]+ { yylval = atoi(yytext); return INTEGER; } [-+\n] { return( *yytext); } [ \t] { /* skip whitespace */ } . { yyerror( "Unknown character” ); } int yywrap( void ) { return 1; } 言語プロセッサ2016（東京工科大学CS学部）

次の例 言語プロセッサ2016（東京工科大学CS学部）

%{ #include <stdio. h> /. Printf. / #include <stdlib. h> / %{ #include <stdio.h> /* Printf */ #include <stdlib.h> /* exit */ #define YYSTYPE int int yyparse( void ); int yylex( void ); void yyerror( char *mes ); %} %token number %token QUIT 254 %% . . . → next page int main() { printf("Enter expression with + - * / ( ) \n"); yyparse(); return 0; } void yyerror( char *mes ) { fprintf( stderr, “%s\n”, mes); } 言語プロセッサ2016（東京工科大学CS学部）

program : program expr ‘\n’ { printf( “= %d\n”, $2 ); } | ; expr : expr '+' term { puts( "expr 1” ); $$ = $1 + $3; } | expr '-' term { puts( "expr 2” ); $$ = $1 - $3; } | term { puts( "expr 3” ); $$ = $1; } | QUIT { exit( 0 ); } term : term '*’ fact { puts( "term 1” ); $$ = $1 * $3; } | term '/’ fact { puts( "term 2” ); $$ = $1 / $3; } | fact { puts( "term 3” ); $$ = $1; } fact : number { puts( "fact 1” ); $$ = $1; } | '-’ number { puts( "fact 1” ); $$ = -$2; } | '(’ expr ')' { puts( "fact 2” );$$ = $2;} 言語プロセッサ2016（東京工科大学CS学部）

cal2.tab.h ( bison –d cal2.y ) /* Tokens. */ #ifndef YYTOKENTYPE #define YYTOKENTYPE /* Put the tokens into the symbol table, so that GDB and other debuggers know about them. */ enum yytokentype { number = 258, QUIT = 254 }; #endif #define number 258 #define QUIT 254 #if ! defined YYSTYPE && ! defined YYSTYPE_IS_DECLARED typedef int YYSTYPE; #define yystype YYSTYPE /* obsolescent; will be withdrawn */ #define YYSTYPE_IS_DECLARED 1 #define YYSTYPE_IS_TRIVIAL 1 extern YYSTYPE yylval; 言語プロセッサ2016（東京工科大学CS学部）

(E）BNFを構文図に書き直してみよう！ （黒板を使います。） 言語プロセッサ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学部）