<?php
$rules = [
[0, '(', '_', 0, ['_', 'x']],
[0, '(', 'x', 0, ['x', 'x']],
[0, ')', 'x', 0, []],
[0, 'EOF', '_', 1, []],
];
$state = 0;
$accept_states = [1];
$init_stack = '_';
$input = '(((()))())';
$tokens = array_merge(
str_split($input),
['EOF']
);
function match(array $rules, $state, $token, $top) {
foreach ($rules as $rule) {
list($init_state, $match_input, $match_stack, $new_state, $push_stack) = $rule;
if ($state === $init_state
&& $token === $match_input
&& $top === $match_stack) {
return $rule;
}
}
$token = var_export($token, true);
throw new \RuntimeException("No rule found for state $state, token $token");
}
$stack = new \SplStack();
$stack->push($init_stack);
foreach ($tokens as $token) {
$top = $stack->pop();
$rule = match($rules, $state, $token, $top);
list($init_state, $match_input, $match_stack, $new_state, $push_stack) = $rule;
$state = $new_state;
foreach ($push_stack as $push_token) {
$stack->push($push_token);
}
}
if (!in_array($state, $accept_states)) {
throw new \RuntimeException("Reached EOF but ended in state $state which is not an accept state.");
}
echo "The provided input has been accepted by accept state $state\n";
echo sprintf("Stack: %s\n", json_encode(iterator_to_array($stack)));
preferences:
48.41 ms | 402 KiB | 5 Q