sqlite-database-integration / wp-includes / database / parser / class-wp-parser-grammar.php

class-wp-parser-grammar.php in SQLite Database Integration 3.0.2, at wp-includes/database/parser/class-wp-parser-grammar.php

143 lines 5.1 KB

Raw Download Zip

1	<?php
2
3	/**
4	* A parser grammar.
5	*
6	* This class represents a parser grammar that can be consumed by WP_Parser.
7	* It loads a compressed grammar from a PHP array, inflates it to an internal
8	* representation, and precomputes a lookup table for quick branch selection.
9	*
10	* @TODO: Add more details about the grammar implementation.
11	*
12	* @access private
13	*/
14	class WP_Parser_Grammar {
15	/**
16	* ID for a special grammar rule that represents an empty "ε" (epsilon) rule.
17	*
18	* An "ε" rule in a grammar is a rule that matches an empty input of 0 bytes.
19	* It can be used to represent optional grammar productions, and it is helpful
20	* for expanding 0-or-1, 0-or-more, and 1-or-more quantifiers into simple rules.
21	*
22	* @TODO Investigate whether we can prevent possible conflict with a token ID.
23	* The MySQL grammar doesn't define a token with ID "0", but generally
24	* token IDs are not guaranteed to always satisfy this condition.
25	*/
26	const EMPTY_RULE_ID = 0;
27
28	/**
29	* @TODO: Review and document these properties and their visibility.
30	*/
31	public $rules;
32	public $rule_names;
33	public $fragment_ids;
34	public $lookahead_is_match_possible = array();
35	public $lowest_non_terminal_id;
36	public $highest_terminal_id;
37	public $native_grammar;
38
39	public function __construct( array $rules ) {
40	$this->inflate( $rules );
41	}
42
43	public function get_rule_name( $rule_id ) {
44	return $this->rule_names[ $rule_id ];
45	}
46
47	public function get_rule_id( $rule_name ) {
48	return array_search( $rule_name, $this->rule_names, true );
49	}
50
51	/**
52	* Inflate the grammar to an internal representation optimized for parsing.
53	*
54	* The input grammar is a compressed PHP array to minimize the file size.
55	* Every rule and token in the compressed grammar is encoded as an integer.
56	*/
57	private function inflate( $grammar ) {
58	$this->lowest_non_terminal_id = $grammar['rules_offset'];
59	$this->highest_terminal_id = $this->lowest_non_terminal_id - 1;
60
61	foreach ( $grammar['rules_names'] as $rule_index => $rule_name ) {
62	$this->rule_names[ $rule_index + $grammar['rules_offset'] ] = $rule_name;
63	$this->rules[ $rule_index + $grammar['rules_offset'] ] = array();
64
65	/**
66	* Treat all intermediate rules as fragments to inline before returning
67	* the final parse tree to the API consumer.
68	*
69	* The original grammar was too difficult to parse with rules like:
70	*
71	* query ::= EOF \| ((simpleStatement \| beginWork) ((SEMICOLON_SYMBOL EOF?) \| EOF))
72	*
73	* We've factored rule fragments, such as `EOF?`, into separate rules, such as `%EOF_zero_or_one`.
74	* This is super useful for parsing, but it limits the API consumer's ability to
75	* reason about the parse tree.
76	*
77	* Fragments are intermediate rules that are not part of the original grammar.
78	* They are prefixed with a "%" to be distinguished from the original rules.
79	*/
80	if ( '%' === $rule_name[0] ) {
81	$this->fragment_ids[ $rule_index + $grammar['rules_offset'] ] = true;
82	}
83	}
84
85	$this->rules = array();
86	foreach ( $grammar['grammar'] as $rule_index => $branches ) {
87	$rule_id = $rule_index + $grammar['rules_offset'];
88	$this->rules[ $rule_id ] = $branches;
89	}
90
91	/**
92	* Compute a rule => [token => true] lookup table for each rule
93	* that starts with a terminal OR with another rule that already
94	* has a lookahead mapping.
95	*
96	* This is similar to left-factoring the grammar, even if not quite
97	* the same.
98	*
99	* This enables us to quickly bail out from checking branches that
100	* cannot possibly match the current token. This increased the parser
101	* speed by a whopping 80%!
102	*
103	* @TODO: Explore these possible next steps:
104	*
105	* * Compute a rule => [token => branch[]] list lookup table and only
106	* process the branches that have a chance of matching the current token.
107	* * Actually left-factor the grammar as much as possible. This, however,
108	* could inflate the serialized grammar size.
109	*/
110	// 5 iterations seem to give us all the speed gains we can get from this.
111	for ( $i = 0; $i < 5; $i++ ) {
112	foreach ( $grammar['grammar'] as $rule_index => $branches ) {
113	$rule_id = $rule_index + $grammar['rules_offset'];
114	if ( isset( $this->lookahead_is_match_possible[ $rule_id ] ) ) {
115	continue;
116	}
117	$rule_lookup = array();
118	$first_symbol_can_be_expanded_to_all_terminals = true;
119	foreach ( $branches as $branch ) {
120	$terminals = false;
121	$branch_starts_with_terminal = $branch[0] < $this->lowest_non_terminal_id;
122	if ( $branch_starts_with_terminal ) {
123	$terminals = array( $branch[0] );
124	} elseif ( isset( $this->lookahead_is_match_possible[ $branch[0] ] ) ) {
125	$terminals = array_keys( $this->lookahead_is_match_possible[ $branch[0] ] );
126	}
127
128	if ( false === $terminals ) {
129	$first_symbol_can_be_expanded_to_all_terminals = false;
130	break;
131	}
132	foreach ( $terminals as $terminal ) {
133	$rule_lookup[ $terminal ] = true;
134	}
135	}
136	if ( $first_symbol_can_be_expanded_to_all_terminals ) {
137	$this->lookahead_is_match_possible[ $rule_id ] = $rule_lookup;
138	}
139	}
140	}
141	}
142	}
143