コンパイラとは プログラミング言語 ( 高級言語 ) で書かれたプログラムを入力し, コンピュータが実行できる言語 ( 機械語など ) に変換するプログラムのこと例 : gcc コンパイラは対応する言語によって複雑である場合もあるし単純である場合もある 本実験では簡単な言語のコンパイラを作成する

Transcription

1 情報工学実験 C コンパイラ (2016 年度 ) 担当 : 笹倉 佐藤 version

2 コンパイラとは プログラミング言語 ( 高級言語 ) で書かれたプログラムを入力し, コンピュータが実行できる言語 ( 機械語など ) に変換するプログラムのこと例 : gcc コンパイラは対応する言語によって複雑である場合もあるし単純である場合もある 本実験では簡単な言語のコンパイラを作成する

3 本実験の目的 3 年間の総仕上げとしてある程度大きなプログラムを作成する グループでシステム ( プログラム ) を仕上げる経験をする 自分でスケジュールを立てシステムを構築する経験をする

4 スケジュール 12/6( 火 ) 概要説明 yacc, lex 演習 12/13( 火 ) yacc, lex を用いた構文解析 1 12/15( 木 ) yacc, lex を用いた構文解析 2 12/20( 火 ) yacc, lex を用いた構文解析 3 1/10( 火 ) コード生成説明 1/18( 水 ) コード生成 1 1/24( 火 ) コード生成 2 1/26( 木 ) コード生成 3 1/31( 火 ) コード生成 4 2/2( 木 ) コード生成 5 2/7( 火 ) 最終面接

5 実験概要 手続き型言語のコンパイラの作成 目的コードはハードウェア実験で作成したプロセッサのアセンブラ 基本言語仕様を与えるので, それを適宜拡張する yacc, lex を使う 時間があればコード最適化を行う

6 実施上の注意 Web ページ hap:// /~sasakura/jikken/ グループで行う グループで共通の言語仕様を決めてプログラムを作成する できるだけ分担してプログラムを書く わからないことはまずグループで相談する 遅刻 欠席する場合は必ずグループの他のメンバーにも連絡のこと 作業報告書を毎回出す 最終面接で評価する ( 最終課題のプログラムが動くかどうか, 内容をきちんと理解しているか, レポートがきちんと書けているか )

7 グループ自己紹介 (5 分間 ) 下記のことをすべて述べること 名前 今朝の朝ごはんは何を食べたか 好きな食べもの 好きな色 特技 好きな科目 苦手な科目 プログラミングの経験 プログラミングがどれくらい好きか

8 手続き型言語とは プログラムに書いてある順番通りにコンピュータが実行すればよいようになっている言語例 :C 言語 その他の言語とは 関数型言語例 :ML, Haskell オブジェクト指向言語例 :Java

9 手続き型言語の利点 手続き を考えてプログラムを書けばよいので比較的わかりやすい コンパイラを作りやすい 基本的には入力プログラムの 1 行 1 行を順番に実行コード ( アセンブラ ) に変換していけばよい ただしそうすると効率の悪いプログラムになる場合があるので, コード最適化を行う場合が多い.

10 コンパイラの概要 字句解析入力プログラムを字句 ( トークン ) に分ける 構文解析入力プログラムが文法に合っているかどうかをチェックする. 抽象構文木 (AST) を作る. AST レベルでの最適化 コード生成実行コード ( アセンブラ ) に変換する コードレベルでの最適化

11 字句解析 入力プログラムを字句 ( トークン ) に分ける 自作するならオートマトンを用いる表駆動型 ( 参考 :2015 年度コンパイラ実験 ) 今回は ( 今年度から ) lex を使う lex については後述

12 字句解析オートマトン 初期状態 整数 以外 0 9 実数 0 9 以外 終了状態 英字 英数字 識別子 英数字以外 整数 実数 識別子の場合の例

13 構文解析 入力プログラムが文法に合っているかどうかをチェックする 合っていなければコンパイラがエラーを出す 自作するなら, 再帰下降型構文解析や演算子順位法を使う 今回は yacc を利用. yacc については後述

14 構文木 < 簡単な算術式 > ::= < 簡単な算術式 > < 演算子 > < 数 > < 数 > < 演算子 > ::= + - < 数 > ::= < 数字 >< 数 > < 数字 > < 数字 > ::= < 簡単な算術式 > < 簡単な算術式 > < 演算子 > < 数 > < 簡単な算術式 > < 数 > < 演算子 > < 数 > ー 3

15 抽象構文木 (AST) 構文解析の結果, プログラムを木の形で記憶する 構文木から非終端記号を取り除き, コード生成に必要なものだけを残して作った木 この木をたどりながらコード生成をする AST を意味を変えないように違う形にすることでより速いコードにすることができる ( コード最適化 )

16 コード生成 AST をたどりながら実行コード ( アセンブラ ) に変換していく AST の形によってどういうコードを生成するかが決まる 一度生成したコードを見直して意味を変えないように変換することでより速いコードにすることもできる ( コード最適化 )

17 yacc, lex UNIX で標準で装備されている字句解析 構文解析ルーチン lex (lexical analyzer) 字句解析ルーチン単独で使うこともできる yacc (Yet Another Compiler Compiler) 構文解析ルーチン字句解析の結果を使うので基本的に lex と一緒に使う

18 yacc と lex 概念的 : 入力プログラム 実装 : 入力プログラム 字句解析 構文解析 構文解析 yacc 字句解析 lex AST AST

19 yacc と lex の出力 yacc も lex も C プログラムを自動生成する その C プログラムをコンパイルすることで実行可能なファイルができる lex lex.yy.c yacc *.tab.h *.tab.c

20 lex の構造 定義部 %% 定義部の終了規則部 %% 規則部の終了ユーザ定義サブルーチン部 :Cのプログラムを書く

21 lex 定義部 初期設定を行う %{ と %} で囲まれた部分はそのまま lex.yy.c にコピーされる.

22 lex 規則部 パタン空白アクションの繰り返し パタンは正規表現で書く アクションは C 言語で書く 例 : %% \n ++num_lines; ++num_chars;. ++num_chars; %%

23 正規表現で使える文字 配布したプリントを参照

24 ユーザ定義サブルーチン部 ここで書いたものはすべて C 言語だと解釈され lex.yy.c にそのままコピーされる yylex() を呼び出さないと字句解析が実行されないので lex 単独でプログラムを書く場合はこの中で必ず yylex() を呼び出さなければならない

25 例 : 文字数を数えるプログラム (count.l) %{ int num_lines = 0, num_chars = 0; %} %% \n ++num_lines; ++num_chars;. ++num_chars; %% Int main(void) { yylex(); prinb("# of lines = %d, # of chars = %d\n", num_lines, num_chars); } return 0;

26 lex のコンパイルの仕方 > flex ファイル名 > gcc lex.yy.c o 実行ファイル名 - lfl UNIX の標準は lex だが,GNU の lex 相当である flex を本実験では使う. lex(flex) の関数 ( 例えば yylex) を使うためには,lex のライブラリである libfl.a をリンクする必要がある.- lfl はそれを指定している. count.l をコンパイルして実行してみよう > flex count.l > gcc lex.yy.c o count - lfl

27 ライブラリがないと言われたら 1. ~/.bashrc に以下を追記 export LD_LIBRARY_PATH=/home/users/ecs/ sato/local/lib:$ld_library_path export LIBRARY_PATH=/home/users/ecs/ sato/local/lib:$library_path 2. bashrc を再読み込みして環境変数を再設定 source./bashrc

28 例 2: 単語数を数えるプログラム (word.l) %{ int charcount = 0; int wordcount = 0; int linecount = 0; %} %% [^ \t\n]+ {wordcount++; charcount += yyleng; } \n {charcount++; linecount++;}. {charcount++;} %% int main(void ) { yylex(); prinb("# of lines = %d, # of words = %d, # of chars = %d\n", linecount, wordcount, charcount); } return 0;

29 lex の主要な変数 関数 yyleng ( 最後に ) マッチしたトークンの長さ yytext ( 最後に ) マッチしたトークン文字列 yylex() 字句解析の開始. アクションの中で return を使うか, もしくは入力がなくなるまで字句解析をする. return を用いたとき, 再度 yylex() を呼ぶと前回の続きから字句解析を再開する

30 例 3: 単語の認識 (verb.l) %{ /* Simple verb recogniton. */ %} %% [\t ]+ /* ignore whitespace */ is am are were was {prinb("%s: is a verb\n", yytext); } [a- za- Z]+ {prinb("%s: is not a verb\n", yytext); }. \n {ECHO; } %% int main(void){ } yylex(); return 0;

31 lex 知っておいた方がよいこと lex のパタンは一度だけしかマッチしない 合致するパタンが複数あるときはマッチする長さがもっとも長いパタンのアクションを実行する例 : This is an island. を入力してみる. : 特別なアクション. 次のパタンと同じアクションを使用することを示す. ECHO : トークンの内容をそのまま出力する. どのパタンにもマッチしない入力に対するデフォルトアクションとして使われる.

32 応用問題 (word- ext.l) word.l を次のように拡張しよう 1. アルファベットのみをcharCountで数える. 2. 数字のみを数える変数を付け加える. 3. 単語と認識したものをその都度表示する.

33 yacc の構造 定義部 %% 定義部の終了規則部 %% 規則部の終了ユーザ定義サブルーチン部 :Cのプログラムを書く 形は lex と同じ

34 yacc 注意点 yacc は字句解析をされた後のトークンを入力とするので必ず字句解析ルーチンが必要. 単独では使えない 字句解析ルーチンを使うには yacc の中から yylex() 関数を呼び出す ( 実際には yyparse() 関数を呼ぶとその中で自動的に yylex() を呼んでくれる ) 字句解析ルーチンは自作することも可能だが普通は lex を使う

35 yacc 定義部 初期設定を行う 使用するトークン名を %token の後に続けて書く そうするとそれに対応した C のマクロ宣言が作成され *.tab.h が自動的に作成される それを lex プログラムでも yacc プログラムでも include することでトークンの受け渡しが可能になる. %{ と %} で囲まれた部分はそのまま *.tab.c にコピーされる. 必要なヘッダファイルの include などを行ったりする

36 yacc 規則部 文法規則を書く 左辺 : 右辺 ; 文法としては左辺が右辺に変換される ( 基本的に書き換えるだけ ). ただしそれに加えて右辺にアクションが書ける. 左辺は非終端記号 左辺と右辺の区切りは : 各ルールの区切りは ; lex と同様に が使える 右辺のアクションはその時点で実行される.C のプログラムも書ける 最初の規則の左辺がスタートシンボルとみなされる

37 yacc ユーザ定義サブルーチン部 ここで書いたものはすべて C 言語だと解釈され *.tab.c にそのままコピーされる yyparse() を呼び出さないと字句解析が実行されないので yacc が main となるプログラムを書く場合はこの中で必ず yyparse() を呼び出さなければならない yyparse() の中で yylex() が呼ばれている.

38 例 : 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 { prinb("ok!\n");} ; %% int main(void){ } if (yyparse()) { } fprinb(stderr, "Error! Error! Error!\n"); return 1;

39 例 : 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]; %%

40 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

41 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 を見ないと決定できない

42 yacc が対応できない規則 2 曖昧な文法 複数の構文木を作れるような文法を曖昧な文法という 曖昧な文法に対して yacc は reduce/reduce conflict や shi /reduce conflict のエラーを出す.

43 曖昧な文法の例 1 start : x y; x : A; y : A; この時,A という入力に対して, これが x から導出される A なのか y から導出される A なのかはっきりしない. どちらも有りうる. これが還元 / 還元衝突 (reduce/reduce conflict)

44 曖昧な文法の例 2 start : x y R; x : A R; y : A; AR という入力に対して,x から A R が導出されるし,y を A を考えて start の規則に戻って R とも考えられる. どちらも有りうる. これがシフト / 還元衝突 (shi /reduce conflict)

45 lex から yacc に値を渡す方法 lex プログラムから yacc プログラムに値を渡すには lex プログラムのアクション部で return 値 ; とする. この場合, 型はデフォルトでは int lex プログラムで渡したい値を yylval 変数に入れておく. この場合の型はデフォルトでは int yylval の型は変更することができる ( 後述 ). yacc プログラムで値を受け取るには 規則部のシンボルの値として受け取れる. $$ : 左辺のシンボルの値 $1 : 右辺一番左のシンボルの値 $2 : 右辺二番目のシンボルの値

46 yylval の型 yylval のデフォルトの型は int int の値が欲しければ何もしなくてよい yylval はライブラリの中で宣言されているので, これを使う lex プログラムの宣言部に C 言語として extern int yylval; を書いておけばよい.

47 加減算を行う計算機 (p- m.y) %{ #include <stdio.h> #include "p- m.tab.h" extern int yylex(); extern int yyerror(); %} %token NUMBER %% statement : expression {prinb("= %d\n", $1);}; expression : expression '+' NUMBER {$$ = $1 + $3; } expression '- ' NUMBER {$$ = $1 - $3; } NUMBER {$$ = $1;}; %% int main(void) { } if (yyparse()) { } fprinb(stderr, "Error\n"); return 1;

48 加減算を行う計算機 (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]; %%

49 演習 : 四則演算 (arith.y) p- m.y を拡張して乗除算と括弧も扱えるようにしよう 乗除算は加減算より優先される ( 先に実行される ) ことに注意 括弧があると括弧の中を先に計算することに注意 最初に文法を考える

50 演習 : 文法 数字と四則演算とかっこからなる算術式の文法を書いてみよ よくない例 (BNF 表記 ): < 算術式 > ::= < 算術式 > < 演算子 > < 因子 > < 因子 > < 演算子 > ::= + - * / < 因子 > ::= < 数 > (< 算術式 >) 算術式において乗除算は加減算より優先されることがこの文法では実現できていない

51 演習 : 文法 数字と四則演算とかっこからなる算術式の文法を書いてみよ 正しい例 (BNF 表記 ): < 算術式 > ::= < 算術式 > + < 項 > < 算術式 > - < 項 > < 項 > < 項 > ::= < 項 > * < 因子 > < 項 > / < 因子 > < 因子 > < 因子 > ::= < 数 > (< 算術式 >)

52 演習 : 四則演算 (arith.y) 文法の正しい例になるように p- m.y を変更し四則演算と括弧が使えるようにしよう (lex プログラムは p- m.y と同じでよい ) 応用 : 除算の時に 0 で割っている場合にはエラーメッセージをだして計算を行わないようにする ヒント : エラーが起こったことを知らせるには関数 yyerror() を使うのがよい 関数 yyerror() はデフォルトでは引数で与えた文字列を stderr に表示する ( 独自に実装することも可能 )

53 演習 : 実数 (arithr.l, arithr.y) これまで整数の四則演算を行っていた arith.y を実数の四則演算を行うように変更しよう lex プログラムを実数をトークンとするように変更する lex プログラムから yacc プログラムへ渡す値も実数になる ヒント :lex プログラム yacc プログラムのどちらにも宣言部で arithr.tab.h を include する前に #define YYSTYPE double を入れる ( 注 :YYSTYPE は yylval の型 ) arithr.tab.h を見て理解すること

54 変数を使えるようにする arithr.y を拡張して変数を使えるようにする 変数はアルファベット小文字一文字だけからなるものとする 変数の数はたかだか 26 なので,26 個の要素をもつ配列 vbltable に格納する 一行だけで計算が終わるのではなく数式を連続で計算できるようにし,$ が入力されたら終了するようにする

55 %union どの変数が使われるのかを知るためには lex プログラムから変数名を受け取らなければならない 数字が入力された時は実数を, 変数が入力された時には整数 ( 配列の添え字に使う ) を受け取るように複数種類の型の値を yylval に入れて lex プログラムから yacc プログラムへ値を渡したい そのための %union

56 %union 宣言の使い方例 yacc プログラムの宣言部にシンボルの型を定義する %union { double dval; int vblno; } C の共用体として実現される yacc プログラムの各シンボルにどの型を取るかを教えてあげなければならない トークンの場合 %token <dval> NUMBER %token <vblno> NAME 非終端記号のシンボルの場合 %type <dval> expression

57 演習 : 変数も使える計算機 (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 を複数行読めるようにし,$ が来たら終わるようにする 各トークン, 必要な非終端記号に型を指定すること

58 基本言語仕様 < プログラム > ::= < 変数宣言部 > < 文集合 > < 変数宣言部 > ::= < 宣言文 > < 変数宣言部 > < 宣言文 > < 宣言文 > ::= 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 < 数字 > ::=

59 この言語で書けるプログラムの例 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; }

60 本日の作業内容 作業目標 このスライドにあるすべての演習問題を実行する それができたら基本言語仕様を構文解析する yacc,lex プログラムを作成する まずは正しいプログラムは何のエラーもなく通るようにする. コード生成はまだしなくてよい. アクション部は何も書かなくてよい. エラーがあれば error と出力するようにする グループで相談しながら作業すること. 可能ならば分担して作業すること. 時間が来たら作業報告書を書いて印刷し, それを提出のこと. 作業報告書にはそれぞれのメンバーが今日何をしたかを書くこと