Marpa::Advanced::Leo - Marpa Leo Implementation
This document is in progress. The most important parts of this document are not yet written.
This document describes Marpa's implementation of the algorithm in Leo 1991. The focus is on features useful for tracing and debugging grammars which have Leo items and Leo completions.
This document assumes that the reader knows the Marpa API, that she has a general knowledge of parsing, and that she is familiar with the document on basic Marpa implementation. and its prerequisites. All the examples in this document assume that none of the data has been stripped.
Below are the code and the trace outputs for the example used in this document.
my $grammar = Marpa::Grammar->new( { start => 'Statement', actions => 'My_Actions', default_action => 'first_arg', strip => 0, rules => [ { lhs => 'Statement', rhs => [qw/Expression/], action => 'do_Statement' }, { lhs => 'Expression', rhs => [qw/Lvalue AssignOp Expression/], action => 'do_Expression' }, { lhs => 'Expression', rhs => [qw/Lvalue AddAssignOp Expression/], action => 'do_Expression' }, { lhs => 'Expression', rhs => [qw/Lvalue MinusAssignOp Expression/], action => 'do_Expression' }, { lhs => 'Expression', rhs => [qw/Lvalue MultiplyAssignOp Expression/], action => 'do_Expression' }, { lhs => 'Expression', rhs => [qw/Variable/], action => 'do_Expression' }, { lhs => 'Lvalue', rhs => [qw/Variable/] }, ], } ); $grammar->precompute(); my $recce = Marpa::Recognizer->new( { grammar => $grammar } ); my @tokens = ( [ 'Variable', 'a' ], [ 'AssignOp', q{=} ], [ 'Variable', 'b' ], [ 'AddAssignOp', q{+=} ], [ 'Variable', 'c' ], [ 'MinusAssignOp', q{-=} ], [ 'Variable', 'd' ], [ 'MultiplyAssignOp', q{*=} ], [ 'Variable', 'e' ], ); $recce->tokens( \@tokens ); %My_Actions::VALUES = ( a => 711, b => 47, c => 1, d => 2, e => 3 ); sub My_Actions::do_Statement { return join q{ }, map { $_ . q{=} . $My_Actions::VALUES{$_} } sort keys %My_Actions::VALUES; } sub My_Actions::do_Expression { my ( undef, $lvariable, $op, $rvalue ) = @_; my $original_value = $My_Actions::VALUES{$lvariable}; return $original_value if not defined $rvalue; return $My_Actions::VALUES{$lvariable} = $op eq q{*=} ? ( $original_value * $rvalue ) : $op eq q{+=} ? ( $original_value + $rvalue ) : $op eq q{-=} ? ( $original_value - $rvalue ) : $rvalue } ## end sub My_Actions::do_Expression sub My_Actions::first_arg { return $_[1] }
show_symbols
0: Statement, lhs=[0] rhs=[7] terminal 1: Expression, lhs=[1 2 3 4 5] rhs=[0 1 2 3 4] terminal 2: Lvalue, lhs=[6] rhs=[1 2 3 4] terminal 3: AssignOp, lhs=[] rhs=[1] terminal 4: AddAssignOp, lhs=[] rhs=[2] terminal 5: MinusAssignOp, lhs=[] rhs=[3] terminal 6: MultiplyAssignOp, lhs=[] rhs=[4] terminal 7: Variable, lhs=[] rhs=[5 6] terminal 8: Statement['], lhs=[7] rhs=[]
show_rules
0: Statement -> Expression 1: Expression -> Lvalue AssignOp Expression 2: Expression -> Lvalue AddAssignOp Expression 3: Expression -> Lvalue MinusAssignOp Expression 4: Expression -> Lvalue MultiplyAssignOp Expression 5: Expression -> Variable 6: Lvalue -> Variable 7: Statement['] -> Statement /* vlhs real=1 */
show_AHFA
Start States: S0; S1 S0: 23 Statement['] -> . Statement <Statement> => S2; leo(Statement[']) S1: predict; 1,3,7,11,15,19,21 Statement -> . Expression Expression -> . Lvalue AssignOp Expression Expression -> . Lvalue AddAssignOp Expression Expression -> . Lvalue MinusAssignOp Expression Expression -> . Lvalue MultiplyAssignOp Expression Expression -> . Variable Lvalue -> . Variable <Expression> => S3; leo(Statement) <Lvalue> => S4 <Variable> => S5 S2: leo-c; 24 Statement['] -> Statement . S3: leo-c; 2 Statement -> Expression . S4: 4,8,12,16 Expression -> Lvalue . AssignOp Expression Expression -> Lvalue . AddAssignOp Expression Expression -> Lvalue . MinusAssignOp Expression Expression -> Lvalue . MultiplyAssignOp Expression <AddAssignOp> => S6; S7 <AssignOp> => S7; S8 <MinusAssignOp> => S7; S9 <MultiplyAssignOp> => S10; S7 S5: 20,22 Expression -> Variable . Lvalue -> Variable . S6: 9 Expression -> Lvalue AddAssignOp . Expression <Expression> => S11; leo(Expression) S7: predict; 3,7,11,15,19,21 Expression -> . Lvalue AssignOp Expression Expression -> . Lvalue AddAssignOp Expression Expression -> . Lvalue MinusAssignOp Expression Expression -> . Lvalue MultiplyAssignOp Expression Expression -> . Variable Lvalue -> . Variable <Lvalue> => S4 <Variable> => S5 S8: 5 Expression -> Lvalue AssignOp . Expression <Expression> => S12; leo(Expression) S9: 13 Expression -> Lvalue MinusAssignOp . Expression <Expression> => S13; leo(Expression) S10: 17 Expression -> Lvalue MultiplyAssignOp . Expression <Expression> => S14; leo(Expression) S11: leo-c; 10 Expression -> Lvalue AddAssignOp Expression . S12: leo-c; 6 Expression -> Lvalue AssignOp Expression . S13: leo-c; 14 Expression -> Lvalue MinusAssignOp Expression . S14: leo-c; 18 Expression -> Lvalue MultiplyAssignOp Expression .
show_earley_sets
Last Completed: 9; Furthest: 9 Earley Set 0 S0@0-0 S1@0-0 Earley Set 1 S5@0-1 [p=S1@0-0; s=Variable; t=\'a'] S3@0-1 [p=S1@0-0; c=S5@0-1] S4@0-1 [p=S1@0-0; c=S5@0-1] S2@0-1 [p=S0@0-0; c=S3@0-1] Earley Set 2 S8@0-2 [p=S4@0-1; s=AssignOp; t=\'='] S7@2-2 L12@0-2; actual="Expression"->12; [c=S8@0-2] Earley Set 3 S5@2-3 [p=S7@2-2; s=Variable; t=\'b'] S12@0-3 [l=L12@0-2; c=S5@2-3] S4@2-3 [p=S7@2-2; c=S5@2-3] S3@0-3 [p=S1@0-0; c=S12@0-3] S2@0-3 [p=S0@0-0; c=S3@0-3] Earley Set 4 S6@2-4 [p=S4@2-3; s=AddAssignOp; t=\'+='] S7@4-4 L12@0-4; actual="Expression"->11; [p=L12@0-2; c=S6@2-4] Earley Set 5 S5@4-5 [p=S7@4-4; s=Variable; t=\'c'] S12@0-5 [l=L12@0-4; c=S5@4-5] S4@4-5 [p=S7@4-4; c=S5@4-5] S3@0-5 [p=S1@0-0; c=S12@0-5] S2@0-5 [p=S0@0-0; c=S3@0-5] Earley Set 6 S9@4-6 [p=S4@4-5; s=MinusAssignOp; t=\'-='] S7@6-6 L12@0-6; actual="Expression"->13; [p=L12@0-4; c=S9@4-6] Earley Set 7 S5@6-7 [p=S7@6-6; s=Variable; t=\'d'] S12@0-7 [l=L12@0-6; c=S5@6-7] S4@6-7 [p=S7@6-6; c=S5@6-7] S3@0-7 [p=S1@0-0; c=S12@0-7] S2@0-7 [p=S0@0-0; c=S3@0-7] Earley Set 8 S10@6-8 [p=S4@6-7; s=MultiplyAssignOp; t=\'*='] S7@8-8 L12@0-8; actual="Expression"->14; [p=L12@0-6; c=S10@6-8] Earley Set 9 S5@8-9 [p=S7@8-8; s=Variable; t=\'e'] S12@0-9 [l=L12@0-8; c=S5@8-9] S4@8-9 [p=S7@8-8; c=S5@8-9] S3@0-9 [p=S1@0-0; c=S12@0-9] S2@0-9 [p=S0@0-0; c=S3@0-9]
Last Completed: 9; Furthest: 9 Earley Set 0 S0@0-0 S1@0-0 Earley Set 1 S5@0-1 [p=S1@0-0; s=Variable; t=\'a'] S3@0-1 [p=S1@0-0; c=S5@0-1] S4@0-1 [p=S1@0-0; c=S5@0-1] S2@0-1 [p=S0@0-0; c=S3@0-1] Earley Set 2 S8@0-2 [p=S4@0-1; s=AssignOp; t=\'='] S7@2-2 L12@0-2; actual="Expression"->12; [c=S8@0-2] Earley Set 3 S5@2-3 [p=S7@2-2; s=Variable; t=\'b'] S12@0-3 [l=L12@0-2; c=S5@2-3] S4@2-3 [p=S7@2-2; c=S5@2-3] S3@0-3 [p=S1@0-0; c=S12@0-3] S2@0-3 [p=S0@0-0; c=S3@0-3] Earley Set 4 S6@2-4 [p=S4@2-3; s=AddAssignOp; t=\'+='] S7@4-4 L12@0-4; actual="Expression"->11; [p=L12@0-2; c=S6@2-4] Earley Set 5 S5@4-5 [p=S7@4-4; s=Variable; t=\'c'] S12@0-5 [l=L12@0-4; c=S5@4-5] S4@4-5 [p=S7@4-4; c=S5@4-5] S3@0-5 [p=S1@0-0; c=S12@0-5] S2@0-5 [p=S0@0-0; c=S3@0-5] Earley Set 6 S9@4-6 [p=S4@4-5; s=MinusAssignOp; t=\'-='] S7@6-6 L12@0-6; actual="Expression"->13; [p=L12@0-4; c=S9@4-6] Earley Set 7 S5@6-7 [p=S7@6-6; s=Variable; t=\'d'] S12@0-7 [l=L12@0-6; c=S5@6-7] S4@6-7 [p=S7@6-6; c=S5@6-7] S3@0-7 [p=S1@0-0; c=S12@0-7] S2@0-7 [p=S0@0-0; c=S3@0-7] Earley Set 8 S10@6-8 [p=S4@6-7; s=MultiplyAssignOp; t=\'*='] S7@8-8 L12@0-8; actual="Expression"->14; [p=L12@0-6; c=S10@6-8] Earley Set 9 S5@8-9 [p=S7@8-8; s=Variable; t=\'e'] S12@0-9 [p=S8@0-2; c=S11@2-9] S4@8-9 [p=S7@8-8; c=S5@8-9] S3@0-9 [p=S1@0-0; c=S12@0-9] S2@0-9 [p=S0@0-0; c=S3@0-9] S14@6-9 [p=S10@6-8; c=S5@8-9] S13@4-9 [p=S9@4-6; c=S14@6-9] S11@2-9 [p=S6@2-4; c=S13@4-9]
trace_values
Pushed value from a18 T@0-1_Variable: Variable = \'a' Popping 1 values to evaluate a18 T@0-1_Variable, rule: 6: Lvalue -> Variable Calculated and pushed value: 'a' Pushed value from a16 R1:1@0-1T@1-2_AssignOp: AssignOp = \'=' Pushed value from a15 T@2-3_Variable: Variable = \'b' Popping 1 values to evaluate a15 T@2-3_Variable, rule: 6: Lvalue -> Variable Calculated and pushed value: 'b' Pushed value from a13 R2:1@2-3T@3-4_AddAssignOp: AddAssignOp = \'+=' Pushed value from a12 T@4-5_Variable: Variable = \'c' Popping 1 values to evaluate a12 T@4-5_Variable, rule: 6: Lvalue -> Variable Calculated and pushed value: 'c' Pushed value from a10 R3:1@4-5T@5-6_MinusAssignOp: MinusAssignOp = \'-=' Pushed value from a9 T@6-7_Variable: Variable = \'d' Popping 1 values to evaluate a9 T@6-7_Variable, rule: 6: Lvalue -> Variable Calculated and pushed value: 'd' Pushed value from a7 R4:1@6-7T@7-8_MultiplyAssignOp: MultiplyAssignOp = \'*=' Pushed value from a6 T@8-9_Variable: Variable = \'e' Popping 1 values to evaluate a6 T@8-9_Variable, rule: 5: Expression -> Variable Calculated and pushed value: 3 Popping 3 values to evaluate a5 R4:2@6-8F5@8-9, rule: 4: Expression -> Lvalue MultiplyAssignOp Expression Calculated and pushed value: 6 Popping 3 values to evaluate a4 R3:2@4-6F4@6-9, rule: 3: Expression -> Lvalue MinusAssignOp Expression Calculated and pushed value: -5 Popping 3 values to evaluate a3 R2:2@2-4F3@4-9, rule: 2: Expression -> Lvalue AddAssignOp Expression Calculated and pushed value: 42 Popping 3 values to evaluate a2 R1:2@0-2F2@2-9, rule: 1: Expression -> Lvalue AssignOp Expression Calculated and pushed value: 42 Popping 1 values to evaluate a1 F1@0-9, rule: 0: Statement -> Expression Calculated and pushed value: 'a=42 b=42 c=-5 d=6 e=3' New Virtual Rule: a0 F0@0-9, rule: 7: Statement['] -> Statement Symbol count is 1, now 1 rules
Copyright 2007-2010 Jeffrey Kegler, all rights reserved. Marpa is free software under the Perl license. For details see the LICENSE file in the Marpa distribution.
To install Marpa, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Marpa
CPAN shell
perl -MCPAN -e shell install Marpa
For more information on module installation, please visit the detailed CPAN module installation guide.