1=head1 NAME
2
3Marpa::Advanced::Leo - Marpa Leo Implementation
4
5=head1 THIS DOCUMENT IS IN PROGRESS
6
7This document is in progress.
8The most important parts of this document are not yet written.
9
10=head1 OVERVIEW
11
12This document describes
13Marpa's implementation of the algorithm
14in
15L<Leo 1991|Marpa::Advanced::Bibliography/"Leo 1991">.
16The focus is on
17features
18useful for tracing and debugging
19grammars which have
20Leo items and Leo completions.
21
22This document assumes that the reader
23knows
24the Marpa API,
25that she
26has a general knowledge of parsing,
27and that she is familiar with
28L<the document on basic Marpa
29implementation|Marpa::Advanced::Implementation>.
30and
31its prerequisites.
32All the examples
33in this document
34assume that none of the data has been stripped.
35
36=head1 APPENDIX: THE EXAMPLE
37
38Below are the code and the trace outputs
39for the example used in this
40document.
41
42=head2 Code for the example
43
44=for Marpa::Display:
45name: Leo Example
46perltidy: '-dcsc -sil=0'
47
48    my $grammar = Marpa::Grammar->new(
49        {   start          => 'Statement',
50            actions        => 'My_Actions',
51            default_action => 'first_arg',
52            strip          => 0,
53            rules          => [
54                {   lhs    => 'Statement',
55                    rhs    => [qw/Expression/],
56                    action => 'do_Statement'
57                },
58                {   lhs    => 'Expression',
59                    rhs    => [qw/Lvalue AssignOp Expression/],
60                    action => 'do_Expression'
61                },
62                {   lhs    => 'Expression',
63                    rhs    => [qw/Lvalue AddAssignOp Expression/],
64                    action => 'do_Expression'
65                },
66                {   lhs    => 'Expression',
67                    rhs    => [qw/Lvalue MinusAssignOp Expression/],
68                    action => 'do_Expression'
69                },
70                {   lhs    => 'Expression',
71                    rhs    => [qw/Lvalue MultiplyAssignOp Expression/],
72                    action => 'do_Expression'
73                },
74                {   lhs    => 'Expression',
75                    rhs    => [qw/Variable/],
76                    action => 'do_Expression'
77                },
78                { lhs => 'Lvalue', rhs => [qw/Variable/] },
79            ],
80        }
81    );
82
83    $grammar->precompute();
84
85    my $recce = Marpa::Recognizer->new( { grammar => $grammar } );
86
87    my @tokens = (
88        [ 'Variable',         'a' ],
89        [ 'AssignOp',         q{=} ],
90        [ 'Variable',         'b' ],
91        [ 'AddAssignOp',      q{+=} ],
92        [ 'Variable',         'c' ],
93        [ 'MinusAssignOp',    q{-=} ],
94        [ 'Variable',         'd' ],
95        [ 'MultiplyAssignOp', q{*=} ],
96        [ 'Variable',         'e' ],
97    );
98
99    $recce->tokens( \@tokens );
100
101    %My_Actions::VALUES = ( a => 711, b => 47, c => 1, d => 2, e => 3 );
102
103    sub My_Actions::do_Statement {
104        return join q{ }, map { $_ . q{=} . $My_Actions::VALUES{$_} }
105            sort keys %My_Actions::VALUES;
106    }
107
108    sub My_Actions::do_Expression {
109        my ( undef, $lvariable, $op, $rvalue ) = @_;
110        my $original_value = $My_Actions::VALUES{$lvariable};
111        return $original_value if not defined $rvalue;
112        return
113            $My_Actions::VALUES{$lvariable} =
114              $op eq q{*=} ? ( $original_value * $rvalue )
115            : $op eq q{+=} ? ( $original_value + $rvalue )
116            : $op eq q{-=} ? ( $original_value - $rvalue )
117            : $rvalue
118
119    } ## end sub My_Actions::do_Expression
120
121    sub My_Actions::first_arg { return $_[1] }
122
123
124=for Marpa::Display::End
125
126=head2 C<show_symbols> Output
127
128=for Marpa::Display
129name: Leo Example show_symbols Output
130remove-display-indent: 1
131remove-blank-last-line: 1
132
133    0: Statement, lhs=[0] rhs=[7] terminal
134    1: Expression, lhs=[1 2 3 4 5] rhs=[0 1 2 3 4] terminal
135    2: Lvalue, lhs=[6] rhs=[1 2 3 4] terminal
136    3: AssignOp, lhs=[] rhs=[1] terminal
137    4: AddAssignOp, lhs=[] rhs=[2] terminal
138    5: MinusAssignOp, lhs=[] rhs=[3] terminal
139    6: MultiplyAssignOp, lhs=[] rhs=[4] terminal
140    7: Variable, lhs=[] rhs=[5 6] terminal
141    8: Statement['], lhs=[7] rhs=[]
142
143=for Marpa::Display::End
144
145=head2 C<show_rules> Output
146
147=for Marpa::Display
148name: Leo Example show_rules Output
149remove-display-indent: 1
150remove-blank-last-line: 1
151
152    0: Statement -> Expression
153    1: Expression -> Lvalue AssignOp Expression
154    2: Expression -> Lvalue AddAssignOp Expression
155    3: Expression -> Lvalue MinusAssignOp Expression
156    4: Expression -> Lvalue MultiplyAssignOp Expression
157    5: Expression -> Variable
158    6: Lvalue -> Variable
159    7: Statement['] -> Statement /* vlhs real=1 */
160
161=for Marpa::Display::End
162
163=head2 C<show_AHFA> Output
164
165=for Marpa::Display:
166name: Leo Example show_AHFA Output
167remove-display-indent: 1
168remove-blank-last-line: 1
169
170    Start States: S0; S1
171    S0: 23
172    Statement['] -> . Statement
173     <Statement> => S2; leo(Statement['])
174    S1: predict; 1,3,7,11,15,19,21
175    Statement -> . Expression
176    Expression -> . Lvalue AssignOp Expression
177    Expression -> . Lvalue AddAssignOp Expression
178    Expression -> . Lvalue MinusAssignOp Expression
179    Expression -> . Lvalue MultiplyAssignOp Expression
180    Expression -> . Variable
181    Lvalue -> . Variable
182     <Expression> => S3; leo(Statement)
183     <Lvalue> => S4
184     <Variable> => S5
185    S2: leo-c; 24
186    Statement['] -> Statement .
187    S3: leo-c; 2
188    Statement -> Expression .
189    S4: 4,8,12,16
190    Expression -> Lvalue . AssignOp Expression
191    Expression -> Lvalue . AddAssignOp Expression
192    Expression -> Lvalue . MinusAssignOp Expression
193    Expression -> Lvalue . MultiplyAssignOp Expression
194     <AddAssignOp> => S6; S7
195     <AssignOp> => S7; S8
196     <MinusAssignOp> => S7; S9
197     <MultiplyAssignOp> => S10; S7
198    S5: 20,22
199    Expression -> Variable .
200    Lvalue -> Variable .
201    S6: 9
202    Expression -> Lvalue AddAssignOp . Expression
203     <Expression> => S11; leo(Expression)
204    S7: predict; 3,7,11,15,19,21
205    Expression -> . Lvalue AssignOp Expression
206    Expression -> . Lvalue AddAssignOp Expression
207    Expression -> . Lvalue MinusAssignOp Expression
208    Expression -> . Lvalue MultiplyAssignOp Expression
209    Expression -> . Variable
210    Lvalue -> . Variable
211     <Lvalue> => S4
212     <Variable> => S5
213    S8: 5
214    Expression -> Lvalue AssignOp . Expression
215     <Expression> => S12; leo(Expression)
216    S9: 13
217    Expression -> Lvalue MinusAssignOp . Expression
218     <Expression> => S13; leo(Expression)
219    S10: 17
220    Expression -> Lvalue MultiplyAssignOp . Expression
221     <Expression> => S14; leo(Expression)
222    S11: leo-c; 10
223    Expression -> Lvalue AddAssignOp Expression .
224    S12: leo-c; 6
225    Expression -> Lvalue AssignOp Expression .
226    S13: leo-c; 14
227    Expression -> Lvalue MinusAssignOp Expression .
228    S14: leo-c; 18
229    Expression -> Lvalue MultiplyAssignOp Expression .
230
231=for Marpa::Display::End
232
233=head2 C<show_earley_sets> "Before" Output
234
235=for Marpa::Display:
236name: Leo Example show_earley_sets "Before" Output
237remove-display-indent: 1
238remove-blank-last-line: 1
239
240    Last Completed: 9; Furthest: 9
241    Earley Set 0
242    S0@0-0
243    S1@0-0
244    Earley Set 1
245    S5@0-1 [p=S1@0-0; s=Variable; t=\'a']
246    S3@0-1 [p=S1@0-0; c=S5@0-1]
247    S4@0-1 [p=S1@0-0; c=S5@0-1]
248    S2@0-1 [p=S0@0-0; c=S3@0-1]
249    Earley Set 2
250    S8@0-2 [p=S4@0-1; s=AssignOp; t=\'=']
251    S7@2-2
252    L12@0-2; actual="Expression"->12; [c=S8@0-2]
253    Earley Set 3
254    S5@2-3 [p=S7@2-2; s=Variable; t=\'b']
255    S12@0-3 [l=L12@0-2; c=S5@2-3]
256    S4@2-3 [p=S7@2-2; c=S5@2-3]
257    S3@0-3 [p=S1@0-0; c=S12@0-3]
258    S2@0-3 [p=S0@0-0; c=S3@0-3]
259    Earley Set 4
260    S6@2-4 [p=S4@2-3; s=AddAssignOp; t=\'+=']
261    S7@4-4
262    L12@0-4; actual="Expression"->11; [p=L12@0-2; c=S6@2-4]
263    Earley Set 5
264    S5@4-5 [p=S7@4-4; s=Variable; t=\'c']
265    S12@0-5 [l=L12@0-4; c=S5@4-5]
266    S4@4-5 [p=S7@4-4; c=S5@4-5]
267    S3@0-5 [p=S1@0-0; c=S12@0-5]
268    S2@0-5 [p=S0@0-0; c=S3@0-5]
269    Earley Set 6
270    S9@4-6 [p=S4@4-5; s=MinusAssignOp; t=\'-=']
271    S7@6-6
272    L12@0-6; actual="Expression"->13; [p=L12@0-4; c=S9@4-6]
273    Earley Set 7
274    S5@6-7 [p=S7@6-6; s=Variable; t=\'d']
275    S12@0-7 [l=L12@0-6; c=S5@6-7]
276    S4@6-7 [p=S7@6-6; c=S5@6-7]
277    S3@0-7 [p=S1@0-0; c=S12@0-7]
278    S2@0-7 [p=S0@0-0; c=S3@0-7]
279    Earley Set 8
280    S10@6-8 [p=S4@6-7; s=MultiplyAssignOp; t=\'*=']
281    S7@8-8
282    L12@0-8; actual="Expression"->14; [p=L12@0-6; c=S10@6-8]
283    Earley Set 9
284    S5@8-9 [p=S7@8-8; s=Variable; t=\'e']
285    S12@0-9 [l=L12@0-8; c=S5@8-9]
286    S4@8-9 [p=S7@8-8; c=S5@8-9]
287    S3@0-9 [p=S1@0-0; c=S12@0-9]
288    S2@0-9 [p=S0@0-0; c=S3@0-9]
289
290=for Marpa::Display::End
291
292=head2 C<show_earley_sets> "After" Output
293
294=for Marpa::Display:
295name: Leo Example show_earley_sets "After" Output
296remove-display-indent: 1
297remove-blank-last-line: 1
298
299    Last Completed: 9; Furthest: 9
300    Earley Set 0
301    S0@0-0
302    S1@0-0
303    Earley Set 1
304    S5@0-1 [p=S1@0-0; s=Variable; t=\'a']
305    S3@0-1 [p=S1@0-0; c=S5@0-1]
306    S4@0-1 [p=S1@0-0; c=S5@0-1]
307    S2@0-1 [p=S0@0-0; c=S3@0-1]
308    Earley Set 2
309    S8@0-2 [p=S4@0-1; s=AssignOp; t=\'=']
310    S7@2-2
311    L12@0-2; actual="Expression"->12; [c=S8@0-2]
312    Earley Set 3
313    S5@2-3 [p=S7@2-2; s=Variable; t=\'b']
314    S12@0-3 [l=L12@0-2; c=S5@2-3]
315    S4@2-3 [p=S7@2-2; c=S5@2-3]
316    S3@0-3 [p=S1@0-0; c=S12@0-3]
317    S2@0-3 [p=S0@0-0; c=S3@0-3]
318    Earley Set 4
319    S6@2-4 [p=S4@2-3; s=AddAssignOp; t=\'+=']
320    S7@4-4
321    L12@0-4; actual="Expression"->11; [p=L12@0-2; c=S6@2-4]
322    Earley Set 5
323    S5@4-5 [p=S7@4-4; s=Variable; t=\'c']
324    S12@0-5 [l=L12@0-4; c=S5@4-5]
325    S4@4-5 [p=S7@4-4; c=S5@4-5]
326    S3@0-5 [p=S1@0-0; c=S12@0-5]
327    S2@0-5 [p=S0@0-0; c=S3@0-5]
328    Earley Set 6
329    S9@4-6 [p=S4@4-5; s=MinusAssignOp; t=\'-=']
330    S7@6-6
331    L12@0-6; actual="Expression"->13; [p=L12@0-4; c=S9@4-6]
332    Earley Set 7
333    S5@6-7 [p=S7@6-6; s=Variable; t=\'d']
334    S12@0-7 [l=L12@0-6; c=S5@6-7]
335    S4@6-7 [p=S7@6-6; c=S5@6-7]
336    S3@0-7 [p=S1@0-0; c=S12@0-7]
337    S2@0-7 [p=S0@0-0; c=S3@0-7]
338    Earley Set 8
339    S10@6-8 [p=S4@6-7; s=MultiplyAssignOp; t=\'*=']
340    S7@8-8
341    L12@0-8; actual="Expression"->14; [p=L12@0-6; c=S10@6-8]
342    Earley Set 9
343    S5@8-9 [p=S7@8-8; s=Variable; t=\'e']
344    S12@0-9 [p=S8@0-2; c=S11@2-9]
345    S4@8-9 [p=S7@8-8; c=S5@8-9]
346    S3@0-9 [p=S1@0-0; c=S12@0-9]
347    S2@0-9 [p=S0@0-0; c=S3@0-9]
348    S14@6-9 [p=S10@6-8; c=S5@8-9]
349    S13@4-9 [p=S9@4-6; c=S14@6-9]
350    S11@2-9 [p=S6@2-4; c=S13@4-9]
351
352=for Marpa::Display::End
353
354=head2 C<trace_values> Output
355
356=for Marpa::Display:
357name: Leo Example trace_values Output
358remove-display-indent: 1
359remove-blank-last-line: 1
360
361    Pushed value from a18 T@0-1_Variable: Variable = \'a'
362    Popping 1 values to evaluate a18 T@0-1_Variable, rule: 6: Lvalue -> Variable
363    Calculated and pushed value: 'a'
364    Pushed value from a16 R1:1@0-1T@1-2_AssignOp: AssignOp = \'='
365    Pushed value from a15 T@2-3_Variable: Variable = \'b'
366    Popping 1 values to evaluate a15 T@2-3_Variable, rule: 6: Lvalue -> Variable
367    Calculated and pushed value: 'b'
368    Pushed value from a13 R2:1@2-3T@3-4_AddAssignOp: AddAssignOp = \'+='
369    Pushed value from a12 T@4-5_Variable: Variable = \'c'
370    Popping 1 values to evaluate a12 T@4-5_Variable, rule: 6: Lvalue -> Variable
371    Calculated and pushed value: 'c'
372    Pushed value from a10 R3:1@4-5T@5-6_MinusAssignOp: MinusAssignOp = \'-='
373    Pushed value from a9 T@6-7_Variable: Variable = \'d'
374    Popping 1 values to evaluate a9 T@6-7_Variable, rule: 6: Lvalue -> Variable
375    Calculated and pushed value: 'd'
376    Pushed value from a7 R4:1@6-7T@7-8_MultiplyAssignOp: MultiplyAssignOp = \'*='
377    Pushed value from a6 T@8-9_Variable: Variable = \'e'
378    Popping 1 values to evaluate a6 T@8-9_Variable, rule: 5: Expression -> Variable
379    Calculated and pushed value: 3
380    Popping 3 values to evaluate a5 R4:2@6-8F5@8-9, rule: 4: Expression -> Lvalue MultiplyAssignOp Expression
381    Calculated and pushed value: 6
382    Popping 3 values to evaluate a4 R3:2@4-6F4@6-9, rule: 3: Expression -> Lvalue MinusAssignOp Expression
383    Calculated and pushed value: -5
384    Popping 3 values to evaluate a3 R2:2@2-4F3@4-9, rule: 2: Expression -> Lvalue AddAssignOp Expression
385    Calculated and pushed value: 42
386    Popping 3 values to evaluate a2 R1:2@0-2F2@2-9, rule: 1: Expression -> Lvalue AssignOp Expression
387    Calculated and pushed value: 42
388    Popping 1 values to evaluate a1 F1@0-9, rule: 0: Statement -> Expression
389    Calculated and pushed value: 'a=42 b=42 c=-5 d=6 e=3'
390    New Virtual Rule: a0 F0@0-9, rule: 7: Statement['] -> Statement
391    Symbol count is 1, now 1 rules
392
393=for Marpa::Display::End
394
395=head1 LICENSE AND COPYRIGHT
396
397Copyright 2007-2010 Jeffrey Kegler, all rights reserved.
398Marpa is free software under the Perl license.
399For details see the LICENSE file in the Marpa distribution.
400
401=cut
402
403# Local Variables:
404#   mode: cperl
405#   cperl-indent-level: 4
406#   fill-column: 100
407# End:
408# vim: expandtab shiftwidth=4:
409
410