NAME

Marpa::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::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` 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` 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; [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]

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

Pushed value from a19 T@0-1_Variable: Variable = \'a'
Popping 1 values to evaluate a19 T@0-1_Variable, rule: 6: Lvalue -> Variable
Calculated and pushed value: 'a'
Pushed value from a17 R1:1@0-1T@1-2_AssignOp: AssignOp = \'='
Pushed value from a16 T@2-3_Variable: Variable = \'b'
Popping 1 values to evaluate a16 T@2-3_Variable, rule: 6: Lvalue -> Variable
Calculated and pushed value: 'b'
Pushed value from a14 R2:1@2-3T@3-4_AddAssignOp: AddAssignOp = \'+='
Pushed value from a13 T@4-5_Variable: Variable = \'c'
Popping 1 values to evaluate a13 T@4-5_Variable, rule: 6: Lvalue -> Variable
Calculated and pushed value: 'c'
Pushed value from a11 R3:1@4-5T@5-6_MinusAssignOp: MinusAssignOp = \'-='
Pushed value from a10 T@6-7_Variable: Variable = \'d'
Popping 1 values to evaluate a10 T@6-7_Variable, rule: 6: Lvalue -> Variable
Calculated and pushed value: 'd'
Pushed value from a8 R4:1@6-7T@7-8_MultiplyAssignOp: MultiplyAssignOp = \'*='
Pushed value from a7 T@8-9_Variable: Variable = \'e'
Popping 1 values to evaluate a7 T@8-9_Variable, rule: 5: Expression -> Variable
Calculated and pushed value: 3
Popping 3 values to evaluate a6 R4:2@6-8F5@8-9, rule: 4: Expression -> Lvalue MultiplyAssignOp Expression
Calculated and pushed value: 6
Popping 3 values to evaluate a5 R3:2@4-6F4@6-9, rule: 3: Expression -> Lvalue MinusAssignOp Expression
Calculated and pushed value: -5
Popping 3 values to evaluate a4 R2:2@2-4F3@4-9, rule: 2: Expression -> Lvalue AddAssignOp Expression
Calculated and pushed value: 42
Popping 3 values to evaluate a3 R1:2@0-2F2@2-9, rule: 1: Expression -> Lvalue AssignOp Expression
Calculated and pushed value: 42
Popping 1 values to evaluate a2 F1@0-9, rule: 0: Statement -> Expression
Calculated and pushed value: 'a=42 b=42 c=-5 d=6 e=3'
New Virtual Rule: F0@0-9, rule: 7: Statement['] -> Statement
Symbol count is 1, now 1 rules
New Virtual Rule: F7@0-9, rule: 7: Statement['] -> Statement
Symbol count is 1, now 2 rules

LICENSE AND COPYRIGHT

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.

	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 Output

show_earley_sets Output

trace_values Output

LICENSE AND COPYRIGHT

Module Install Instructions

`show_symbols` Output

`show_rules` Output

`show_AHFA` Output

`show_earley_sets` Output

`show_earley_sets` Output

`trace_values` Output