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.)

/a/の場合:
    0| char 'a'
    1| match
 
/abc/の場合:
    0| char 'a'
    1| char 'b'
    2| char 'c'
    3| match
 
/(ab|cd)/の場合:
    0| split 1, 4
    1| char 'a'
    2| char 'b'
    3| jmp 6
    4| char 'c'
    5| char 'd'
    6| match
 
/(ab)*/の場合:
    0| split 1 4
    1| char 'a'
    2| char 'b'
    3| jmp 0
    4| match
 
/a+/の場合:
    0| char 'a'
    1| split 0 2
    2| match
 
/ab?c/の場合: 
    0| char 'a'
    1| split 2 3
    2| char 'b'
    3| char 'c'
    2| match

<?php
class RegexVMThread
{
    public $stringPointer = 0, $programCounter = 0;
}
class RegexVMInstruction
{
    const CHAR = 0;
    const MATCH = 1;
    const JUMP = 2;
    const SPLIT = 3;
    public $type, $param;
    function __construct($instructionType, $param = null)
    {
        $this->type = $instructionType;
        $this->param = $param;
    }
}
class RegexVM
{
    static function run($string, array $instructions)
    {
        $threads = array();
        $thread = new RegexVMThread;
        for (;;) {
            // 現在の命令を取り出す
            $instruction = $instructions[$thread->programCounter];
            if (!$instruction) {
                throw new Exception();
            }
            switch (true) {
                
                case $instruction->type === RegexVMInstruction::CHAR:
                    $char = substr($string, $thread->stringPointer, 1);
                    // マッチする場合
                    if ($char === $instruction->param) {
                        $thread->stringPointer++;
                        $thread->programCounter++;
                    } else {
                        if ($threads) {
                            // スレッドがまだある場合には、
                            // 現在のスレッドを捨ててそのスレッドに切り替える
                            $thread = array_shift($threads);
                        } else {
                            // スレッドがもうない場合には、失敗する
                            return false;
                        }
                    }
                    break;
                case $instruction->type === RegexVMInstruction::SPLIT:
                    // スレッドを分割する
                    $newThread = clone($thread);
                    $newThread->programCounter = $instruction->param;
                    array_unshift($threads, $newThread);
                    $thread->programCounter++;
                    break;
                case $instruction->type === RegexVMInstruction::MATCH:
                    // マッチする
                    return true;
                case $instruction->type === RegexVMInstruction::JUMP:
                    // 特定の命令に飛ぶ
                    $thread->programCounter = $instruction->param;
                    break;
            }
        }
        
    }
}

<?php
include_once __DIR__ . '/../src/PHPRegex.php';
# /a/という正規表現を表現
$instructions = array(
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'a'),
    new RegexVMInstruction(RegexVMInstruction::MATCH)
);
var_dump(RegexVM::run('a', $instructions)); // => true
var_dump(RegexVM::run('b', $instructions)); // => false
# /abc/という正規表現を表現
$instructions = array(
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'a'),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'b'),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'c'),
    new RegexVMInstruction(RegexVMInstruction::MATCH)
);
var_dump(RegexVM::run('abc', $instructions)); // => true
var_dump(RegexVM::run('bc', $instructions));  // => false
# /(ab)|(cd)/という正規表現を表現する命令列
$instructions = array(
    new RegexVMInstruction(RegexVMInstruction::SPLIT, 4),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'a'),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'b'),
    new RegexVMInstruction(RegexVMInstruction::JUMP, 6),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'c'),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'd'),
    new RegexVMInstruction(RegexVMInstruction::MATCH)
);
var_dump(RegexVM::run('ab', $instructions)); // => true
var_dump(RegexVM::run('cd', $instructions)); // => true
var_dump(RegexVM::run('bc', $instructions)); // => false
# /a?/という正規表現を表現する命令列
$instructions = array(
    new RegexVMInstruction(RegexVMInstruction::SPLIT, 2),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'a'),
    new RegexVMInstruction(RegexVMInstruction::MATCH)
);
var_dump(RegexVM::run('', $instructions));  // => true
var_dump(RegexVM::run('a', $instructions)); // => true
# /(ab)*/という正規表現を表現する命令列
$instructions = array(
    new RegexVMInstruction(RegexVMInstruction::SPLIT, 4),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'a'),
    new RegexVMInstruction(RegexVMInstruction::CHAR, 'b'),
    new RegexVMInstruction(RegexVMInstruction::JUMP, 0),
    new RegexVMInstruction(RegexVMInstruction::MATCH)
);
var_dump(RegexVM::run('ab', $instructions));     // => true
var_dump(RegexVM::run('abab', $instructions));   // => true
var_dump(RegexVM::run('ababab', $instructions)); // => true 
var_dump(RegexVM::run('', $instructions));       // => true