1. Top » 
  2. 計算機科学実験及実習

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  • Genre:

コンパイラについてのメモ #10 閑話休題

実際ブログはかなり後書きで書いているわけで、自分の復習を兼ねている。
というわけで今やっているアセンブリコードの生成部分を軽くメモ。
結局は構文木を読んで出力するんだけどね。

int square(int x){
return x * x;
}

int squaresum(int x, int y){
return square(x) + square(y);
}

int pythagoras(int x, int y, int z){
if( square(x) == squaresum(y,z) )
return 1;
else
return 0;
}


現実的には実用性はないけど、こういう簡単な例しか思い浮かばないのです。
というか初期値代入使えない、配列使えないのでできることが少ない。
これをアセンブリコードで出力させるのらよ。

二乗する部分はこんな感じ。

    
GLOBAL _square

_square
push ebp
mov ebp, esp
sub esp, 4
mov eax, [ebp+8]
mov [ebp-4], eax
mov eax, [ebp+8]
imul eax, [ebp-4]
jmp _square0
_square0
mov esp, ebp
pop ebp
ret



二乗和はこう


GLOBAL _squaresum

_squaresum
push ebp
mov ebp, esp
mov eax, [ebp+12]
push eax
CALL _square
mov [ebp-4], eax
mov eax, [ebp+8]
push eax
CALL _square
add eax, [ebp-4]
jmp _squaresum1
_squaresum1
mov esp, ebp
pop ebp
ret


ピタゴラス判定はこう

    GLOBAL    _pythagoras

_pythagoras
push ebp
mov ebp, esp
mov eax, [ebp+12]
push eax
mov eax, [ebp+16]
push eax
CALL _squaresum
mov [ebp-4], eax
mov eax, [ebp+8]
push eax
CALL _square

cmp eax, [ebp-4]
jne _IF3
mov eax, 1
jmp _pythagoras2
jmp _IF4
_IF3

mov eax, 0
jmp _pythagoras2
_IF4

_pythagoras2
mov esp, ebp
pop ebp
ret



吐き出すコードが冗長なんだが、もう直す時間はなさそう。
スポンサーサイト

コンパイラについてのメモ #9

次々と文法について見てきます。

compound_statement:
LTK csopt RTK
;
複文は{}で囲まれています。

csopt:
|declaration_list
|statement_list
|declaration_list statement_list
;
複文の中身は空か、宣言だけか、文だけか、又は変数宣言と式の両方です

declaration_list:
declaration
|declaration_list declaration
;
宣言は一つの宣言の繰り返しです

statement_list:
statement
|statement_list statement
;
文は一つの文の繰り返しです

expression:
assignment_expr
|expression COMMA assignment_expr
;
式はassignment又はその繰り返しです

assignment_expr:
logical_OR_expr
|IDENTIFIER IN assignment_expr
;
assignment式はOR式か代入文です

logical_OR_expr:
logical_AND_expr
|logical_OR_expr OR logical_AND_expr
;
OR式はAND式かAND式とOR式のORです

logical_AND_expr:
equality_expr
|logical_AND_expr AND equality_expr
;
AND式は等式か等式とAND式のANDです

equality_expr:
relational_expr
|equality_expr EQ relational_expr
|equality_expr NEQ relational_expr
等式は関係式か等式か不等式です

relational_expr:
additive_expr
|relational_expr MT additive_expr
|relational_expr LT additive_expr
|relational_expr MTE additive_expr
|relational_expr LTE additive_expr
;
関係式は>か<か>=か<=です

additive_expr:
multiplicative_expr
|additive_expr ADD multiplicative_expr
|additive_expr SUB multiplicative_expr
その一つ一つの式は式の和か差です

multiplicative_expr:
unary_expr
|multiplicative_expr MUL unary_expr
|multiplicative_expr DIV unary_expr
;
一つ一つの和や差に出てくる式はかけ算か割り算です

unary_expr:
posifix_expr
|SUB unary_expr
;
かけ算割り算に出てくる一つ一つはある項か単項演算子のマイナスがついている項です

posifix_expr:
primary_expr
|IDENTIFIER LK RK
|IDENTIFIER LK argument_expression_list RK
;
一つ一つの項は識別子や関数呼び出しです

primary_expr:
IDENTIFIER
|CONSTANT
|LK expression RK
;
素項は変数か定数か式か、又は括弧の式です。

argument_expression_list:
assignment_expr
|argument_expression_list COMMA assignment_expr
;
関数への変数の渡す物は代入式などその他です



以上。
実に長い文法・・・とはいえ、結構短いですな。
実際にこれを作って

bison -d parser.y



などとしてファイルを通してみると、実際に文法チェックされます。

コンパイラについてのメモ #8

コンパイラについての話、続きです。
実際の文法について見ていきましょう。
簡単に日本語で注釈を入れていきますけど、本当はダメです。
日本語は使えません、後は-と、その他には$とか使えません。

program:
external_declaration
|program external_declaration
;
プログラムは外部宣言という要素の繰り返しです。

external_declaration:
declaration
|function_defunction
;
外部宣言は変数宣言又は関数定義です

declaration:
INT declarator_list
;
変数宣言はINTで始まってdeclaratorのリストです

declarator_list:
declarator
|declarator_list COMMA declarator
;
declaratorのリストとはdeclaratorの繰り返しです。

declarator:
IDENTIFIER
;
declaratorは識別子です。

function_defunction:
INT declarator LK ptlo RK compound_statement
;
関数宣言はINTで始まって定義式が来て、()の間にパラメータ、
その後ろに複文がつきます。

ptlo:
|parameter_type_list
;
パラメータは空もしくはパラメータのリストです

parameter_type_list:
parameter_declaration
|parameter_type_list COMMA parameter_declaration
;
パラメータのリストとはパラメータの宣言の繰り返しです

parameter_declaration:
INT declarator
;
パラメータの宣言とは変数宣言です

statement:
SCOLON
|expression SCOLON
|compound_statement
|IF LK expression RK statement elseopt
|WHILE LK expression RK statement
|RETURN expression SCOLON
|RETURN SCOLON
;
文というのは次の6種類です
 1.空の文
 2.式
 3.複文
 4.IF文
 5.WHILE文
 6.RETURN式(値を返す)
 7.RETURN式(値を返さない)

elseopt:
|ELSE statement
;
elseのオプションについての記述



おぉぉ。だんだんそれっぽくなってきました。
まだまだ文法について見ていきます。

コンパイラについてのメモ #7

文法ファイルを書いていく。
とはいえ文法ファイルは実験指定なので、間違えないように書いていきます。
まずはどんなトークン(終端記号)を使うのかを書く。
例えば終端記号に

 定数    CONSTAN
 識別子   IDENTIFIER
 等号    = != ==
 四則演算  + * / -


などを使いますよと宣言しておく。
するとbisonを通して*.tab.hファイルにしたときにASCIIコードで
利用している部分にかぶらない定数を割り当ててくれる。
あとはdefineされているCONSTANTやADD、IDENTIFIERなどをプログラムの中で使える。

%{
#include <stdio.h>
#include <stdlib.h>
#include "common.h"
#include "common.c"
%}
%error_verbose

%token IDENTIFIER CONSTANT INT
%token COMMA COLON SCOLON IF WHILE ELSE RETURN
%token LK RK LTK RTK // ( ) { }
%token IN // =
%token OR // ||
%token AND // &&
%token EQ // ==
%token NEQ // !=
%token LT MT LTE MTE // < > <= >=
%token ADD SUB MUL DIV // + - * /

%token CONS
%token DECLARATION
%token DECLARATIONL
%token DECLARATOR
%token DECLARATORL
%token STATEL
%token PARAM
%token PARAML
%token FUNDEF
%token EXPR
%token VAL
%token ARGS
%token R
%token CPMD_STM
%token POSF
%token UNARY
%token NONE
%token PRG


まぁ、たくさんあっても別に問題ないので多めに書いておく。

次に共用体を使うためにこんなおまじないを書きます。

%union{
int i;
char *str;
tree t;
}


これを書いておくと、終端記号が還元されるとき
(たとえばCONSTAN->10になったり、IDENTIFIER->mainになったりするとき)
そのときに魔法がかかって、時には整数、時には文字、時にはtreeといったように
複数の型に還元できるようになる。
その代わり、どのルールがどれに変化するかを書かないといけなくなる。つまり

 program   -> t
 IDENTIFIER -> str
 CONSTANT -> i


になどです。ここのtとかstrとかiというのは、unionの命令を書いた所の名前です。
というわけで次のように書きます。

%type <str>	IDENTIFIER
%type <i> CONSTANT
%type <t> main program external_declaration declaration declarator_list
declarator function_defunction parameter_type_list parameter_declaration
statement compound_statement declaration_list statement_list expression
assignment_expr logical_OR_expr logical_AND_expr equality_expr
relational_expr additive_expr multiplicative_expr unary_expr posifix_expr
primary_expr argument_expression_list


この大量の英羅列は、後に説明します。
それぞれが意味を持っていて、例えばfunction_defuntionは関数選言の部分を
multiplicative_exprは積の項を・・・とだんだん小さい要素を表しています。

以上が文法ファイルの定義セクションです。
また文法ファイルの末尾は次のように書くのがお決まりらしいのでそうします。

extern int yylineno;
int yyerror(char *s){
fprintf(stderr, "%d: %s\n", yylineno, s);
return 0;
}
main(){
yyparse();
}



以上です。
さて、定義セクションと最後のお決まり部分の間に書く文法部分を次に説明します。

コンパイラについてのメモ #6

構文解析をした結果をうまく表現するために構文木を作る。
そのためにどんどん関数を作っていこう。

#include <string.h>
#include "parser.tab.h"

定数ノードの表現
tree make_constant_node(int i){
tree ne = (tree)malloc(sizeof(union node));
ne->co.op = CONSTANT;
ne->co.value = i;
return ne;
}

識別子の表現
tree make_token_node(char *s){
tree ne = (tree)malloc(sizeof(union node));

ne->tk.op = IDENTIFIER;
ne->tk.name = strdup(s);
return ne;
}

一つの接点、四つ組の表現
tree make_tuple(int op, tree t1, tree t2, tree t3, tree t4){
tree ne = (tree)malloc(sizeof(union node));
ne->tuple.op = op;
ne->tuple.a[0] = t1;
ne->tuple.a[1] = t2;
ne->tuple.a[2] = t3;
ne->tuple.a[3] = t4;
return ne;
}



共用体を使っているので、なんか旨く書けるみたい。
共用体が含む全ての構造体の共通メンバをうまくアクセス出来る技なんだって。

あ、そういえばまだ文法(yファイル、bisonが食べる)を書いてなかった。

コンパイラについてのメモ #5

引き続きコンパイラ製作。
字句解析はflex、構文解析はbisonが行う。
結局今からやることは、その出力を利用して構文木を作る。
そしてソースファイルをうまく表示すること。

#include <string.h>
typedef struct tk{
int op;
char *name;
} *token;
typedef struct tuple{
int op;
union node *a[4];
} *tuple;
typedef struct co{
int op;
int value;
} *constant;
typedef union node{
struct{
int op;
}n;
struct tuple tuple;
struct tk tk;
struct co co;
} *tree;

tree make_constant_node(int);
tree make_token_node(char *);
tree make_tuple(int, tree, tree, tree, tree);


とりあえず構文木を表現するための構造体、共用体。
その操作のための関数を準備しよう。

コンパイラについてのメモ #4

C言語のとても小さいやつ、 Tiny Cというのが今回の実験の対象。
字句解析はflex、構文解析はbisonに任せる。
というわけで実際にC言語で使うような字句を区切るためには
こんな感じのlexファイルにしたらいいんじゃないかな。

%option noyywrap
%option yylineno

%{
#include "second.tab.h"
%}

ALPHA [A-Za-z]
ALPHAP [A-Za-z_]
DIGIT [0-9]

%%
else {return (ELSE);}
if {return (IF);}
int {return (INT);}
return {return (RETURN);}
while {return (WHILE);}

{ALPHA}{ALPHAP}* {return (IDENTIFIER);}

{DIGIT}* {return (CONSTANT); }

"," {return COMMA;}
";" {return SCOLON;}
"(" {return LK;}
")" {return RK;}
"{" {return LTK;}
"}" {return RTK;}
"=" {return IN;}
"||" {return OR;}
"&&" {return AND;}
"==" {return EQ;}
"!=" {return NEQ;}
"<" {return LT;}
">" {return MT;}
"<=" {return LTE;}
">=" {return MTE;}
"+" {return ADD;}
"-" {return SUB;}
"*" {return MUL;}
"/" {return DIV;}

[ \t\n] ;
. {yyerror("Error: invalid character");}

%%




実験が少しずつ進んでいきます・・・。
これを利用して文法に正しいかどうか合致するかどうかを検査するのがbisonの仕事。
次はそれを考えます。
(とはいっても文法は指定されてるのだけどね)

コンパイラについてのメモ #3

文法ファイル(bisonが処理するもの、拡張子.y)は実験では指定されている。
ともかく簡単な例で確認しよう。
例示は理解の試金石なのだから。

足し算と掛け算だけを解析する文法とは
掛け算は足し算よりも優先順位が高いことに注意します。

%{
#include <stdio.h>
%}
%token Integer
%%
program:
expr { printf("%d\n", $1); }
;
expr:
mult_expr { $$ = $1; }
| mult_expr '+' expr { $$ = $1 + $3; }
;
mult_expr:
Integer { $$ = $1; }
| Integer '*' mult_expr { $$ = $1 * $3; }
;
%%
int yyerror(char *s){
fprintf(stderr, "%s\n", s);
return 0;
}
main(){
yyparse();

}



この文法ではIntegerとう存在を定義します(defineみたいに)
これは終端記号→これ以上細分化できないもので、数値です。
こんなのはtokenと書いてファイルの先頭に定義できます。

結局文法が言っていることは

 プログラム → 式
 式 → 乗算後の式
     又は 乗算後の式+式
 乗算後の式 → 数値
         又は 数値×数値

と言っています。
ようするに掛け算は足し算よりも先に計算することをいっています。

結局これをbisonに通します

bison -d calc.y



-dを使うことでcalc.tab.hというヘッダを作ってくれます。
これの中にtokenなどがどのようにdefineされるのかとかを書いてくれるらしいです。
あとはyyerrorなどもおそらく書いてくれます。これを使ってflexと連携します。


流れ

1.bison -d calc.y
->making calc.tab.c and calc.tab.h
2.flex calc.l
->making lex.yy.c using calc.tab.h



こうして一連に必要なファイルが全部できる。(らしい)

コンパイラについてのメモ #2

結局、字句解析を行ってもらうためにFlexに命令します。
lexではおなじみ、正規表現を利用してトークンを定義する。
つまり

 ある正規表現 → やること

という変換表一覧を作って書いてやる。
それをlexに通すと自動的にLexerとしてlex.yy.cというファイルにしてくれます。

lexのファイルの形式

%{
・・・最初の部分(そのままレキシカルアナライザに書かれる)・・・
%}
%%
・・・定義部(対応表を書く)・・・
%%
・・・コード部(使わない)・・・
%%




定義部の部分に正規表現→行動の対応を書く。
最初の部分にはその処理に利用するヘッダであったりとか
その他にもyaccで作るヘッダを入れてみたり、名前を定義したりする(マクロ)。


すごい簡単な例

%option noyywrap
%{
%}
%%
[0-9]+ {printf("VALUE=%s\n", yytext);}
"+"|"*"|"-" {printf("OPT=%s\n" , yytext);}
[ \t\n] ;
. ;
%%
main(){
yylex();
}


最後の 「.」 はすべてのパターンに一致しなかったことを示す。
つまり判別するパターンは全部で3つです。


1.数字
 数字の場合、lexして取ってきた物(勝手にyytextに代入されている)を出力。
 
2.演算子+と*と-
 文字をそのまま出力

3.スペース及びタブ及び改行は無視する
 [ \t\n] ;

といったことが書いてあります。
最後のmainを書くことで、この部分が出力されるファイル lex.yy.cに出される。
これをコンパイルすることでレキシカルアナライザを実行できる。


実行手順

@:flex calc.l
@:gcc -o cl lex.yy.c
@:cl < sample



例えばsampleに 「4-3」 と書いておくと次のように出力されます。


cl < sample
VALUE=4
OPT=-
VALUE=3


 最初に4という値、次に演算子-、最後に値3が入ってくる

というのが字句分析の結果です。
これをもっと上手く使うとコンパイラに流用できるよっていうお話らしい。
難しいね。

コンパイラについてのメモ #1

実験の課題:コンパイラの作成
コンパイラの勉強したことのない自分、涙目。


コンパイラの処理
 1.ソースを書く

 2.ソースの字句解析 ← Lexical Analyzerが行う

 3.ソースの構文解析 ← parserが行う

 4.コード生成 → 要するにアセンブリを作るということ

 5.最適化する


実験では1→5までやるらしい。
なんていう無茶ぶり!!(;・∀・)


実験ではLexとParserを作るために別のプログラムを利用しますのよ。
その名前をlex、yaccと呼びます。今回の実験では

 Lexical Analyzer ←作る- lex : flex
 Parser ←作る- yacc : bison

というプログラムを使います。

Page Top

訪問者

お引っこし。 http://parabola.sblog.jp/

プロフィール

parabola0

Author:parabola0
Twitter用ですが…。
プロフィール

最新記事
最新コメント
最新トラックバック
カテゴリ
月別アーカイブ
検索フォーム
リンク

このブログをリンクに追加する

QRコード
QRコード
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。