Page MenuHomePhabricator
Diviner libphutil Tech Docs PhutilParserGenerator

final class PhutilParserGenerator
libphutil Technical Documentation (Parsers)

Simple LR(1) parser generator. Generally, build a parser by setting terminals and rules, then calling 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 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.

Tasks

Grammar Rules

No methods for this task.

Rule Validation

Computing First()

No methods for this task.

Computing Action and Goto Tables

No methods for this task.

Inspecting Generator State

Other Methods

Methods

public function processGrammar()

This method is not documented.
Return
wild

public function setTerminals($terminals)

This method is not documented.
Parameters
array$terminals
Return
wild

public function setRules($rules)

This method is not documented.
Parameters
array$rules
Return
wild

public function setStartRule($rule_name)

This method is not documented.
Parameters
$rule_name
Return
wild

public function getStartRule()

This method is not documented.
Return
wild

public function getEOFSymbol()

This method is not documented.
Return
wild

public function getInitSymbol()

This method is not documented.
Return
wild

public function getEpsilonSymbol()

This method is not documented.
Return
wild

public function getEndSymbol()

This method is not documented.
Return
wild

public function isTerminal($symbol)

This method is not documented.
Parameters
$symbol
Return
wild

public function isRule($symbol)

This method is not documented.
Parameters
$symbol
Return
wild

private function validateRules()

Perform a battery of tests on the provided rules to detect problems which would prevent us from generating a parser.

Return
void

private function parseRules()

This method is not documented.
Return
wild

private function validateRuleSymbols()

This method is not documented.
Return
wild

private function validateStartRule()

This method is not documented.
Return
wild

private function chooseSpecialSymbols()

This method is not documented.
Return
wild
This method is not documented.
Return
wild

private function validateAllRulesReachable()

This method is not documented.
Return
wild

private function computeReachableRules($rule, &$stack)

This method is not documented.
Parameters
$rule
array&$stack
Return
wild

private function validateAllRulesReducible()

This method is not documented.
Return
wild

private function isRuleReducible($rule, &$reducible)

This method is not documented.
Parameters
$rule
array&$reducible
Return
wild

private function computeRuleReducible($rule, &$reducible)

This method is not documented.
Parameters
$rule
array&$reducible
Return
wild

private function buildFirstTable()

This method is not documented.
Return
wild

private function buildRuleFirst($rule)

This method is not documented.
Parameters
$rule
Return
wild

private function getFirstForProduction($production)

This method is not documented.
Parameters
array$production
Return
wild

private function addState($set)

This method is not documented.
Parameters
array$set
Return
wild

private function buildSuccessors($start_state)

This method is not documented.
Parameters
$start_state
Return
wild

private function hashSet($set)

This method is not documented.
Parameters
array$set
Return
wild

private function buildTables()

This method is not documented.
Return
wild

public function generateParserFunction($name)

This method is not documented.
Parameters
$name
Return
wild

private function formatAndIndent($var, $depth)

This method is not documented.
Parameters
$var
$depth
Return
wild

public function parseTokens($tokens, $callback)

This method is not documented.
Parameters
array$tokens
$callback
Return
wild

public static function parseTokensWithTables($action_table, $goto_table, $eof_symbol, $tokens, $callback)

This method is not documented.
Parameters
$action_table
$goto_table
$eof_symbol
array$tokens
$callback
Return
wild

public function inspectRules()

This method is not documented.
Return
wild

public function inspectFirstTable()

This method is not documented.
Return
wild