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