技術

2.4. 基本的な式の構文解析

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第2章 万華鏡: 構文解析器とASTの実装
第4節 基本的な式の構文解析

処理するのが一番簡単な数値リテラルからまず着手する。
我々の文法における各構成要素を構文解析する関数を定義してみよう。
数値リテラル用としては以下のようになる。

/// numberexpr ::= number
static ExprAST *ParseNumberExpr() {
  ExprAST *Result = new NumberExprAST(NumVal);
  getNextToken(); // 数値を消費
  return Result;
}

この関数はとてもシンプルである。
現在のトークンがtok_numberの場合にこの関数が呼び出される事を想定している。
この関数は現在の数値(NumVal)を読み取り、NumberExprASTノードを生成し、字句解析器を次のトークンへと進め、そして最後にノードを返す。
幾つか興味深い点がこの関数にはある。
一番重要なのは、この関数が、処理対象の構成要素に合致する全てのトークンを読み取り、字句解析器のバッファを次のトークン(これは処理対象の構成要素ではない)に進めてから戻る点である。
これは、再帰下降構文解析において極めて標準的な方法である。
よりおもしろい例として、丸括弧は次のように定義できる。

/// parenexpr ::= '(' 式 ')'
static ExprAST *ParseParenExpr() {
  getNextToken();  // "("を消費。
  ExprAST *V = ParseExpression();
  if (!V) return 0;

  if (CurTok != ')')
    return Error("expected ')'");
  getNextToken();  // ")"を消費。
  return V;
}

この関数は、構文解析器についての興味深い点を幾つか示している。

  1. エラー関数の使い方を示している。
    この関数は、現在のトークンが”(“の場合に呼ばれることを想定しているが、副次式を解析した後、”)”の出現がない可能性がある。
    例えば、”(4)”ではなくて”(4 x”とユーザーが入力した場合、構文解析器はエラーを返すだろう。
    エラーは起こり得るので、それが起きたことを示す方法が構文解析器には必要となる。
    我々の構文解析器では、エラーの場合はnullを返す。
  2. 再帰的にParseExpressionを呼び出している。(さらにParseExpressionがParseParenExprを呼び出せることもすぐ後に知ることになるだろう。)
    これはパワフルである。
    なぜなら再帰的な文法の処理を可能とし、各構成要素をとてもシンプルに保つことが出来るからである。
    丸括弧そのものはASTノードの構築を行わないことに注意。
    このようなやり方の場合、丸括弧の一番重要な役割は、グルーピングの機能を提供し構文解析器を導く事である。
    構文解析器がASTを構築してしまえば、丸括弧は必要ない。

次は、変数の参照と関数の呼び出しの処理である。

/// identifierexpr
///   ::= identifier
///   ::= identifier '(' 式* ')'
static ExprAST *ParseIdentifierExpr() {
  std::string IdName = IdentifierStr;

  getNextToken();  // 識別子を消費。

  if (CurTok != '(') // 単なる変数の参照。
    return new VariableExprAST(IdName);

  // 関数呼び出し。
  getNextToken();  // "("を消費。
  std::vector<ExprAST*> Args;
  if (CurTok != ')') {
    while (1) {
      ExprAST *Arg = ParseExpression();
      if (!Arg) return 0;
      Args.push_back(Arg);

      if (CurTok == ')') break;

      if (CurTok != ',')
        return Error("Expected ')' or ',' in argument list");
      getNextToken();
    }
  }

  // ”)”を消費。
  getNextToken();

  return new CallExprAST(IdName, Args);
}

この関数は、他の関数と同じスタイルに従っている。(現在のトークンがtok_identifierの場合に呼び出されることを想定している。)
この関数もまた、再帰呼び出しやエラー処理を含む。
この関数の面白い点は、現在の識別子が単なる変数の参照か、関数呼び出しの式のどちらなのかを決定するために先読みの技法を使ってることである。
現在の識別子の後のトークンが”(“であるかどうかを見て、VariableExprASTとCallExprASTのどちらか適したほうのノードを生成する事によって、これを処理している。

簡単な式解析ロジックがうまいこと完成したので、それらをひとつのエントリポイントに纏め上げたヘルパー関数を定義できる。
我々はこれらの式の類を”プライマリ”式と呼ぶ。
その理由はあとの章でより明確になるだろう。
任意のプライマリ式を解析するために、以下のような式の分類が必要となる。

/// プライマリ
///   ::= identifierexpr
///   ::= numberexpr
///   ::= parenexpr
static ExprAST *ParsePrimary() {
  switch (CurTok) {
  default: return Error("unknown token when expecting an expression");
  case tok_identifier: return ParseIdentifierExpr();
  case tok_number:     return ParseNumberExpr();
  case '(':            return ParseParenExpr();
  }
}

これによって、これまでの幾つかの関数でCurTokの状態を仮定できてた理由がより明確になった。
先読みによって、どの種類の式として調査し解析されるべきか決定する。

これで基本的な式は処理可能となった。
次に我々は二項演算式(binary expressions)を処理出来るようにする必要がある。
それはちょっと複雑である。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください