コンパイラの技術と関数電卓プログラム(2)
前半では、1文字の数字と簡単な演算子で表現される計算式を再帰下降パーサで計算する処理で、 演習を行った。
後半は、さらに実際のコンパイラに近いものとして、 C言語で広く使われている、字句解析ツール(lexical analyzer : lex or flex)、 構文解析ツール(parser : yacc or bison) を使って、 さらに現実的な関数電卓プログラムを作ってみる。
lex or flex による字句解析
lexは、字句解析のプログラムを自動生成するツール。 “%%”行の内側に、正規表現によるルールとその処理(アクション)を書き並べる。 また、“%{ … %}”の内側に、その処理に必要なC言語のソースを書き、 lex で処理を行うと、lex.yy.c というC言語のソースを出力する。
lex.yy.c の中には、yylex() という関数が自動的に作られ、構文解析ツールから呼び出される。
# flex は、lex の改良版。
(( mycalc.l )) %{ #include <stdio.h> // yaccが出力するヘッダファイル #include "y.tab.h" int yywrap( void ) { // 1: スキャナ終了 // 0: yyin を切り替えて継続 return 1 ; } %} %% "+" return ADD ; "-" return SUB ; "*" return MUL ; "/" return DIV ; "\n" return CR ; [0-9][0-9]* { // 入力はyytextに格納されている。 int temp ; sscanf( yytext , "%d" , &temp ) ; yylval.int_value = temp ; // 返り値は、字句(トークン)の種別を表す定数 return INT_LITERAL; } %%
このプログラムを、lex で処理させると、“+” 記号に ADD という定数記号を割り振るとか、数字列” [0-9][0-9]* “をみつけると、文字列から数値を生成(sscanf)して、その場合の記号に INT_LITERAL という定数記号を割り振る…といった処理のプログラムを生成してくれる。(INT_LITERALは構文解析側で定義する定数)
yacc or bison
yacc ( Yet Another Compiler Compiler ) もしくはその改良版の bison は、構文解析のプログラムを自動生成してくれるツールである。構文をBNF記法で記載すると、字句解析ツール(lex等)を呼び出しながら構文に合わせたトークンの出現に応じた状態遷移のための「遷移テーブル」を自動生成し、 その遷移テーブルを用いた処理のプログラムをC言語で出力してくれる。
字句解析プログラムは、様々なトークンとデータを返す。このデータには様々な場合考えられるので、 そのトークンに合わせたデータの型を “%union” の中に記載(C言語の共用体参照)する。 “%%”〜”%%” の間には、BNF記法の(ルール)と、それに対応する処理(アクションは“{ }”の中の部分)を記載する。最初の“%{ … %}”の間には、処理に必要なC言語を記載する。
# bison(水牛)は、yacc(山牛)の改良版。
(( mycalc.y )) %{ #include <stdio.h> #include <stdlib.h> // yacc が定義する内部関数のプロトタイプ宣言 #define YYDEBUG 1 extern int yydebug ; extern int yyerror( char const* ) ; extern char *yytext ; extern FILE *yyin ; // 最初に呼び出される関数yyparse() extern int yyparse( void ) ; // 字句解析を呼び出す関数yylex() extern int yylex( void ) ; %} // 字句(トークン)の定義 %union { int int_value; } %token <int_value> INT_LITERAL %token ADD SUB MUL DIV CR %type <int_value> expression term primary_expression %% // 構文の定義 line_list : line // 行の繰り返し | line_list line ; line : expression CR { printf( ">>%d\n" , $1 ) ; } ; expression : term | expression ADD term { $$ = $1 + $3 ; } | expression SUB term { $$ = $1 - $3 ; } ; term : primary_expression | term MUL primary_expression { $$ = $1 * $3 ; } | term DIV primary_expression { $$ = $1 / $3 ; } ; primary_expression : INT_LITERAL ; %% // 補助関数の定義 int yyerror( char const* str ) { fprintf( stderr , "parser error near %s\n" , yytext ) ; return 0 ; } int main( void ) { yydebug = 0 ; // yydebug=1 でデバッグ情報表示 yyin = stdin ; if ( yyparse() ) { // 構文解析を開始 fprintf( stderr , "Error ! Error ! Error !\n" ) ; exit( 1 ) ; } }
このプログラムを、yacc で処理すると、“expression ADD term“のルール「加算式 + 乗算式」という文になっている部分を見つけると、そのルールに対応するアクション“{ $$ = $1 + $3 ; }”「$1(加算式部分の値)と、$3(乗算式の部分)の値を加えて、$$(式の結果)を求める」といった処理を生成してくれる。yyparse() 関数を呼び出すと、構文の一番最上部の line_list に相当する処理が起動される。yyerror()は、構文解析の途中で文法エラーになった時に呼び出される関数。
生成されるパーサの内容に興味があるなら、生成される y.tab.c の内容を読むと良い。
make と Makefile
これらのプログラムでは、字句解析プログラム mycalc.l から生成された lex.yy.c, y.tab.h と, 構文解析プログラム mycalc.y から生成された y.tab.c を組合せて1つの実行ファイルにコンパイルする。 これらの手順は煩雑なので、make ツールを使う。
make は、 Makefile に記載されている“ターゲット”と、それを作るために必要な“依存ファイル”、 “依存ファイル”から”ターゲット”を生成する処理“アクション”から構成される。 make は、ターゲットと依存ファイルの更新時間を比較し、 必要最小限の処理を行う。
基本的な Makefile の書き方は、
ターゲット: 依存ファイル... アクション # アクションの前はタブ
の様に書き、依存ファイルが更新されていたら、アクションを実行し、ターゲットを更新する。
以下に、今回の課題で使用する Makefile を示す。
(( Makefile )) # 最終ターゲット mycalc: y.tab.o lex.yy.o gcc -o mycalc y.tab.o lex.yy.o # 構文解析処理 y.tab.o: mycalc.y bison -dy mycalc.y # -dy : yacc互換モード gcc -c y.tab.c # 字句解析処理 lex.yy.o: mycalc.l mycalc.y flex -l mycalc.l # -l : lex互換モード gcc -c lex.yy.c clean:; rm mycalc y.tab.c y.tab.h lex.yy.c *.o (( ファイルの依存関係のイメージ図 )) mycalc.l mycalc.y | \ | lex.yy.c y.tab.h y.tab.c | \ | lex.yy.o y.tab.o \ / mycalc
この課題にあたり、後半の実験では flex, bison などの unix 系プログラミング環境を利用する。
macOS の利用者であれば MacPorts や、Windows 利用者であれば、wsl(Windows subsystem for Linux) などをインストールし実行すること。
今回の実験であれば、linux(Debian系)ならば、”sudo apt-get install flex bison gcc make” にて、必要なパッケージをインストールして実験を行うこと。
再帰下降パーサのサンプルコード
再帰下降パーサ・サンプル
授業でもやっていない再帰下読みの説明でもあり、 簡単なサンプルコードを示したいけど、Webで探しても全体的に大きなプログラムばかりで、 再帰関数をどう記述していくか解かりにくい。 ということで、+,-,*,/と数字1桁という条件で、字句解析無しのサンプルコードを書いてみた。
# 数字一桁と1文字演算子なので、字句解析は再帰下降パーサにそのまま組み込みとなっている。
// 再帰下読みの基本の一番短いサンプル // // 字句解析は面倒なので、 // 演算子は1文字のみ、定数は数字1桁だけとする。 #include <stdio.h> #include <ctype.h> // 括弧の無い +,-,*,/ だけの式の処理 // // 今回は以下の構文だけとする。 // 以下のような文法の書き方をバッカス記法(BNF)と言う。 // // exp_PLUS_MINUS ::= exp_MUL_DIV '+' exp_PLUS_MINUS // | exp_MUL_DIV '-' exp_PLUS_MINUS // | exp_MUL_DIV // ; // exp_MUL_DIV ::= DIGIT '*' exp_MUL_DIV // | DIGIT '/' exp_MUL_DIV // | DIGIT // ; // DIGIT ::= [0-9] ; // 構文解析に使う関数のプロトタイプ宣言 int exp_PLUS_MINUS( const char* , const char** ) ; int exp_MUL_DIV( const char* , const char** ) ; // PLUS,MINUSだけの式 // 構文解析関数の引数 // pc: 解析する文字列の先頭 // endp: 解析が終わった場所 int exp_PLUS_MINUS( const char* pc , const char** endp ) { // left=乗除算式 int left = exp_MUL_DIV( pc , endp ) ; if ( **endp == '+' ) { // right=加減算式 int right = exp_PLUS_MINUS( *endp + 1 , endp ) ; return left + right ; } else if ( **endp == '-' ) { // right=加減算式 int right = exp_PLUS_MINUS( *endp + 1 , endp ) ; return left - right ; } else { // 乗除算式を返す return left ; } } // MUL,DIVだけの式 // DIGITに相当する構文木の処理は、組み込んでしまう。 int exp_MUL_DIV( const char* pc , const char** endp ) { if ( isdigit( *pc ) ) { // left=数値 int left = *pc - '0' ; *endp = pc + 1 ; if ( **endp == '*' ) { // right=乗除算式 int right = exp_MUL_DIV( *endp + 1 , endp ) ; return left * right ; } else if ( **endp == '/' ) { // right=乗除算式 int right = exp_MUL_DIV( *endp + 1 , endp ) ; return left / right ; } // 数値を返す return left ; } else { printf( "Error\n" ) ; return 0 ; } } // 課題(1): () を含む処理にしたかったら、 // BNF の構文木は、どう直すべきか? // 課題(2): () を含む処理、空白を無視する処理、 // 定数式が複数桁を使える処理。 int main() { const char* e = NULL ; printf( "%d\n" , exp_PLUS_MINUS( "1+2*3" , &e ) ) ; printf( "%d\n" , exp_PLUS_MINUS( "1*2+3" , &e ) ) ; return 0 ; }
理解確認
- このプログラムでは演算子は、右結合だろうか?、左結合だろうか?
コンパイラの技術と関数電卓プログラム(1)
コンパイラを作るための技術の基礎を学んでもらうために、 簡単な関数電卓プログラム作成を課題とする。 基本は、printf( “%d” , eval( “1+2*3”) ) みたいな計算プログラムを作成する。
計算式から、計算処理を行う場合、演算子の優先順位を正しく処理できることが求められる。
一般的には、計算の機械語を生成する場合、データを準備して計算という方法であり、 逆ポーランド記法変換が行われる。
たとえば、”1+2*3″は、”1,2,+,3,*” といった表記に改められ、変換後の式は スタックを用いて、「値はpush,演算子はpop,pop,計算して,push」という 単純なルールで処理すれば、計算を行うことができる。
字句解析と構文解析
このような、計算式の処理を実行する場合、”1“,”+“,”2“,”✳︎“,”3“という 字句に切り分ける処理を、字句解析という。 この結果から、”式✳︎式”なら掛け算、”式+式”は足し算といった、 前後の字句の組合せから、構文木を生成する処理は、構文解析という。 コンパイラであれば、この後、最適化、コード生成などが行われる。
C言語であれば、コンパイル前後には以下の処理が行われる。
- プリプロセッサ処理
↓(#の無いCコード) - コンパイル処理
- 字句解析
- 構文解析
- コード生成
↓(中間コード)
- リンク処理 ← ライブラリ
↓ - 機械語
字句解析と正規表現
字句(トークン)の切り出しでは、その文法を説明する際には、正規表現なども用いられる。
簡単な正規表現 . 任意の文字 * 直前の0回以上の繰り返し + 直前の1回以上の繰り返し [0-9a-z] カッコの中の文字のいずれか - は範囲を示す。 (a|b|c) 丸カッコの|区切りのうちのどれか。 (例) C言語の変数の正規表現 [a-zA-Z_][a-zA-Z0-9_]*
構文解析の方法
構文解析では、構文を状態遷移として考え、この式の後にくる可能性のある状態は? という考えで解析を行う。 このような構文は、一般的にバッカス・ナウア記法(BNF)などで表現されることが多い。 また、簡単な構文解析であれば、
などが用いられる。
再帰下降パーサ
簡単な再帰下降パーサの演習として、1桁の数字と+,*演算子の処理プログラムを 考える。
加減,乗除の式のバッカス記法(BNF) exp_加減 ::= exp_乗除 '+' exp_乗除 | exp_乗除 '-' exp_乗除 | exp_乗除 ; exp_乗除 ::= DIGIT '*' exp_乗除 | DIGIT '/' exp_乗除 | DIGIT ; DIGIT ::= [0-9] ;
練習として、上に示す再帰下降パーサに、 (1) “(“,”)” を含めた場合の、BNF 記法を考え、(2) 数値として複数桁が使えるようにし、 (3) 式を読みやすくする空白を処理できるように 改造せよ。
専攻科実験・コンパイラと関数電卓プログラム作成
- コンパイラの技術と関数電卓プログラム(1)
- 課題
- 複数桁の数字が使えること。
- 式中に空白が使えること。
- 何らかの演算子を追加すること。
- (例) %,単項演算子のマイナスなど
- 演算子が左結合か右結合か確認すること。
- オプション課題
- 変数が使えること。
(変数名は1文字のA-Zといったもので良い)
- 変数が使えること。
- レポート内容
- コンパイラ技術の概要、課題(1)の説明・最終的なBNF記法・ソース・動作検証、考察
- 課題
- コンパイラの技術と関数電卓プログラム(2)
- 課題
- 基本的に、lex+yaccで(1)と同様の課題完成を目指す。
- レポート内容
- lex,yaccの概要、課題(2)の説明・ソース・動作検証、考察
- 課題
コンパイラと関数電卓プログラム(専攻科実験2018)
専攻科1年・生産システム実験1(後期)の「コンパイラと関数電卓プログラム」の説明は、昨年度資料と共通なのでリンクを記載しておく。
型による処理速度の実験
授業のネタとするために、型によって計算時間がどう変化するか実験。レガシーなコンピュータを使ってきた人間には、float とか double とか出てきたら、「Z80な時代の頭」では数倍遅いのを期待したけど、FPU を搭載して当たり前のこの時代、そんなに差は出ない。
FPUという言葉さえ、最近は死語かな…
しかたがないので、macOS , Raspberry-Pi , Arduino 遅さの時代を逆行しながら実験。
// test.cxx #ifndef TYPE #define TYPE int #endif #include <stdio.h> TYPE foo( TYPE i ) { TYPE ans = 0 ; for( int j = 0 ; j < 30000 ; j++ ) { ans += i * i ; } return ans ; } int main() { TYPE y = 0 ; for( TYPE i = 0 ; i < 100000 ; i++ ) { y = foo( i ) ; } return 0 ; }
iMac で実験
iMac で実験。デスクトップ 64 bit マシンだし、そんなに差は出ないのは予想どおり。
bash-3.2$ uname -a Darwin imac2 17.4.0 Darwin Kernel Version 17.4.0: ... root:xnu-4570.41.2~1/RELEASE_X86_64 x86_64 bash-3.2$ g++ -O0 -DTYPE=int test.cxx bash-3.2$ time ./a.out user 0m6.857s bash-3.2$ g++ -O0 -DTYPE="long long int" test.cxx bash-3.2$ time ./a.out user 0m6.831s bash-3.2$ g++ -O0 -DTYPE=float test.cxx bash-3.2$ time ./a.out user 0m8.528s bash-3.2$ g++ -O0 -DTYPE=double test.cxx bash-3.2$ time ./a.out user 0m8.615s
Raspberry-Pi3 で実験
組み込み系の FPU などが貧弱なマシンを想定し、Raspberry-Pi 3 で同じことをやってみた。
64bit整数 long long int が想定外に遅いな。
raspberry-pi:~$ uname -a Linux raspberry-pi 4.14.22-v7+ #1096 SMP ...2018 armv7l GNU/Linux raspberry-pi:~$ gcc -O0 -DTYPE=int test.cxx raspberry-pi:~$ time ./a.out user 0m37.588s raspberry-pi:~$ gcc -O0 -DTYPE="long long int" test.cxx raspberry-pi:~$ time ./a.out user 1m18.535s raspberry-pi:~$ gcc -O0 -DTYPE=float test.cxx raspberry-pi:~$ time ./a.out user 0m52.206s raspberry-pi:~$ gcc -O0 -DTYPE=double test.cxx raspberry-pi:~$ time ./a.out user 0m50.287s
Arduino で実験
同じことを Arduino でやってみた。main のループは 1/10000 の回数にして、10000倍の時間を掲載…
ようやく「Z80 な頭」が期待している実験結果となったかな。
int 6880[sec] 16bit int long 6320[sec] 32bit int float 92080[sec] 32bit float double 92080[sec] Arduino Uno では、double = 32bit で float と同じ
電卓プログラム作成の補足
専攻科実験で、「字句解析と構文解析で電卓プログラムを作ろう」というネタを実施中。
サンプルプログラムを見せて、課題の1つが「式を読みやすくするための空白が使えるように改良」としているが、学生さんより、『最初に空白を全部消してから処理するのはアリ?』との質問。
ひとまずは動くプログラムをつくってくれればいいけど….
でも、空白を先に全部消してから、トークン切り出しをやると、色々とトラブルが起こる。
((例1)) x=-1 ; 昔、私が学生の頃に使ったCコンパイラは、"+="演算子を、 "=+"と書いても良かった。だから、"x -= 1"と誤認され、 プログラムがバグった。この経験以降、代入文の"="の前後 とかややこしい演算子の式で、空白を適所に打たないヤツは シロウト判定している。 今回の質問のように、空白を除去してから字句解析を行うと、 "x = -1"と誤認されないように空白を入れあっても、 "x -= 1"に誤認される。 ((例2)) C++でのテンプレートクラスでは、<>の中に型を 書いたりするけど、Foot<int>といった型も 出てくる。んで、<>の中にテンプレートクラス が出てくると、Foo< Bar<int> > といった 型を使う場合がある。でも、空白除去後に字句解析をすると、 Foo<Bar<int>>となり、右シフト演算子になる。 → C++03 から C++11 での仕様の変化 ・C++03までは、テンプレートの">"の前後には空白を入れるべき。 ・C++11からは、"<"のトークンの数で">>"でも区別してくれる。
専攻科実験・コンパイラと関数電卓プログラム作成
- コンパイラの技術と関数電卓プログラム(1)
- 課題
- 複数桁の数字が使えること。
- 式中に空白が使えること。
- 何らかの演算子を追加すること。
- (例) %,単項演算子のマイナスなど
- 演算子が左結合か右結合か確認すること。
- オプション課題
- 変数が使えること。
(変数名は1文字のA-Zといったもので良い)
- 変数が使えること。
- レポート内容
- コンパイラ技術の概要、課題(1)の説明・ソース・動作検証、考察
- 課題
- コンパイラの技術と関数電卓プログラム(2)
- 課題
- 基本的に、lex+yaccで(1)と同様の課題完成を目指す。
- レポート内容
- lex,yaccの概要、課題(2)の説明・ソース・動作検証、考察
- 課題
電子情報棟の無線LANの更新
電子情報棟では、学生実験などでのノートパソコンのネットワーク接続手段 として、FERECのルータを活用している。 アクセスポイントのSSID,パスワードを知っている利用者であれば、 WiFi接続後に、Web認証が要求されるので、 自分の学籍番号ベースのIDとパスワードを入力すれば、 ネットワークが利用できるようになる。
ただし、ネットワーク接続によるトラブルを避けるために、 http,httpsしか利用できないようにFirewall機能を設定してある。 特別の登録IDを設定すれば、Firewallの条件を変えることもできる。
IEEE.802.11n対応ハイパワーAPに更新
これまでは、主要な実験室にはハイパワーのアクセスポイント、 実験的に導入していた部屋には、小型のアクセスポイントを設置していた。 元々の機材は11a.b.gに対応していたが、フロアや実験室の場所によっては、 電波が弱く接続が困難であった。
今回、業務用の11n対応のハイパワーアクセスポイントに変更し、 電波条件もかなり改善し、電子情報棟のすべての教室・大きな実験室では、 十分な電波強度でアクセスポイントに接続が可能となった。
払下げPCのセッティング
情報処理センターの払下げPCのセッティングを行う。 払下げ時のパスワードを変更し、 ウィルス対策ソフトを入れ、Microsoft Updateとなった。 最後に、BIOSのNetworkBootを停止させる。 でも、実験で必要そうなソフトを追加インストールしないといけないし、 Sambaのドメインに登録して、使えるようにしたいしな…
10台まとめてセッティングだけど、きびきびと動かないマシンじゃ、 待ち時間が長い。んで、複数台並行作業なんだけど、どのマシンはどこまでやったのか… という状態で、作業のヌケがありそう…