C言語の自作コンパイル while文の表現

Question

C言語の自作コンパイラを作成したいと思っています。以下のlex, yacc, cのコードを用いてwhile文を表現したいのですが、うまくいきません。test.c の T_WHILEの部分がおかしいのかなと思うのですが、どのように変更したらよいか教えていただきたいです。

#include <stdio.h>
struct stab {
  int val;
  char name[20]; } stab[100];
int stabuse = 0;
struct node {
  int type, left, right; } ntab[400];
int ntabuse = 1;
#define T_STLIST 1
#define T_ASSIGN 2
#define T_READ 3
#define T_PRINT 4
#define T_ADD 5
#define T_SUB 6
#define T_MUL 7
#define T_DIV 8
#define T_REM 9
#define T_NUM 10
#define T_VAR 11
#define T_WHILE 12
#define T_IF 13
#define T_LT 14
#define T_GT 15
int lookup(char*);
int node(int, int, int);
void dotree(int);
extern char *yytext;
#include "y.tab.c"
#include "lex.yy.c"

int main() {
  yyparse();
  return 0;
}
int lookup(char *s) {
  int i;
  for(i = 0; i < stabuse; ++i)
    if(strcmp(stab[i].name, s) == 0) return i;
  if(stabuse >= 99) {
    printf("table overflow.\n"); exit(1); }
  strcpy(stab[stabuse].name, s); return stabuse++;
}
int node(int t, int l, int r) {
  int i = ntabuse++;
  ntab[i].type = t;
  ntab[i].left = l;
  ntab[i].right = r;
  return i;
}
void dotree(int i) {
  int stk;
  printf(" .section .rodata\n");
  printf(".Lprompt: .string\"> \"\n"); /* プロンプト */
  printf(".Lread: .string\"%%ld\"\n"); /* 読み取り用書式 */
  printf(".Lprint: .string\"%%ld\\n\"\n"); /* 書き出し用書式 */
  printf(" .text\n");
  printf(".global main\n");
  printf("main:\n");
  printf(" pushq %%rbp\n");
  printf(" movq %%rsp,%%rbp\n");
  stk = (8*stabuse + 15) / 16; /* 変数の個数*8 で 16 の倍数へ切り上げ */
  stk *= 16;
  printf(" subq $%d,%%rsp\n", stk);
  emittree(i);
  printf(" leave\n");
  printf(" ret\n");
}

void emittree(int i)
{
  static int labelno = 1;
  int l;
  switch(ntab[i].type) {
  case T_STLIST: if(ntab[i].left) emittree(ntab[i].left);
    emittree(ntab[i].right);
    break;
  case T_READ: printf(" movq $.Lprompt,%%rdi\n");
    printf(" movq $0,%%rax\n"); /* 浮動小数点レジスタを使わない */
    printf(" call printf\n");
    printf(" leaq %d(%%rbp),%%rsi\n", -(ntab[i].left+1)*8);
    printf(" movq $.Lread,%%rdi\n");
    printf(" movq $0,%%rax\n"); /* 浮動小数点レジスタを使わない */
    printf(" call scanf\n");
    break;
  case T_PRINT: emittree(ntab[i].left);
    printf(" popq %%rsi\n");
    printf(" movq $.Lprint,%%rdi\n");
    printf(" movq $0,%%rax\n"); /* 浮動小数点レジスタを使わない */
    printf(" call printf\n");
    break;
  case T_NUM: printf(" pushq $%d\n", ntab[i].left);
    break;
  case T_VAR: printf(" pushq %d(%%rbp)\n", -(ntab[i].left+1)*8);
    break;
  default: printf("NotImplemented: %d\n", ntab[i].type);
    break;
  case T_ASSIGN: emittree(ntab[i].right);
    printf(" popq %d(%%rbp)\n", -(ntab[i].left+1)*8);
    break;
  case T_ADD: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rdx\n");
    printf(" popq %%rax\n");
    printf(" addq %%rdx,%%rax\n");
    printf(" pushq %%rax\n");
    break;
  case T_SUB: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rdx\n");
    printf(" popq %%rax\n");
    printf(" subq %%rdx, %%rax\n");
    printf(" pushq %%rax\n");
    break;
  case T_MUL: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rdx\n");
    printf(" popq %%rax\n");
    printf(" imulq %%rdx\n");
    printf(" pushq %%rax\n");
    break;
  case T_DIV: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rsp\n");
    printf(" popq %%rax\n");
    printf(" movq $0,%%rdx\n");
    printf(" idivq %%rsp\n");
    printf(" pushq %%rax\n");
    break;
  case T_REM: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rsp\n");
    printf(" popq %%rax\n");
    printf(" movq $0,%%rdx\n");
    printf(" idivq %%rsp\n");
    printf(" pushq %%rdx\n");
  case T_LT: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rcx\n");
    printf(" popq %%rax\n");
    printf(" cmp %%rcx,%%rax\n");
    printf(" jge ");
    break;
  case T_GT: emittree(ntab[i].left);
    emittree(ntab[i].right);
    printf(" popq %%rcx\n");
    printf(" popq %%rax\n");
    printf(" cmp %%rcx,%%rax\n");
    printf(" jle ");
    break;
  case T_IF: l = labelno++;
    emittree(ntab[i].left);
    printf(".L%d\n", l);
    emittree(ntab[i].right);
    printf(".L%d:\n", l);
    break;
  case T_WHILE:  　　　　 // この部分
　 l = labelno++;　　// ラベル番号更新
    printf(".L%d:\n", l);   // ラベル l 生成
    emittree(ntab[i].left);　// 分岐条件判定
    printf(".L%d\n", l+1);　// 不成立なら l+1に移動
    emittree(ntab[i].right);　// 成立していたら、中身を実行
    printf(".L%d\n", l);　// 前のラベル l に戻る
    printf(".L%d:\n", l+1);　// ラベル l+1 生成
    break;
  }
}

%token NUM;
%token IDENT;
%token READ;
%token PRINT;
%token WHILE;
%token IF;
%left '+' '-';
%left '*' '/';
%%
prog : IDENT '{' stlist'}' { dotree($3); return 0; }
;
stlist : { $$ = 0; }
| stlist stat { $$ = node(T_STLIST, $1, $2); }
;
stat : var '=' expr ';' { $$ = node(T_ASSIGN, $1, $3); }
| READ var ';' { $$ = node(T_READ, $2, 0); }
| PRINT expr ';' { $$ = node(T_PRINT, $2, 0); }
| WHILE '(' cond ')' stat { $$ = node(T_WHILE, $3, $5); }
| IF '(' cond ')' stat { $$ = node(T_IF, $3, $5); }
| '{' stlist '}' { $$ = $2; }
;

cond : expr '<' expr { $$ = node(T_LT, $1, $3); }
| expr '>' expr { $$ = node(T_GT, $1, $3); }
;
expr : term { $$ = $1; }
| expr '+' term { $$ = node(T_ADD, $1, $3); }
| expr '-' term { $$ = node(T_SUB, $1, $3); }
;
term: prim{ $$ = $1; }
| term '*' prim { $$ = node(T_MUL, $1, $3); }
| term '/' prim { $$ = node(T_DIV, $1, $3); }
| term '%' prim { $$ = node(T_REM, $1, $3); }
;

prim : NUM { $$ = node(T_NUM, atoi(yytext), 0); }
| var { $$ = node(T_VAR, $1, 0); }
| '(' expr ')' { $$ = $2; }
;
var : IDENT { $$ = lookup(yytext); }
;

alpha [a-zA-Z]
digit [0-9]
white [\n\t ]
%%
while { return WHILE; }
if { return IF; }
read { return READ; }
print { return PRINT; }
{alpha}({alpha}|{digit})* { return IDENT; }
{digit}+ { return NUM; }
[-+()=;{}<>*/%] { return yytext[0]; }
{white} { ; }

Comments

[itagagaki]

> うまくいきません
これでは伝わりません。何がどうなるのですか？
whileが含まれなければ期待どおりの結果になるのですか？

[j0ker_9]

-----------------
main {
read x;
i = 0;
while(x > 0){
i = i + x;
x = x - 1;
}
print i;
-----------------
このようなwhile文を含んだファイルを作成しコンパイルすると、以下のように表示されます。

>cc test4.s
test4.s: Assembler messages:
test4.s:41: Error: unknown pseudo-op: `.l1'

whileではない場合(ifや加算など)の場合はうまく動作します。

[melian]

printf(".L%d\n", l);　// 前のラベル l に戻る
ですが、ここは jmp 命令ではないでしょうか。
printf("jmp .L%d\n", l);　// 前のラベル l に戻る

Answer 1

解決済みになっていますが、解決していません。次のコードがエラーになります。

main {
	i = 0;
	while (i < 5) {
		print i;
		i = i + 1;
	}
	i = 3;
	while (i > 0) {
		print i;
		i = i - 1;
	}
}

Answer 2

わかりました

    emittree(ntab[i].right);　// 成立していたら、中身を実行
    printf(".L%d\n", l);　// 前のラベル l に戻る

ここではntab[i].right（ステートメントまたはブロック）は条件分岐オペコードを出力しないわけですから、

    emittree(ntab[i].right);　// 成立していたら、中身を実行
    printf("jmp .L%d\n", l);　// 前のラベル l に無条件ジャンプ

じゃないですか？

Comments

[j0ker_9]

長いコードの解析ありがとうございました。とても助かりました。

Answer 3

whileはラベル2つつかうから、l = labelno++では足りない気がするけど、これは本質ではなさそう。
whileのボディが「 emittree(ntab[i].right);　// 成立していたら、中身を実行」で解釈されるわけだけど、その最後はjmpを出力しないのでは。なので 「 printf(".L%d\n", l);　// 前のラベル l に戻る」ここのラベルだけ生えてきてエラーになる。
「printf("jmp .L%d\n", l);　// 前のラベル l に戻る」かな。

Answer 4

おそらくwhileだけでなくifもダメなのでは。

printf(".L%d\n", l+1);　// 不成立なら l+1に移動

これアセンブラ命令になっていませんね。
たとえばx86アセンブラなら、条件付きのジャンプとしてjz、jc、jo、jsがあります。
無条件ジャンプならjmpです。

「不成立なら」の条件はどこで得られるのでしょうか。その仕組みが入っていないように見えます。

Comments

[j0ker_9]

case T_IF:
l = labelno++;
emittree(ntab[i].left);
printf(".L%d\n", l);
emittree(ntab[i].right);
printf(".L%d:\n", l);
break;

条件式では、まずラベル番号を用意します。(emittree() を呼び出して) 条件判定命令
と分岐命令の一部を生成してから、成り立たなかった時の飛び先を埋めます。ついで中身
の文を生成し、その後でラベルを生成します。では、試してみましょう。

-----------------------
while以外の部分はほとんどコピペであり、if文の説明は上記のように書かれていました。実際に以下のようなif文を動かしてみましたが正常に動作しました。そのため、問題はwhile文のみかと思います。

実際に動かしたif文
main {
read x;
if(x > 0) print 1;
if(x < 0) print 0;
}

[itagagaki]

T_WHILEで
emittree(ntab[i].left);
で条件式の評価を行って、その先で最終的に T_GT 等でオペコード
printf(" jle ");
が出力されることが期待されていて、帰って来てから
printf(".L%d\n", l+1);　// 不成立なら l+1に移動
でオペランド（ジャンプ先ラベル）を出力しているのですね。

T_GTには到達しているのでしょうか？
出力された .s ファイル全体はどうなっているのですか？

[j0ker_9]

出力された.sファイルは以下のようになっています。長文になりますがよろしくお願いいたします。

.section .rodata
.Lprompt: .string"> "
.Lread: .string"%ld"
.Lprint: .string"%ld\n"
.text
.global main
main:
pushq %rbp
movq %rsp,%rbp
subq $16,%rsp
movq $.Lprompt,%rdi
movq $0,%rax
call printf
leaq -8(%rbp),%rsi
movq $.Lread,%rdi
movq $0,%rax
call scanf
pushq $0
popq -16(%rbp)
.L1:
pushq -8(%rbp)
pushq $0
popq %rcx
popq %rax
cmp %rcx,%rax
jle .L2
pushq -16(%rbp)
pushq -8(%rbp)
popq %rdx
popq %rax
addq %rdx,%rax
pushq %rax
popq -16(%rbp)
pushq -8(%rbp)
pushq $1
popq %rdx
popq %rax
subq %rdx, %rax
pushq %rax
popq -8(%rbp)
.L1
.L2:
pushq -16(%rbp)
popq %rsi
movq $.Lprint,%rdi
movq $0,%rax
call printf
leave
ret