PHPで仮想マシンベースの正規表現エンジンを作ってみる 第一回

To start, we'll define a regular expression virtual machine (think Java VM). The VM executes one or more threads, each running a regular expression program, which is just a list of regular expression instructions. Each thread maintains two registers while it runs: a program counter (PC) and a string pointer (SP). 
 
 The regular expression instructions are: 
 
    char c     If the character SP points at is not c, stop this thread: it failed.
               Otherwise, advance SP to the next character and advance PC to the next instruction. 
    match      Stop this thread: it found a match. 
    jmp x      Jump to (set the PC to point at) the instruction at x. 
    split x, y Split execution: continue at both x and y. Create a new thread with SP 
               copied from the current thread. One thread continues with PC x. 
               The other continues with PC y. (Like a simultaneous jump to both locations.)

* hoge|fuga  "|"による選択を利用できます
* a(ho|ge)b  括弧によるグルーピングができます
* a+b*c?     "+"や"*"や"?"などの繰り返し演算子が利用できます

<?php
include_once __DIR__ . '/../vendor/autoload.php';
class RegexSyntaxParser implements PEG_IParser
{ 
    protected $regexParser;
    function __construct()
    {
        /*
         * regex <- split*
         * split <- operations ("|" operations)*
         * operations <- operation*
         * operation <- target operator
         * target <- charClass / group / singleCharacter
         * suffixOperator <- "*" / "+" / "?"
         * group <- "(" split ")"
         * charClass <- "[" (!"]" .)+ "]"
         * singleCharacter <- ![+*?|[)] .
         */
        $singleCharacter = self::objectize('singleCharacter', 
            PEG::second(PEG::not(PEG::choice('*', '+', '?', '|', '[', ')')), PEG::anything())
        );
        $charClass = self::objectize('charClass', PEG::second(
            '[', 
            PEG::many1(PEG::second(PEG::not(']'), PEG::anything())),
            ']'
        ));
        $group = self::objectize('group', PEG::memo(PEG::second(
            '(', PEG::ref($split), ')'
        )));
        $suffixOperator = self::objectize('suffixOperator', PEG::choice('*', '+', '?'));
        $target = PEG::choice(
            $charClass, $group, $singleCharacter
        );
        $operation = self::objectize('operation', 
            PEG::seq($target, PEG::optional($suffixOperator))
        );
        $operations = self::objectize('operations', PEG::many($operation));
        $split = self::objectize('split', 
            PEG::choice(PEG::listof($operations, '|'), '')
        );
        $this->regexParser = self::objectize('regex', PEG::many($split));
    }
    /**
     * @return PEG::IParser
     */
    function getParser() 
    {
        return $this->regexParser;
    }
    /**
     * @param String $str
     */
    function parse(PEG_IContext $context)
    {
        return $this->regexParser->parse($context);
    }
    /**
     * @param PEG_IParser
     * @return PEG_IParser
     */
    protected static function objectize($name, PEG_IParser $parser)
    {
        return PEG::hook(function($result) use($name) {
            return new RegexSyntaxNode($name, $result);
        }, $parser);
    }
}
class RegexSyntaxNode
{
    protected $name, $content;
    function __construct($name, $content) 
    {
        $this->name = $name;
        $this->content = $content;
    }
    function __toString()
    {
        $result = '';
        $result .= $this->name . " {\n";
        $result .= $this->dump($this->content);
        $result .= "}";
        return $result;
    }
    protected function dump($content)
    {
        $result = '';
        if (is_array($content)) {
            foreach ($content as $i => $element) {
                $result .= $this->dump($element);
            }
        } elseif ($content instanceof self) {
            $result .= self::indent($content->__toString()) . "\n";
        } else {
            $result .= self::indent(var_export($content, true)) . "\n";
        }
        return $result;
    }
    static function indent($str) {
        $lines = preg_split("/\r|\n|\r\n/", $str);
        foreach ($lines as $i => $line) {
            $lines[$i] = '  ' . $line;
        }
        return implode($lines, "\n");
    }
}

<?php
include_once __DIR__ . '/../src/PHPRegex.php';
$parser = new RegexSyntaxParser();
echo 'a => ' . $parser->parse(PEG::context('a')) . "\n\n";
echo 'a|b =>' .  $parser->parse(PEG::context('a|b')) . "\n\n"; 
echo 'a(bc) => ' . $parser->parse(PEG::context('a(bc)')) . "\n\n";
echo 'a+b*c? => ' . $parser->parse(PEG::context('a+b*c?')) . "\n\n";

a => regex {
  split {
    operations {
      operation {
        singleCharacter {
          'a'
        }
        false
      }
    }
  }
}
a|b =>regex {
  split {
    operations {
      operation {
        singleCharacter {
          'a'
        }
        false
      }
    }
    operations {
      operation {
        singleCharacter {
          'b'
        }
        false
      }
    }
  }
}
a(bc) => regex {
  split {
    operations {
      operation {
        singleCharacter {
          'a'
        }
        false
      }
      operation {
        group {
          split {
            operations {
              operation {
                singleCharacter {
                  'b'
                }
                false
              }
              operation {
                singleCharacter {
                  'c'
                }
                false
              }
            }
          }
        }
        false
      }
    }
  }
}
a+b*c? => regex {
  split {
    operations {
      operation {
        singleCharacter {
          'a'
        }
        suffixOperator {
          '+'
        }
      }
      operation {
        singleCharacter {
          'b'
        }
        suffixOperator {
          '*'
        }
      }
      operation {
        singleCharacter {
          'c'
        }
        suffixOperator {
          '?'
        }
      }
    }
  }
}