ずぼら向けパーサジェネレーター

http://d.hatena.ne.jp/ytqwerty/20050424#p1の続き。

反応をいただいたので、もう少し詳しく書くことにしましょう。
たとえば四則演算。

expression =>
| sum
+ int evaluate();
sum =>
| product
| add' x:sum "+" y:product -- left rec
| sub' x:sum "-" y:product -- left rec
divide => 
| product
| div' x:divide "/" y:clause -- left rec
product =>
| clause
| mul' x:product "*" y:clause -- left rec
clause =>
| "(" expression ")"
| integer' n:#integer

この文法ファイルの文法自体は、最近Adaが脳内デフォルトと化している影響を受けてはいますが、構成自体はYaccなんかのそれとそうかけ離れたモノではないと思います。
ただ、還元動作時のアクションを書くところが無くて、$$とか$1の代わりに、add'とかx:などと生成コード上で使われる名前を付けます。構文木を組み立てるために必要な、ノードの名前やフィールドの名前を与えているわけですね。
で、こうなります。

import lexical;

interface expression
{
  int evaluate();
}

interface sum
{
  int evaluate();
}

class add : sum, expression, clause, product, divide
{
  sum x;
  product y;
  int evaluate();
}

class sub : sum, expression, clause, product, divide
{
  sum x;
  product y;
  int evaluate();
}

interface divide
{
}

class div : divide
{
  divide x;
  clause y;
}

interface product
{
  int evaluate();
}

class mul : product, sum, divide, expression, clause
{
  product x;
  clause y;
  int evaluate();
}

interface clause
{
  int evaluate();
}

class integer : clause, product, sum, divide, expression
{
  token* n;
  int evaluate();
}

expression parse_expression(Scanner scanner)
{
  expression result;
  result = parse_sum(scanner);
  return result;
}

sum parse_sum(Scanner scanner)
{
  sum result;
  result = parse_product(scanner);
  while(is_keyword(scanner.next, "+") || is_keyword(scanner.next, "-"))
  {
    if(is_keyword(scanner.next, "+")){
      add r = new add;
      r.x = result;
      if(!is_keyword(scanner.next, "+")) throw new Exception("error");
      scanner.advance();
      r.y = parse_product(scanner);
      result = r;
    }else if(is_keyword(scanner.next, "-")){
      sub r = new sub;
      r.x = result;
      if(!is_keyword(scanner.next, "-")) throw new Exception("error");
      scanner.advance();
      r.y = parse_product(scanner);
      result = r;
    }
  }
  return result;
}

divide parse_divide(Scanner scanner)
{
  divide result;
  result = parse_product(scanner);
  while(is_keyword(scanner.next, "/"))
  {
    if(is_keyword(scanner.next, "/")){
      div r = new div;
      r.x = result;
      if(!is_keyword(scanner.next, "/")) throw new Exception("error");
      scanner.advance();
      r.y = parse_clause(scanner);
      result = r;
    }
  }
  return result;
}

product parse_product(Scanner scanner)
{
  product result;
  result = parse_clause(scanner);
  while(is_keyword(scanner.next, "*"))
  {
    if(is_keyword(scanner.next, "*")){
      mul r = new mul;
      r.x = result;
      if(!is_keyword(scanner.next, "*")) throw new Exception("error");
      scanner.advance();
      r.y = parse_clause(scanner);
      result = r;
    }
  }
  return result;
}

clause parse_clause(Scanner scanner)
{
  clause result;
  if(is_keyword(scanner.next, "(")){
    expression r;
    if(!is_keyword(scanner.next, "(")) throw new Exception("error");
    scanner.advance();
    r = parse_expression(scanner);
    if(!is_keyword(scanner.next, ")")) throw new Exception("error");
    scanner.advance();
    result = r;
  }else if(is_integer(scanner.next)){
    integer r = new integer;
    r.n = scanner.next;
    scanner.advance();
    result = r;
  }
  return result;
}

構文木にinterfaceというのはちょっとしたアイデアと思っています。
再帰下降なのは…状態遷移でやってくのも、理屈は理解してるつもりではあるのですが、こっちのほうが圧倒的にデバッグ含めて楽ということで勘弁してください。あと理屈は理解していても状態遷移表の生成アルゴリズムまでは理解していないので私が書くには調査が必要とか以下略。そんなわけで対応できる文法には制限がかかります。いちおう左再帰には対応したつもりですが。あと肝心のジェネレーターは今さっきでっち上げたばかりですのでこのコードの動作確認すらしていないためアップロードは憚られます…。
で、ユーザーはlexical.dというのを別に(手で)書いて、nextプロパティとadvanceメソッドを持ったScannerクラス、それからToken構造体、Token構造体をふるい分けるためのis_xxx関数群を用意しないといけません。
あとは雛形だけ生成された仮想関数(ここではevalute)の中身を埋めて完成。
実はDのような実装を混ぜて記述する言語ですと、この方式でパーサーを再生成するとevaluteの中身が消えてしまうのですよね…。
AdaやC++等のヘッダー分離型言語でヘッダーだけ生成するか、あるいはPascalみたいな言語でinterfaceかimplementationのいずれかの節を{$I}*1するか、が妥当と思います。

*1:cppライクに無加工includeを行う指令