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

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

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