学習範囲

パーサの作成とスタックマシンの概要まで

パーサの作成

確認のため四則演算の生成規則は以下のような形となっています。

expr    = mul ("+" mul | "-" mul)*
mul     = primary ("*" primary | "/" primary)*
primary = num | "(" expr ")"

抽象構文木のノード型です。

// 抽象構文木のノードの種類
typedef enum {
  ND_ADD, // +
  ND_SUB, // -
  ND_MUL, // *
  ND_DIV, // /
  ND_NUM, // 整数
} NodeKind;

typedef struct Node Node;

// 抽象構文木のノードの型
struct Node {
  NodeKind kind; // ノードの型
  Node *lhs;     // 左辺
  Node *rhs;     // 右辺
  int val;       // kindがND_NUMの場合のみ使う
};

前回記述した関数とデータ型を使ってパーサを書いていきます。

expr関数

expr = mul ("+" mul | "-" mul)*　

意味: exprは１つのmulを受け取り、"+"か"-"で連結する式です。

このexpr式の生成規則が、そのまま関数呼び出しとループにマップされています。
consumeというのは前回定義した関数で、入力トークンの次のトークンがマッチしたときに、入力を1トークン読み進めて真を返します。

Node *expr() {
  Node *node = mul();

  for (;;) {
    if (consume('+'))
      node = new_node(ND_ADD, node, mul());
    else if (consume('-'))
      node = new_node(ND_SUB, node, mul());
    else
      return node;
  }
}

mul関数

mul = primary ("*" 　primary | "/" primary)　*

意味: mulは1つ以上のprimaryを受け取り、"*"　や　 "/" で連結する式です。

このmul式の生成規則が、そのまま関数呼び出しとループにマップされています。

Node *mul() {
  Node *node = primary();

  for (;;) {
    if (consume('*'))
      node = new_node(ND_MUL, node, primary());
    else if (consume('/'))
      node = new_node(ND_DIV, node, primary());
    else
      return node;
  }
}

primary関数

primary = num | "(" expr ")"

意味: 数値や括弧で囲まれた式を表しています。

以下のコードはprimary式の生成規則を表しています。

Node *primary() {
  // 次のトークンが"("なら、"(" expr ")"のはず
  if (consume('(')) {
    Node *node = expr();
    expect(')');
    return node;
  }

  // そうでなければ数値のはず
  return new_node_num(expect_number());
}

呼び出し例

例として1+2 * 3という式で考えてみます。

ステップ1.

expr→mul→primaryというように関数呼び出しが行われて、返り値として１を表す構文木が返される。

ステップ2.

exprの中のconsume('+')という式が真になるので、+というトークンが消費され、mulが再度呼び出される。残りは2*3となる。

ステップ3.

2というトークンが読み込まれるが、リターンはせずにmulの中のconsume('*')という式が真になるため、mulは再度primaryを呼び出す。

ステップ4.

3というトークンを読み込む。結果としてmulからは2*3を表す構文木が返る。

ステップ5.

リターンした先のexprでは、1を表す構文木と2 * 3を表す構文木が組み合わされて、1+2*3を表す構文木が構築される。

スタックマシン

スタックとはデータを積み木のように積み上げていくデータ構造のことです。

1. 新しくデータを積む場合には一番上に置く

これを "PUSH" という

2. データを取り出す場合には一番上のものを一つ取り出す

これを "POP" という

3. 要素を２つ取り出して、その結果を元の積み木の一番上に戻すこと。

これを "ADD"　という

2 * 3 + 4 * 5を計算する例です。

// 2 * 3を計算
PUSH 2
PUSH 3
MUL

※格納1には6が入っている

// 4 * 5を計算
PUSH 4
PUSH 5
MUL

※格納2には20が入っている

// 2 * 3 + 4 * 5を計算
ADD
※2箇所で格納している、値をそれぞれ取り出して足して
新たな格納3に26という値で収納する

まとめ

生成規則を関数として定義することでより柔軟な計算を行えることができました。これまでは一つの式の解しか保存していませんが、スタックの概念を使うことで複数の解を格納して計算できるようになります。徐々に電卓に近づいていると感じました。