<?php
/**
* Simple LR(1) parser generator. Generally, build a parser by setting terminals
* and rules, then calling @{method:processGrammar}. For example, here is a
* simple grammar which accepts one or more "a" followed by exactly one "b":
*
* $parser = id(new PhutilParserGenerator())
* ->setTerminals(array('a', 'b'))
* ->setStartRule('S')
* ->setRules(
* array(
* 'S' => 'A b',
* 'A' => array(
* 'A a',
* 'a',
* )))
* ->processGrammar();
*
* To actually parse token streams, use @{method:parseTokens}.
*
* $tokens = get_tokens(); // Usually from PhutilLexer
* $callback = 'some_callback';
* $tree = $parser->parseTokens($tokens, $callback);
*
* The callback is invoked when a grammar rule matches. It should have this
* signature:
*
* function parser_callback($rule, $production, array $tokens) {
* // ...
* }
*
* The `$rule` is the matching rule; the `$production` is the matching
* production, and `$tokens` is the matching tokens (for terminal rules) or the
* return value of previous parse callbacks (for nonterminal rules).
*
* You should either return a result of evaluation, or some sort of abstract
* representation of the parse tree (this is more likely to be useful for more
* complex grammars).
*
* NOTE: This class generates LR(1) parsers, which perform less-than-optimally
* on large grammars. Worse, it is written in PHP. It is suitable only for
* very simple grammars with few states.
*
* NOTE: These parsers silently resolve reduce/reduce conflicts by choosing the
* first reduction, and silently resolve shift/reduce conflicts by shifting.
* These are the same rules used by Yacc, but are implicit.
*
* @task rules Grammar Rules
* @task rvalidation Rule Validation
* @task first Computing First()
* @task tables Computing Action and Goto Tables
* @task inspect Inspecting Generator State
*/
final class PhutilParserGenerator extends Phobject {
private $terminals;
private $rules;
private $startRule = 'start';
private $states = array();
private $sets = array();
private $successor = array();
private $setHashes = array();
private $actionTable;
private $gotoTable;
private $rulesValidated = false;
private $eofSymbol;
private $initSymbol;
private $epsilonSymbol;
private $endSymbol;
private $firstTable;
public function processGrammar() {
$this->validateRules();
$this->buildFirstTable();
$init = $this->getInitSymbol();
$eof = $this->getEOFSymbol();
$end = $this->getEndSymbol();
$this->rules[$init] = array(
array($this->startRule, $end),
);
list($is_new, $state) = $this->addState(
array(
array($this->getInitSymbol(), 0, 0, $eof),
));
$this->buildSuccessors($state);
$this->buildTables();
return $this;
}
/* -( Grammar Rules )------------------------------------------------------ */
public function setTerminals(array $terminals) {
$this->terminals = array_fill_keys($terminals, true);
return $this;
}
public function setRules(array $rules) {
$this->rules = $rules;
return $this;
}
public function setStartRule($rule_name) {
$this->startRule = $rule_name;
return $this;
}
public function getStartRule() {
return $this->startRule;
}
public function getEOFSymbol() {
if ($this->eofSymbol === null) {
throw new PhutilInvalidStateException('processGrammar');
}
return $this->eofSymbol;
}
public function getInitSymbol() {
if ($this->initSymbol === null) {
throw new PhutilInvalidStateException('processGrammar');
}
return $this->initSymbol;
}
public function getEpsilonSymbol() {
if ($this->epsilonSymbol === null) {
throw new PhutilInvalidStateException('processGrammar');
}
return $this->epsilonSymbol;
}
public function getEndSymbol() {
if ($this->endSymbol === null) {
throw new PhutilInvalidStateException('processGrammar');
}
return $this->endSymbol;
}
public function isTerminal($symbol) {
return isset($this->terminals[$symbol]);
}
public function isRule($symbol) {
return isset($this->rules[$symbol]);
}
/* -( Rule Validation )---------------------------------------------------- */
/**
* Perform a battery of tests on the provided rules to detect problems which
* would prevent us from generating a parser.
*
* @return void
* @task rvalidation
*/
private function validateRules() {
// Rules must be specified in the right format.
$this->parseRules();
// Rules must contain only known symbols.
$this->validateRuleSymbols();
// The start rule must exist and be valid.
$this->validateStartRule();
// Now, we select printable names for special symbols (EOF, epsilon, etc)
// that don't conflict with any symbols in the grammar.
$this->chooseSpecialSymbols();
// Make sure every terminal can be reached by some rule.
$this->validateAllTerminalsReachable();
// Make sure every rule can be reached.
$this->validateAllRulesReachable();
// Make sure every rule has some valid reduction.
$this->validateAllRulesReducible();
$this->rulesValidated = true;
}
/**
* @task rvalidation
*/
private function parseRules() {
foreach ($this->rules as $rule_name => $rule_variants) {
if (!is_array($rule_variants)) {
$rule_variants = array($rule_variants);
$this->rules[$rule_name] = $rule_variants;
}
foreach ($rule_variants as $vkey => $variant) {
if ($variant === null) {
$variant = array(null);
} else if (!is_array($variant)) {
$variant = preg_split('/\s+/', $variant);
} else {
foreach ($variant as $symbol) {
if (($symbol === null) && count($variant) > 1) {
throw new PhutilInvalidRuleParserGeneratorException(
pht(
"Rule '%s' contains a production '%s' which is ".
"nonempty but has a null in it. A rule with other ".
"may not contain null.",
$rule_name,
$vkey));
}
}
}
$this->rules[$rule_name][$vkey] = array_values($variant);
}
}
}
/**
* @task rvalidation
*/
private function validateRuleSymbols() {
foreach ($this->rules as $rule => $productions) {
foreach ($productions as $production_name => $production) {
foreach ($production as $symbol) {
if ($symbol === null) {
continue;
}
if ($this->isTerminal($symbol)) {
continue;
}
if ($this->isRule($symbol)) {
continue;
}
$production_string = implode(' ', $production);
throw new PhutilUnknownSymbolParserGeneratorException(
pht(
"Symbol '%s' in production '%s' ('%s') of rule '%s' does not ".
"name a rule or terminal. Did you misspell a symbol, fail to ".
"specify a terminal, or forget a rule?",
$symbol,
$production_name,
$production_string,
$rule));
}
}
}
}
/**
* @task rvalidation
*/
private function validateStartRule() {
$start_rule = $this->getStartRule();
if (!$this->isRule($start_rule)) {
throw new PhutilUnknownSymbolParserGeneratorException(
pht(
"Start rule '%s' does not appear in the rules for the grammar. Use ".
"%s to choose a different start rule, or add a rule named '%s'.",
$start_rule,
'setStartRule()',
$start_rule));
}
}
/**
* @task rvalidation
*/
private function chooseSpecialSymbols() {
$special = array(
'eofSymbol' => '(end-of-file)',
'epsilonSymbol' => '(epsilon)',
'initSymbol' => '(init)',
'endSymbol' => '(end)',
);
foreach ($special as $key => $value) {
while ($this->isRule($value) || $this->isTerminal($value)) {
$value .= "'";
}
$special[$key] = $value;
}
$this->eofSymbol = $special['eofSymbol'];
$this->epsilonSymbol = $special['epsilonSymbol'];
$this->initSymbol = $special['initSymbol'];
$this->endSymbol = $special['endSymbol'];
foreach ($this->rules as $rule => $productions) {
foreach ($productions as $production_name => $production) {
foreach ($production as $key => $symbol) {
if ($symbol === null) {
$this->rules[$rule][$production_name][$key] = $this->epsilonSymbol;
}
}
$this->rules[$rule][$production_name][] = $this->endSymbol;
}
}
$this->terminals[$this->getEOFSymbol()] = true;
}
/**
* @task rvalidation
*/
private function validateAllTerminalsReachable() {
$seen = array();
foreach ($this->rules as $rule => $productions) {
foreach ($productions as $production) {
foreach ($production as $symbol) {
$seen[$symbol] = true;
}
}
}
$missing = array_diff_key($this->terminals, $seen);
unset($missing[$this->getEOFSymbol()]);
if ($missing) {
$missing_terminals = array_keys($missing);
$missing_terminals = implode(', ', $missing_terminals);
throw new PhutilUnreachableTerminalParserGeneratorException(
pht(
'Some terminals do not appear in any rule: %s',
$missing_terminals));
}
}
/**
* @task rvalidation
*/
private function validateAllRulesReachable() {
$stack = array();
$reachable = $this->computeReachableRules($this->getStartRule(), $stack);
$missing = array_diff_key($this->rules, $reachable);
unset($missing[$this->getStartRule()]);
if ($missing) {
$missing_rules = array_keys($missing);
$missing_rules = implode(', ', $missing_rules);
throw new PhutilUnreachableRuleParserGeneratorException(
pht(
'Some rules can never be reached from any production: %s',
$missing_rules));
}
}
/**
* @task rvalidation
*/
private function computeReachableRules($rule, array &$stack) {
if (isset($stack[$rule])) {
return $stack[$rule];
}
$stack[$rule] = array();
foreach ($this->rules[$rule] as $production) {
foreach ($production as $symbol) {
if ($this->isRule($symbol)) {
$stack[$rule][$symbol] = true;
$stack[$rule] += $this->computeReachableRules($symbol, $stack);
}
}
}
return $stack[$rule];
}
/**
* @task rvalidation
*/
private function validateAllRulesReducible() {
$reducible = array();
foreach ($this->rules as $rule => $productions) {
if (!$this->isRuleReducible($rule, $reducible)) {
throw new PhutilIrreducibleRuleParserGeneratorException(
pht(
"Rule '%s' can never be reduced: it recurses indefinitely ".
"and reaches no production of terminals.",
$rule));
}
}
}
/**
* @task rvalidation
*/
private function isRuleReducible($rule, array &$reducible) {
if (isset($reducible[$rule])) {
return $reducible[$rule];
}
// Set this ahead of time so we don't end up in an infinite loop if
// rules recurse. We'll overwrite it if we find a reduction.
$reducible[$rule] = false;
$reducible[$rule] = $this->computeRuleReducible($rule, $reducible);
return $reducible[$rule];
}
/**
* @task rvalidation
*/
private function computeRuleReducible($rule, array &$reducible) {
$epsilon = $this->getEpsilonSymbol();
$end = $this->getEndSymbol();
$productions = $this->rules[$rule];
// In the first pass, try to find a trivially reducible production, e.g. one
// with epsilon or only terminals. Also, remove recursive productions (those
// which directly involve the rule itself) because we know we won't be able
// to reduce them. If we're lucky, this will allow us to determine that the
// rule is reducible without recursion. For example, we can immediately
// reduce these productions:
//
// R -> a
// R -> b c d
// R -> (epsilon)
//
// We can never reduce these productions:
//
// R -> R
// R -> a R b
//
// We might be able to reduce these productions, but they aren't as cheap
// or easy to figure out, since we need to first determine if other rules
// can be reduced:
//
// R -> X Y
// R -> X a
//
// If we find a reduction, we return immediately.
foreach ($productions as $key => $production) {
$has_only_terminals = true;
foreach ($production as $symbol) {
if ($symbol == $end) {
break;
} else if ($symbol == $epsilon) {
// The rule contains an epsilon production, which can always reduce
// it.
return true;
} else if ($symbol == $rule) {
// The rule contains itself; this production is never reducible. We
// must find another reducible production.
unset($productions[$key]);
continue 2;
} else if ($this->isTerminal($symbol)) {
// This is a terminal; keep looking. We'll be able to reduce the
// production if it contains only terminals.
continue;
} else {
// This is a rule, so we can't trivially reduce it. We'll keep it
// for the next round if we can't find any trivial reductions.
$has_only_terminals = false;
break;
}
}
if ($has_only_terminals) {
return true;
}
}
// If we have no productions left, this rule can't be reduced.
if (empty($productions)) {
return false;
}
// We have remaining productions which include other rules. Look for a
// nontrivial reduction. For example:
//
// R -> X Y
// X -> x
// Y -> y
//
// In this case, X and Y are both reducible, so "X Y" is reducible and thus
// R is reducible.
foreach ($productions as $production) {
$can_reduce = true;
foreach ($production as $symbol) {
// NOTE: We don't need to check for epsilon here, because we would
// already have determined the rule was reducible if we had an epsilon
// production.
if ($symbol == $end) {
break;
} else if ($this->isTerminal($symbol)) {
continue;
} else if (!$this->isRuleReducible($symbol, $reducible)) {
$can_reduce = false;
break;
}
}
if ($can_reduce) {
// The production contained only terminals and reducible rules, so it
// is reducible. We're good and don't need to examine remaining
// productions.
return true;
}
}
// We didn't find any reducible productions.
return false;
}
/* -( Computing First() )-------------------------------------------------- */
private function buildFirstTable() {
$this->firstTable = array();
foreach ($this->rules as $rule => $productions) {
$this->buildRuleFirst($rule);
}
}
private function buildRuleFirst($rule) {
if (isset($this->firstTable[$rule])) {
return $this->firstTable[$rule];
}
$this->firstTable[$rule] = array();
$productions = $this->rules[$rule];
foreach ($productions as $key => $production) {
$this->firstTable[$rule] += $this->getFirstForProduction($production);
}
return $this->firstTable[$rule];
}
private function getFirstForProduction(array $production) {
$set = array();
$end = $this->getEndSymbol();
$epsilon = $this->getEpsilonSymbol();
$eof = $this->getEOFSymbol();
$accept_epsilon = true;
foreach ($production as $symbol) {
if ($symbol === $end) {
break;
} else if ($symbol === $epsilon) {
break;
} else if ($this->isTerminal($symbol)) {
$set[$symbol] = true;
$accept_epsilon = false;
break;
} else {
$symbol_set = $this->buildRuleFirst($symbol);
$has_epsilon = isset($symbol_set[$epsilon]);
unset($symbol_set[$epsilon]);
$set += $symbol_set;
if (!$has_epsilon) {
$accept_epsilon = false;
break;
}
}
}
if ($accept_epsilon) {
$set[$epsilon] = true;
}
return $set;
}
/* -( Computing States )--------------------------------------------------- */
private function addState(array $set) {
$seen = array();
foreach ($set as $item) {
$seen[$item[0]][$item[1]][$item[2]][$item[3]] = true;
}
$end = $this->getEndSymbol();
$epsilon = $this->getEpsilonSymbol();
for ($ii = 0; $ii < count($set); $ii++) {
$item = $set[$ii];
$production = $this->rules[$item[0]][$item[1]];
$next = $production[$item[2]];
if ($this->isTerminal($next)) {
continue;
} else if ($next === $epsilon) {
continue;
} else if ($next === $end) {
continue;
}
$v = array_slice($production, $item[2] + 1, -1);
$v[] = $item[3];
$v[] = $end;
$firsts = $this->getFirstForProduction($v);
foreach ($firsts as $nfirst => $ignored) {
if (!$this->isTerminal($nfirst)) {
unset($firsts[$nfirst]);
}
}
foreach ($this->rules[$next] as $pkey => $nproduction) {
foreach ($firsts as $nfirst => $ignored) {
if (isset($seen[$next][$pkey][0][$nfirst])) {
continue;
}
$set[] = array($next, $pkey, 0, $nfirst);
$seen[$next][$pkey][0][$nfirst] = true;
}
}
}
$hash = $this->hashSet($set);
if (isset($this->setHashes[$hash])) {
return array(false, $this->setHashes[$hash]);
}
$this->states[] = $set;
$state = last_key($this->states);
$this->setHashes[$hash] = $state;
return array(true, $state);
}
private function buildSuccessors($start_state) {
$end = $this->getEndSymbol();
$nexts = array();
foreach ($this->states[$start_state] as $item) {
$next = $this->rules[$item[0]][$item[1]][$item[2]];
if ($next === $end) {
continue;
}
$nexts[$next][] = array(
$item[0],
$item[1],
$item[2] + 1,
$item[3],
);
}
foreach ($nexts as $next => $items) {
list($is_new, $state) = $this->addState($items);
$this->successor[$start_state][$next] = $state;
if ($is_new) {
$this->buildSuccessors($state);
}
}
}
private function hashSet(array $set) {
foreach ($set as $k => $item) {
$set[$k] = implode("\0", $item);
}
sort($set);
$set = implode("\1", $set);
return md5($set);
}
private function buildTables() {
$action = array();
$goto = array();
$end = $this->getEndSymbol();
$eof = $this->getEOFSymbol();
$init = $this->getInitSymbol();
foreach ($this->states as $state => $items) {
$shift = array();
$reduce = array();
$accept = false;
foreach ($items as $item) {
$next = $this->rules[$item[0]][$item[1]][$item[2]];
if ($next == $end) {
if ($item[0] !== $init) {
$reduce[$item[3]][] = $item;
} else if ($item[0] === $init && $item[3] === $eof) {
$accept = $item;
}
} else if ($this->isTerminal($next)) {
$shift[$next] = $item;
} else {
$goto[$state][$next] = $this->successor[$state][$next];
}
}
foreach ($reduce as $next => $reductions) {
if (count($reductions) > 1) {
$ways = array();
foreach ($reductions as $reduction) {
$ways[] = "{$reduction[0]}/{$reduction[1]}";
}
$ways = implode('; ', $ways);
// TODO: As below, we should have more explicit handling of
// reduce/reduce conflicts. For now, just pick the first one.
if (false) {
throw new Exception(
pht(
"Reduce/reduce conflict: from state '%s', when a ".
"'%s' is encountered, it may be reduced in multiple ".
"ways: %s",
$state,
$next,
$ways));
}
}
$reduce[$next] = head($reductions);
}
$srconflicts = array_intersect_key($shift, $reduce);
foreach ($srconflicts as $next => $ignored) {
// TODO: We should probably have better or more explicit handling of
// shift/reduce conflicts. For now, we just shift.
if (false) {
$what = $reduce[$next][0];
throw new Exception(
pht(
"Shift/reduce conflict: from state '%s', when a '%s' ".
"is encountered, shifting conflicts with reducing '%s'.",
$state,
$next,
$what));
} else {
// Resolve the shift/reduce by shifting.
$reduce = array();
}
}
if ($accept && isset($shift[$eof])) {
throw new Exception(pht('Accept/shift conflict!'));
}
if ($accept && isset($reduce[$eof])) {
throw new Exception(pht('Accept/reduce conflict!'));
}
foreach ($reduce as $next => $item) {
$action[$state][$next] = array(
'R',
array(
$item[0],
$item[1],
count($this->rules[$item[0]][$item[1]]) - 1,
),
);
}
foreach ($shift as $next => $item) {
$action[$state][$next] = array(
'S',
$this->successor[$state][$next],
);
}
if ($accept) {
$action[$state][$eof] = array('A');
}
}
$this->actionTable = $action;
$this->gotoTable = $goto;
}
public function generateParserFunction($name) {
$out = array();
$out[] = 'function '.$name.'(array $tokens, $callback) {';
$out[] = ' return '.__CLASS__.'::parseTokensWithTables(';
$out[] = ' '.$this->formatAndIndent($this->actionTable, 4).',';
$out[] = ' '.$this->formatAndIndent($this->gotoTable, 4).',';
$out[] = ' '.$this->formatAndIndent($this->getEOFSymbol(), 4).',';
$out[] = ' $tokens,';
$out[] = ' $callback);';
$out[] = '}';
return implode("\n", $out);
}
private function formatAndIndent($var, $depth) {
$var = phutil_var_export($var);
$var = str_replace("\n", "\n".str_repeat(' ', $depth), $var);
return $var;
}
public function parseTokens(array $tokens, $callback) {
return self::parseTokensWithTables(
$this->actionTable,
$this->gotoTable,
$this->getEOFSymbol(),
$tokens,
$callback);
}
public static function parseTokensWithTables(
$action_table,
$goto_table,
$eof_symbol,
array $tokens,
$callback) {
$state_stack = array(0);
$token_stack = array();
$tokens = array_reverse($tokens);
while (true) {
$state = end($state_stack);
if (empty($tokens)) {
$next = $eof_symbol;
} else {
$next_token = end($tokens);
$next = $next_token[0];
}
if (!isset($action_table[$state][$next])) {
$expected = implode(', ', array_keys($action_table[$state]));
throw new Exception(
pht(
"Unexpected '%s' in state %s! Expected: %s",
$next,
$state,
$expected));
}
$action = $action_table[$state][$next];
switch ($action[0]) {
case 'S':
$state_stack[] = $action[1];
$token_stack[] = array_pop($tokens);
break;
case 'R':
$r_rule = $action[1][0];
$r_prod = $action[1][1];
$r_size = $action[1][2];
$token_v = array();
while ($r_size--) {
$token_v[] = array_pop($token_stack);
array_pop($state_stack);
}
$token_v = array_reverse($token_v);
$token_stack[] = call_user_func_array(
$callback,
array($r_rule, $r_prod, $token_v));
$goto = $goto_table[end($state_stack)][$r_rule];
$state_stack[] = $goto;
break;
case 'A':
break 2;
}
}
return head($token_stack);
}
/* -( Inspecting Generator State )----------------------------------------- */
/**
* @task inspect
*/
public function inspectRules() {
if (!$this->rulesValidated) {
throw new PhutilInvalidStateException('processGrammar');
}
return $this->rules;
}
/**
* @task inspect
*/
public function inspectFirstTable() {
if ($this->firstTable === null) {
throw new PhutilInvalidStateException('processGrammar');
}
return $this->firstTable;
}
}