1Marpa::XS::Rewrite(3) User Contributed Perl DocumentationMarpa::XS::Rewrite(3)
2
6 Marpa::XS::Rewrite - How Marpa rewrites grammars
7
9 Marpa rewrites grammars, adding internal symbols and rules in the
10 process. These rewritings do not affect the semantics, but they do
11 show up when you look at Marpa's grammars.
12 Marpa's internal symbols have tags at the end, enclosed in square
14 brackets. This means that all Marpa internal symbols end in a right
15 square bracket.
16 Marpa adds a new start rule
18 Many parsers add their own start rule and their own start symbol to
19 grammars. Marpa is no exception. The new internal start symbol is the
20 original start symbol with ""[']"" suffixed. An example of a Marpa
21 internal start symbol is ""Expression[']"". If the grammar allows a
22 null parse, there will also be a Marpa internal nulling start symbol,
23 with ""['][]"" suffixed. An example of a Marpa internal nulling start
24 symbol would be ""Script['][]"".
25 Marpa eliminates proper nullable symbols
27 A symbol is nulled if it produces the empty sentence. Nulling symbols
28 are those which are always nulled. Nullable symbols are those which
29 are sometimes nulled. Non-nullable symbols are those which are never
30 nulled.
31 All nulling symbols are also nullable symbols. A proper nullable is
33 any nullable symbol which is not a nulling symbol. In other words, a
34 proper nullable is a symbol that might or might not be nulled.
35 Nullable symbols were a problem in previous versions of Earley parsers.
37 Aycock and Horspool 2002 outlined a new approach for dealing with them.
38 I use their ideas with modifications of my own.
39 Marpa rewrites its grammar to eliminate proper nullables. It does this
41 by turning every proper nullable into two symbols: a non-nullable
42 variant and a nulling variant. The non-nullable variant keeps the
43 original symbol's name, but is no longer allowed to appear in places
44 where it might be nulled.
45 The name of the nulling variant is that of the original symbol with the
47 nulling tag (""[]"") suffixed. When the nulling variant is used, it
48 must be nulled.
49 The newly introduced nulling symbols will not appear on any left hand
51 sides, with one exception: grammars that allow a null parse will have a
52 nulling start rule. Except for the nulling start symbol, Marpa marks
53 nulling symbols internally and recognizes them directly, without the
54 need for empty rules.
55 Rules with proper nullables on the RHS have to be replaced with new
57 rules covering every possible combination of the non-nullable and
58 nulling variants. That rewrite is called the CHAF rewrite.
59 Marpa divides some rules up into smaller ones
61 Here's an example of a CHAF rewrite:
62 { lhs => 'statement',
64 rhs => [
65 qw/optional_whitespace expression
66 optional_whitespace optional_modifier
67 optional_whitespace/
68 ]
69 }
70 This rule contains four instances of proper nullables, illustrating my
72 fear that grammars of practical interest will have lots of proper
73 nullables on right hand sides. "optional_whitespace" and
74 "optional_modifier" are both proper nullables and "optional_whitespace"
75 appears three times.
76 Here's is the output from "show_rules", showing what Marpa does with
78 this rule:
79 0: statement -> optional_whitespace expression optional_whitespace optional_modifier optional_whitespace
81 /* !used */
82 15: statement -> optional_whitespace expression statement[R0:2] /* vrhs real=2 */
84 16: statement -> optional_whitespace expression optional_whitespace[] optional_modifier[] optional_whitespace[]
85 17: statement -> optional_whitespace[] expression statement[R0:2] /* vrhs real=2 */
86 18: statement -> optional_whitespace[] expression optional_whitespace[] optional_modifier[] optional_whitespace[]
87 19: statement[R0:2] -> optional_whitespace statement[R0:3] /* vlhs vrhs real=1 */
88 20: statement[R0:2] -> optional_whitespace optional_modifier[] optional_whitespace[] /* vlhs real=3 */
89 21: statement[R0:2] -> optional_whitespace[] statement[R0:3] /* vlhs vrhs real=1 */
90 22: statement[R0:3] -> optional_modifier optional_whitespace /* vlhs real=2 */
91 23: statement[R0:3] -> optional_modifier optional_whitespace[] /* vlhs real=2 */
92 24: statement[R0:3] -> optional_modifier[] optional_whitespace /* vlhs real=2 */
93 Rule 0 is the original rule. Because Marpa has rewritten it, the rule
95 is marked ""!used"", telling later stages in the precomputation to
96 ignore it. Marpa breaks Rule 0 up into three pieces, each with no more
97 than two proper nullables. Marpa then eliminates the proper nullables
98 in each piece by factoring.
99 To factor a piece, Marpa first rewrites it into multiple rules, one for
101 each possible combination of nulled and non-nulled symbols. Marpa then
102 replaces each proper nullable with its nulling or non-nullable variant,
103 as appropriate. There are two symbol variants for each proper
104 nullable. With a maximum of two proper nullables for each piece, each
105 with two variants, there are at most four combinations. A rule for one
106 of these combinations is called a factored rule, or a factor.
107 In the example in the above display, the original rule (Rule 0) was
109 broken into three pieces. Rule 0 had 5 RHS symbols, and the three
110 pieces contain, respectively, the first two RHS symbols; the third RHS
111 symbol; and the last two (that is, 4th and 5th) RHS symbols.
112 The first piece of Rule 0 is factored into four rules: Rules 15 to 18.
114 The second piece is factored into three rules: Rules 19 to 21. The
115 third and last piece of Rule 0 is also factored into three rules: Rules
116 22 to 24.
117 When a rule is broken into pieces, the left hand side of the first
119 piece is the left hand side of the original rule. New symbols are
120 introduced to be the left hand sides of the other pieces. The names of
121 the new LHS symbols are formed by suffixing a tag to the name of the
122 original left hand side. The suffixed tag begins with a capital "R"
123 and identifies the location of the piece in the original rule. For
124 example, the tag ""[R0:3]"" indicates that this symbol is the left hand
125 side for the piece of Rule 0 which begins at right hand symbol 3 (the
126 first symbol is symbol 0).
127 When a new LHS symbol is created for a piece, the worst case is that
129 the new LHS is also a proper nullable. This worst case occurs when all
130 the original symbols in the piece for the new LHS and all symbols in
131 all subsequent pieces are proper nullables.
132 A newly created LHS symbol will always appear on the RHS of the
134 previous piece. If the newly created symbol is a proper nullable, then
135 it counts against the limit of two proper nullables for that previous
136 piece, and it must be factored, just the same as if it was one of the
137 proper nullables appearing in the original rule.
138 Rule 0 is such a worst case. The last three symbols of the right hand
140 side are all proper nullables. That means that all the symbols in the
141 last two pieces of the original rule are proper nullables. Therefore
142 both of the newly created LHS symbols are proper nullables.
143 The original Rule 0 has 4 proper nullables. After the CHAF rewrite,
145 there are 6 proper nullables: the original 4 plus the 2 symbols newly
146 created to serve as left hand sides. This is why, in order to have at
147 most 2 proper nullables per piece, the original rule must to be divided
148 into 3 pieces.
149 CHAF preserves user semantics. Marpa, when it splits the rule into
151 pieces and factors the pieces, inserts logic to gather and preserve the
152 values of child nodes. The user's semantic actions see the original
153 child values as if the CHAF rewrite had never occurred.
154 Marpa converts sequence productions to BNF rules
156 Internally, Marpa converts productions specified as sequences into BNF
157 productions. The conversion is done in a standard way. For example,
158 {
160 lhs => 'statements',
161 rhs => [qw/statement/],
162 separator => 'comma',
163 min => 1
164 }
165 becomes
167 2: statements -> statements[Subseq:8:5] /* vrhs real=0 */
169 3: statements -> statements[Subseq:8:5] comma /* vrhs real=1 */
170 4: statements[Subseq:8:5] -> statement /* vlhs real=1 */
171 5: statements[Subseq:8:5] -> statements[Subseq:8:5] comma statement /* vlhs vrhs real=2 */
172 In the added symbol, the tag ""[Subseq:8:5]"" indicates a special
174 symbol introduced to serve as the LHS of the sequence. The ""8:5""
175 indentifies the sequence using the symbol ID's of the two symbols
176 involved. ""statements"", the LHS symbol, has symbol ID 8.
177 ""statement"", the RHS symbol, has symbol ID 5.
178 Here's another example, this time of a sequence without a separator.
180 The rule
181 { lhs => 'block', rhs => [qw/statements/], min => 0 },
183 is rewritten by Marpa as follows:
185 7: block -> /* empty !used */
187 8: block -> block[Subseq:0:8] /* vrhs real=0 */
188 9: block[Subseq:0:8] -> statements /* vlhs real=1 */
189 10: block[Subseq:0:8] -> block[Subseq:0:8] statements /* vlhs vrhs real=1 */
190 Note that rule 7, the empty rule with the "block" symbol as its LHS, is
192 marked ""!used"". "block" is a proper nullable, and rules from
193 sequence conversion undergo the same rewriting of proper nullables as
194 any other rules. In this case a nulling variant of "block" ("block[]")
195 was created. That made the empty rule created by the sequence
196 conversion useless, and that is why it was marked ""!used"".
197
199 Copyright 2012 Jeffrey Kegler
200 This file is part of Marpa::XS. Marpa::XS is free software: you can
201 redistribute it and/or modify it under the terms of the GNU Lesser
202 General Public License as published by the Free Software Foundation,
203 either version 3 of the License, or (at your option) any later version.
204 Marpa::XS is distributed in the hope that it will be useful,
206 but WITHOUT ANY WARRANTY; without even the implied warranty of
207 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
208 Lesser General Public License for more details.
209 You should have received a copy of the GNU Lesser
211 General Public License along with Marpa::XS. If not, see
212 http://www.gnu.org/licenses/.
213perl v5.32.0 2020-07-28 Marpa::XS::Rewrite(3)