++ed by:
PERLANCAR DOUGDUDE AZAWAWI DRTECH

4 PAUSE users
1 non-PAUSE user.

Author image Jeffrey Kegler
and 1 contributors

NAME

Marpa::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::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 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

LICENSE AND COPYRIGHT

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.