情報工学実験
C
コンパイラ
（
2018年度）
担当：笹倉・佐藤
2018.12.6 その3
yaccの構造
定義部
%%
定義部の終了
規則部
%%
規則部の終了
ユーザ定義サブルーチン部
：
Cのプログラムを書く
形は
lexと同じ
yacc
•
yacc のキモは規則部
• 規則部には文法規則を書く
左辺
: 右辺
•
yaccは入力されたプログラムを右辺から左辺
に「還元」していく
• この規則にアクションが書かれていたら還元
するときにアクションも実行する．
• アクションというのは基本的にはCプログラム．
yacc 注意点
•
yacc は
字句解析をされた後のトークン
を入力
とするので必ず字句解析ルーチンが必要．単
独では使えない
• 字句解析ルーチンを使うにはyaccの中から
yylex()関数を呼び出す（実際にはyyparse()関
数を呼ぶとその中で自動的に
yylex()を呼んで
くれる）
• 字句解析ルーチンは自作することも可能だが
普通は
lexを使う
yacc 定義部
• 初期設定を行う
• 使用するトークン名を
%token
の後に続けて書
– そうするとそれに対応したCのマクロ宣言が作成され *.tab.h が自動的に作成される – それをlexプログラムでもyaccプログラムでもincludeす ることでトークンの受け渡しが可能になる．
•
%{
と
%}
で囲まれた部分はそのまま *.tab.c にコ
ピーされる．必要なヘッダファイルの
includeなど
を行ったりする
yacc 規則部
• 文法規則を書く • 左辺 : 右辺; • 文法としては左辺が右辺に変換される（基本的に書き換え るだけ）．ただしそれに加えて右辺にアクションが書ける． • 左辺は非終端記号 • 左辺と右辺の区切りは : • 各ルールの区切りは; • lexと同様に | が使える • 右辺のアクションはその規則を使って還元が行われるとき に実行される．Cのプログラムも書ける • 最初の規則の左辺がスタートシンボルとみなされる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; } }例：「
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
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のエラーを出す．
曖昧な文法の例
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)
lex から yacc に値を渡す方法
•
lex プログラムから yacc プログラムに値を渡すには
– lex プログラムのアクション部で return 値； とする．この 場合，型はデフォルトではint – lex プログラムで渡したい値をyylval変数に入れておく．こ の場合の型はデフォルトではint – yylvalの型は変更することができる（後述）．•
yacc プログラムで値を受け取るには
– 規則部のシンボルの値として受け取れる． $$ : 左辺のシンボルの値 $1 : 右辺一番左のシンボルの値 $2 : 右辺二番目のシンボルの値 …yylval の型
•
yylval のデフォルトの型は int
int の値が欲しければ何もしなくてよい
•
yylval はライブラリの中で宣言されているので，
これを使う
lexプログラムの宣言部にC言語と
して
extern int yylval;
を書いておけばよい．
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;加減算を行う計算機
(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 を拡張して乗除算と括弧も扱えるように
しよう
• 乗除算は加減算より優先される（先に実行さ
れる）ことに注意
• 括弧があると括弧の中を先に計算することに
注意
• 最初に文法を考える
演習：文法
• 数字と四則演算とかっこからなる算術式の文
法を書いてみよ
<算術式> ::= <算術式> <演算子> <因子> | <因子> <演算子> ::= + | - | * | / <因子> ::= <数> | (<算術式>)よくない例
(BNF
表記
)
：
算術式において乗除算は加減算より優先されることがこの 文法では実現できていない演習：文法
• 数字と四則演算とかっこからなる算術式の文
法を書いてみよ
<算術式> ::= <算術式> + <項> | <算術式> - <項> | <項> <項> ::= <項> * <因子> | <項> / <因子> | <因子> <因子> ::= <数> | (<算術式>)正しい例
(BNF
表記
)
：
演習：四則演算
(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; }演習：実数
(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に格納する
(注：これは問題を簡単にするためにこのようにするだけなので実 際にコンパイラを作成する時はこの方法ではなく個別にメモリを確 保して変数名を記憶するようにすること）• 一行だけで計算が終わるのではなく数式を連続
で計算できるようにし，
$が入力されたら終了す
るようにする
%union
• どの変数が使われるのかを知るためにはlex
プログラムから変数名を受け取らなければな
らない
• 数字が入力された時は実数を，変数が入力
された時には整数（配列の添え字に使う
)を受
け取るように複数種類の型の値を
yylvalに入
れて
lexプログラムからyaccプログラムへ値を
渡したい
• そのための%union
%union宣言の使い方例
•
yaccプログラムの宣言部にシンボルの型を定義する
%union {
double dval;
int vblno;
}
Cの共用体として実現される
•
yaccプログラムの各シンボルにどの型を取るかを教え
てあげなければならない
– トークンの場合 %token <dval> NUMBER %token <vblno> NAME – 非終端記号のシンボルの場合 %type <dval> expression
演習：変数も使える計算機
(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|この言語で書けるプログラムの例
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; }
