情報工学実験 C コンパイラ (2018 年度 ) 担当 : 笹倉 佐藤 2018.12.6 その 3 yacc の構造 定義部 定義部の終了 規則部 規則部の終了 ユーザ定義サブルーチン部 :C のプログラムを書く 形は lex と同じ 1
yacc yacc のキモは規則部 規則部には文法規則を書く左辺 : 右辺 yacc は入力されたプログラムを右辺から左辺に 還元 していく この規則にアクションが書かれていたら還元するときにアクションも実行する. アクションというのは基本的には C プログラム. yacc 注意点 yacc は字句解析をされた後のトークンを入力とするので必ず字句解析ルーチンが必要. 単独では使えない 字句解析ルーチンを使うには yacc の中から yylex() 関数を呼び出す ( 実際には yyparse() 関数を呼ぶとその中で自動的に yylex() を呼んでくれる ) 字句解析ルーチンは自作することも可能だが普通は lex を使う 2
yacc 定義部 初期設定を行う 使用するトークン名を %token の後に続けて書 そうするとそれに対応した C のマクロ宣言が作成され *.tab.h が自動的に作成される それを lex プログラムでも yacc プログラムでも include することでトークンの受け渡しが可能になる. %{ と %} で囲まれた部分はそのまま *.tab.c にコピーされる. 必要なヘッダファイルの include などを行ったりする yacc 規則部 文法規則を書く 左辺 : 右辺 ; 文法としては左辺が右辺に変換される ( 基本的に書き換えるだけ ). ただしそれに加えて右辺にアクションが書ける. 左辺は非終端記号 左辺と右辺の区切りは : 各ルールの区切りは ; lex と同様に が使える 右辺のアクションはその規則を使って還元が行われるときに実行される.C のプログラムも書ける 最初の規則の左辺がスタートシンボルとみなされる 3
yacc ユーザ定義サブルーチン部 ここで書いたものはすべて C 言語だと解釈され *.tab.c にそのままコピーされる yyparse() を呼び出さないと字句解析が実行されないので yacc が main となるプログラムを書く場合はこの中で必ず yyparse() を呼び出さなければならない yyparse() の中で yylex() が呼ばれている. 例 : I am だけを受理する (sample.y) %{ #include <stdio.h> #include "sample.tab.h" extern int yylex(); extern int yyerror(); %} %token SUBJECT PRED SPACE statement : SUBJECT SPACE PRED { printf("ok!\n");} ; int main(void){ if (yyparse()) { fprintf(stderr, "Error! Error! Error!\n"); return 1; } } 4
例 : I am だけを受理する (sample.l) %{ #include "sample.tab.h" /* lex for sample.y */ %} I {return SUBJECT;} am {return PRED;} [\t ]+ {return SPACE;} \n return 0;. return yytext[0]; yacc のコンパイルの仕方 > flex ファイル名 > bison -d ファイル名 > gcc *.tab.c lex.yy.c o 実行ファイル名 lfl -ly UNIX の標準は yacc だが,GNU の yacc 相当である bison を本実験では使う.-d はヘッダファイルを出すためのオプション. ヘッダファイルに変更がなければつけなくてよい. sample.y をコンパイルして実行してみよう > flex sample.l > bison d sample.y > gcc sample.tab.c lex.yy.c o sample lfl -ly 5
yacc が対応できない規則 1 二つ以上のトークンを先読みしないといけないような文法 例 : phrase : cart_animal AND CART work_animal AND PLOW ; cart_animal : HORSE GOAT; work_animal : HORSE OX; ( 注 : 大文字はトークン ) この例では例えば HORSE AND CART の HORSE が cart_animal から導出された HORSE なのか work_animal から導出された HORSE なのかは HORSE の 2 トークン先の CART を見ないと決定できない yacc が対応できない規則 2 曖昧な文法 複数の構文木を作れるような文法を曖昧な文法という 曖昧な文法に対して yacc は reduce/reduce conflict や shift/reduce conflict のエラーを出す. 6
曖昧な文法の例 1 start : x y; x : A; y : A; この時,A という入力に対して, これが x から導出される A なのか y から導出される A なのかはっきりしない. どちらも有りうる. これが還元 / 還元衝突 (reduce/reduce conflict) 曖昧な文法の例 2 start : x y R; x : A R; y : A; AR という入力に対して,x から A R が導出されるし,y を A を考えて start の規則に戻って R とも考えられる. どちらも有りうる. これがシフト / 還元衝突 (shift/reduce conflict) 7
lex から yacc に値を渡す方法 lex プログラムから yacc プログラムに値を渡すには lex プログラムのアクション部で return 値 ; とする. この場合, 型はデフォルトでは int lex プログラムで渡したい値を yylval 変数に入れておく. この場合の型はデフォルトでは int yylval の型は変更することができる ( 後述 ). yacc プログラムで値を受け取るには 規則部のシンボルの値として受け取れる. $$ : 左辺のシンボルの値 $1 : 右辺一番左のシンボルの値 $2 : 右辺二番目のシンボルの値 yylval の型 yylval のデフォルトの型は int int の値が欲しければ何もしなくてよい yylval はライブラリの中で宣言されているので, これを使う lex プログラムの宣言部に C 言語として extern int yylval; を書いておけばよい. 8
yacc のアクションでできること $$ に値を代入することで, 規則部の左辺の値を任意に決められる ( 特に明示しなければ $$ = $1 となる ) 還元のタイミングで任意の C プログラムを実行できる 例えば printf で値を表示させたり 例えば抽象構文木を作ったり 加減算を行う計算機 (p-m.y) %{ #include <stdio.h> #include "p-m.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER statement : expression {printf("= %d\n", $1);}; expression : expression '+' NUMBER {$$ = $1 + $3; } expression '-' NUMBER {$$ = $1 - $3; } NUMBER {$$ = $1;}; int main(void) { if (yyparse()) { } fprintf(stderr, "Error\n"); return 1; return 0; } 9
加減算を行う計算機 (p-m.l) %{ #include "p-m.tab.h" extern int yylval; %} [0-9]+ {yylval = atoi(yytext); return NUMBER; } [\t ] ; /* ignore whitespace */ \n return 0;. return yytext[0]; 演習 : 四則演算 (arith.y) p-m.y を拡張して乗除算と括弧も扱えるようにしよう 乗除算は加減算より優先される ( 先に実行される ) ことに注意 括弧があると括弧の中を先に計算することに注意 最初に文法を考える 10
演習 : 文法 数字と四則演算とかっこからなる算術式の文法を書いてみよ よくない例 (BNF 表記 ): < 算術式 > ::= < 算術式 > < 演算子 > < 因子 > < 因子 > < 演算子 > ::= + - * / < 因子 > ::= < 数 > (< 算術式 >) 算術式において乗除算は加減算より優先されることがこの文法では実現できていない 演習 : 文法 数字と四則演算とかっこからなる算術式の文法を書いてみよ 正しい例 (BNF 表記 ): < 算術式 > ::= < 算術式 > + < 項 > < 算術式 > - < 項 > < 項 > < 項 > ::= < 項 > * < 因子 > < 項 > / < 因子 > < 因子 > < 因子 > ::= < 数 > (< 算術式 >) 11
演習 : 四則演算 (arith.y) 文法の正しい例になるように p-m.y を変更し四則演算と括弧が使えるようにしよう (lex プログラムの内容は p-m.l と同じでよい. p-m.l を arith.l にコピーし,p-m.tab.h を arith.tab.h に変更して使う ) 応用 : 除算の時に 0 で割っている場合にはエラーメッセージをだして計算を行わないようにする ヒント : エラーが起こったことを知らせるには関数 yyerror() を使うのがよい 関数 yyerror() はデフォルトでは引数で与えた文字列を stderr に表示する ( 独自に実装することも可能 ) arith.y( 穴埋め ) %{ #include <stdio.h> #include "arith.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER statement : expression { printf("= %d\n", $1);} ; expression : expression '+' mulexp {$$ = $1 + $3;} expression '-' mulexp {$$ = $1 - $3;} mulexp {$$ = $1;} ; mulexp : mulexp '*' primary {$$ = $1 * $3;} mulexp '/' primary {if ($3 == 0) { yyerror("divide by zero"); return 0;} else $$ = $1 / $3;} primary {$$ = $1;} ; primary : '(' expression ')' {$$ = $2;} NUMBER {$$ = $1;} ; int main(void) { if(yyparse()) { fprintf(stderr, "Error\n"); return 1; } return 0; } 12
演習 : 実数 (arithr.l, arithr.y) これまで整数の四則演算を行っていた arith.y を実数の四則演算を行うように変更しよう lex プログラムを実数をトークンとするように変更する ヒント : 実数を受理するように正規表現を変える lex プログラムから yacc プログラムへ渡す値も実数になる ヒント :lex プログラム yacc プログラムのどちらにも宣言部で arithr.tab.h を include する前に #define YYSTYPE double を入れる ( 注 :YYSTYPE は yylval の型 ) arithr.tab.h を見て理解すること 変数を使えるようにする arithr.y を拡張して変数を使えるようにする 変数はアルファベット小文字一文字だけからなるものとする 変数の数はたかだか 26 なので,26 個の要素をもつ配列 vbltable に格納する ( 注 : これは問題を簡単にするためにこのようにするだけなので実際にコンパイラを作成する時はこの方法ではなく個別にメモリを確保して変数名を記憶するようにすること ) 一行だけで計算が終わるのではなく数式を連続で計算できるようにし,$ が入力されたら終了するようにする 13
%union どの変数が使われるのかを知るためには lex プログラムから変数名を受け取らなければならない 数字が入力された時は実数を, 変数が入力された時には整数 ( 配列の添え字に使う ) を受け取るように複数種類の型の値を yylval に入れて lex プログラムから yacc プログラムへ値を渡したい そのための %union %union 宣言の使い方例 yacc プログラムの宣言部にシンボルの型を定義する %union { double dval; int vblno; } C の共用体として実現される yacc プログラムの各シンボルにどの型を取るかを教えてあげなければならない トークンの場合 %token <dval> NUMBER %token <vblno> NAME 非終端記号のシンボルの場合 %type <dval> expression 14
演習 : 変数も使える計算機 (arithrv.[ly]) arithr.[ly] を拡張する %union 行を arithrv.y に加える 変数の値を格納する配列 vbltable[26] を arithrv.y で宣言し, arithrv.l では extern 宣言する 変数のトークンを NAME として arithrv.l で読み込めるようにする arithrv.y に statement : NAME = expression expression を付け加える ( アクション部も各自考えて追加すること ) NAME を expression の中で使えるようにする statement を複数行読めるようにし,$ が来たら終わるようにする 各トークン, 必要な非終端記号に型を指定すること 基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= define < 識別子 >; < 文集合 > ::= < 文 > < 文集合 > < 文 > < 文 > ::= < 代入文 > < ループ文 > < 条件分岐文 > < 代入文 > ::= < 識別子 > = < 算術式 >; < 算術式 > ::= < 算術式 > < 加減演算子 > < 項 > < 項 > < 項 > ::= < 項 > < 乗除演算子 > < 因子 > < 因子 > < 因子 > ::= < 変数 > (< 算術式 >) < 加減演算子 > ::= + - < 乗除演算子 > ::= * / < 変数 > ::= < 識別子 > < 数 > < ループ文 > ::= while (< 条件式 >) { < 文集合 > } < 条件分岐文 > ::= if (< 条件式 >) { < 文集合 > } if (< 条件式 >) { < 文集合 > } else { < 文集合 > } < 条件式 > ::= < 算術式 > < 比較演算子 > < 算術式 > < 比較演算子 > ::= == '<' '>' < 識別子 > ::= < 英字 > < 英数字列 > < 英字 > < 英数字列 > ::= < 英数字 > < 英数字列 > < 英数字 > < 英数字 > ::= < 英字 > < 数字 > < 数 > ::= < 数字 > < 数 > < 数字 > < 英字 > ::= 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 < 数字 > ::= 0 1 2 3 4 5 6 7 8 9 15
この言語で書けるプログラムの例 define a; define a1; define b; a = 2800; b = (a + 5) *3; if (b> 3000) { b = 3000; } a1 = 0; while(a1 < 2){ b = b / 2; a1 = a1 + 1; } 本日の作業内容 作業目標 1. スライド 資料をみながら四則演算のできる計算機のプログラムを完成させる ( 資料の演習問題 2) 2. スライドをみながら四則演算のできる計算機が実数も扱えるようにする 3. スライド 資料をみながら変数も使える計算機のプログラムを完成させる ( 資料 8 節 ) 4. 基本言語仕様を構文解析する yacc,lex プログラムを作成する まずは正しいプログラムは何のエラーもなく通るようにする. コード生成はまだしなくてよい. アクション部は何も書かなくてよい. エラーがあれば error と出力するようにする 時間が来たら作業報告書を書いて印刷し, それを提出のこと. 作業報告書には作業目標の何番まで終了したかを書くこと. 16