NAME

Marpa::XS::Advanced::Leo - Marpa Leo Implementation

THIS DOCUMENT IS IN PROGRESS

This document is in progress. The most important parts of this document are not yet written.

OVERVIEW

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.

APPENDIX: THE EXAMPLE

Below are the code and the trace outputs for the example used in this document.

Code for the example

my $grammar = Marpa::XS::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::XS::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` Output

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` Output

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` Output

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` "Before" Output

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; [l=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; [l=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; [l=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]

`show_earley_sets` "After" Output

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; [l=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; [l=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; [l=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` Output

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 AND LICENSE

Copyright 2010 Jeffrey Kegler
This file is part of Marpa::XS.  Marpa::XS is free software: you can
redistribute it and/or modify it under the terms of the GNU Lesser
General Public License as published by the Free Software Foundation,
either version 3 of the License, or (at your option) any later version.

Marpa::XS is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser
General Public License along with Marpa::XS.  If not, see
http://www.gnu.org/licenses/.

To install Marpa::XS, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Marpa::XS

CPAN shell

perl -MCPAN -e shell
install Marpa::XS

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

THIS DOCUMENT IS IN PROGRESS

OVERVIEW

APPENDIX: THE EXAMPLE

Code for the example

show_symbols Output

show_rules Output

show_AHFA Output

show_earley_sets "Before" Output

show_earley_sets "After" Output

trace_values Output