PHPで字句解析 + 構文木生成ツールを作る

ハタさんのブログ(復刻版) : PHPだけで、パーサジェネレータ作る。（仮やハタさんのブログ(復刻版) : PHPだけで、構文解析 + 構文木ツール(?)作る。その２に影響を受けて、自分も作ってみることに。
とりあえずだいたい動くようになってきた。

文法定義

<?php

$f = TexpFactory::getCaller();
$e = ElementalTexpFactory::getCaller();

// 整数
$decimal_integer_leaf = $f( 'leaf', 'decimal_integer',
  $e( 'decimalInteger')
);
// 単項演算子
$unary_operator_leaf = $f( 'leaf', 'unary_operator',
  $f( 'char', '-+')
);
// 二項演算子
$binary_operator_leaf = $f( 'leaf', 'binary_operatro',
  $f( 'char', '+-*/')
);

// 再帰構造にするためあらかじめノード生成
$atom_node = $f( 'nnode', 'atom');
$exp_list_node = $f( 'nnode', 'exp_list');

// '(' exp_list_node ')'
$parenth_form = $f( 'seq',
  $f( 'char', '('),
  $f( 'ospace'),
  $exp_list_node,
  $f( 'char', ')'),
  $f( 'ospace')
);

// exp_atom := atom_node | parenth_form
$exp_atom = $f( 'orexp',
  $atom_node,
  $parenth_form
);

// exp_list_node := exp_atom ( binary_operator_leaf exp_atom )*
$exp_list_node->setup(
  $f( 'seq',
    $f( 'ospace'),
    $exp_atom,
    $f( 'ospace'),
    $f( 'olist',
      $f( 'seq',
        $binary_operator_leaf,
        $f( 'ospace'),
        $exp_atom
      )
    )
  )
);

// atom_node := integer_leaf 
//            | unary_operator_leaf integer_leaf
//            | unary_operator_leaf atom_node
//            | unary_operator_leaf parenth_form
$atom_node->setup(
  $f( 'seq',
    $f( 'orexp',
      $decimal_integer_leaf,
      $f( 'seq',
        $unary_operator_leaf,
        $f( 'ospace'),
        $decimal_integer_leaf
      ),
      $f( 'seq',
        $unary_operator_leaf,
        $f( 'ospace'),
        $atom_node
      ),
      $f( 'seq',
        $unary_operator_leaf,
        $f( 'ospace'),
        $parenth_form
      )
    ),
    $f( 'ospace')
  )
);

JavaScript で構文解析: Days on the Moonでの文法定義と比べてかなり長ったらしいものになっています

んでこれを解析にかけて構文木を表示する

<?php
$exp = ' -345 + ( 2 -( 5 + 4 ) / 2 ) - -122';
$node = $exp_list_node->process( new StringIterator( $exp));
$node->display();

結果

exp_list:
  atom:
    unary_operator:'-'
    decimal_integer:'345'
  binary_operatro:'+'
  exp_list:
    atom:
      decimal_integer:'2'
    binary_operatro:'-'
    exp_list:
      atom:
        decimal_integer:'5'
      binary_operatro:'+'
      atom:
        decimal_integer:'4'
    binary_operatro:'/'
    atom:
      decimal_integer:'2'
  binary_operatro:'-'
  atom:
    unary_operator:'-'
    decimal_integer:'122'

左再帰できないのでリスト形式で計算式を解釈しています。