Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
1
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

Cコンパイラ実装で躓いたところ

低レイヤを知りたい人のためのCコンパイラ作成入門

という Rui Ueyama氏による,有名なサイトが有る.(まったく入門ではないが)
そこを参考にコンパイラを作っていて,躓く点が非常に多かったため,ちょくちょく追加して行こうと思う.

つまずきポイント

token->strがNULLのときの動作

入力されたソースコードをtoken毎に分割していく後,最後のtokenはEOFだ,というふうな実装になっている.
その際,メンバ変数であるtoken->strにはNULLが代入される.
tokenizeが終わった後,構文木を構築する際,各種consumeという名の関数でtokenを消費していき構築していく.
その際,構文上予測されるtokenかどうかを判断し,間違っていればエラー処理関数であるerrorと,error_atを用いる.
この関数を用いると,視覚的に見やすくエラー表示がなされる.

例えばCのソースコードとして

1

が単体である場合,本来は;が来るはずであるが,この場合NULLになる.
error_at関数は,「;が予測されるけどNULLが入力されてるよ」と出力しようとする.
また,先頭から何文字目か,というのを表示する機能を持っている.以下のようなよく見るやつ.

1
 ^ expected ";" but given ""

このとき,位置を算出するために,事前に入力コード全体の文字配列の先頭ポインタを持つuser_inputが存在し,
それと,error_atにて渡される今現在見ている文字のポインタの差を取って,何文字目なのかを算出している.

もしココにNULLが渡された場合,(処理系によるが0周辺の値が多い?)差が膨大になるため,大量のスペースが
入力されてしまう.
コレによって,何が原因でエラーが発生したのかがわからなくなり.この問題自体を解決するのに数日かかった.

ちょうどセミコロンを構文に含んだと同時に発生したため,そもそも入力文字列が間違っているという想定がないことも,発見が遅れた原因だと思う.

extern宣言

extern宣言を用いて,ファイル間での変数の共有を行っているが,最初,変数を参照するすべてのファイルで
グローバル変数の宣言的なものをしてしまっていた.

Segmentation Fault

幾つかの設計簡略化のため,tokenはグローバルで保持されている.
ポインタでよくある話で,宣言,定義だけでは実体がない.それを失念していて,一生懸命実体のないリストの先頭から要素を追加しようとしていた.

グローバル変数は勝手に初期化されるものと言う認識が謎にあったみたい.(そもそも0で初期化されてるんだから有効なわけがない)

hoge.h
extern Token *token;
hoge.c
#include "hoge.h"

Token *token;

Token tok = calloc(1, sizeof(Token));
tok = ...;
token->next = tok;

もちろん結果はSegmentation Fault. Cのコンパイラどこで発生したか教えてくれないかなぁ(gdb/lldbを使えという話)

STEP. 10 複数文字のローカル変数

ポインタ初期化

またもやポインタの初期化を忘れていた.

parse.c
// variable finder
typedef struct LVar LVar;

struct LVar {
  LVar *next;
  char *name;
  int len;
  int offset;
};

LVar *locals;

static LVar *find_lvar(Token *tok) {
  for (LVar *var = locals; var; var = var->next) {
    if (var->len == tok->len && !memcmp(tok->str, var->name, var->len)) {
      return var;
    }
  }
  return NULL;
}

登録されてあるかを,連結リストを見て確認するが,初回のfind_lvar関数の呼び出し時に,グローバル変数localsNULLであるので,範囲外アクセスでSegmentation Fault
元記事には存在していなかったので,このぐらい自分でやれよ,なのか,もしかしたら自分が間違えているかも知れないが,よくわからん.
リファレンス実装にも初期化は書いておらず.なぜ動いているのか不明.

if (locals == NULL) {
  locals = calloc(1, sizeof(LVar));
}

をfind_lvar関数の頭につけて,NULLだったときに確保してやると動いた.

連結リストの実装が意味不明だった

なんとなく連結リストというと,頭のポインタが最初に用意されていて,その後に要素を引っ付けていくイメージだった.
一番最初だけは頭のポインタに要素を打ち込む.末尾のnextは常にNULL

if (locals == NULL) {
  locals = calloc(1, sizeof(LVar));
  locals->name = ...;
  locals->next = NULL;
  return;
}
LVar *lvar = calloc(0, sizeof(LVar));
lvar->name = ....;
lvar->next = NULL;
locals->next = lvar;

みたいな感じ.でも記事においては

lvar = calloc(1, sizeof(LVar));
lvar->next = locals;
lvar->name = ...;
locals = lvar;

となっていて,最初は意味がわからず,30分ほど考え続けた.
で,漸く,今作った新しい要素を先頭方向に追加して,localsのポインタ値を手前側に持ってくるってことをしていることに気づいた.
先頭のポインタは動かないっていう謎の考えがあったせい.

STEP. 11 Returnの実装

tokenizeがうまく言ってなかった (未解決) (解決)

記事通りのコードでは動かない場所があった.この程度も考えて解決できない人はプログラミングは向いてないので,たんぽぽを乗せる仕事をしたほうがいいという啓示だと思う.
自分はまだ考えても全くわかってないので,プログラミング向いていない.

ここではreturn実装のため,stmtに一部変更を加える.
しかし,そのとおりのコードでは動かない.
(自分で作ったコンパイラが吐く)エラーは

return 1;
       ^ expected ';', but 1;

である.エラーが出力される部分を見てみる.

parse.c
static Node *stmt() {
  Node *node;

  if (consume_keyword(TK_RETURN)) {
    node = calloc(1, sizeof(Node));
    node->kind = ND_RETURN;
    node->lhs = expr();
  } else {
    node = expr();
  }

  if (!consume(";")) {
    error_at(token->str, "expected ';', but %s", token->str);
  }
  return node;
}

細かな違いがあるものの大まかには記事と同様のコードである.なぜ動かないのか不明.
return文のEBNFは

stmt = expr ";" | "return" expr ";"

で,それを表現できてるとは思うのだが...

returnだったら,exprを左のノードに追加する.もう片方は存在しない.
exprはかなり上位のノードで,変数や数値,四則演算の式を示すことができる.
先程のreturn 1;では,1はexprなので,それが評価された後,;のtokenが消費されるはずなんだけど....
なんで?
return;は通るみたいだ.

追記:後に解決した.
そもそもtokenizeがうまく言っておらず,"return"という文字列がTK_RETURNとして認識されておらず,変数扱いとなっていたため,エラーが出ていた.
もしreturnという変数名が許容されるのであれば,あのエラーは正当なものになる.

直接的な原因は,自分がctype.hisalnum関数を用いており,この関数の返り値が,A-z0-9だったら0を返すであり,記事中で実装されていた独自の関数is_alnumとは逆であった.ちゃんと記事通りにしよう.プログラミング出来ないのに,下手にアレンジを加えるとすぐどこかに不整合が生じて,何倍もの時間を要してしまう.

C言語の標準ライブラリが真偽値を返してくれないので,ココらへんがいつになっても慣れない...

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
1
Help us understand the problem. What are the problem?