Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Left-recursion causes infinite loop #6484

Open
p6rt opened this issue Aug 31, 2017 · 3 comments
Open

Left-recursion causes infinite loop #6484

p6rt opened this issue Aug 31, 2017 · 3 comments
Labels
regex Regular expressions, pattern matching, user-defined grammars, tokens and rules

Comments

@p6rt
Copy link

p6rt commented Aug 31, 2017

Migrated from rt.perl.org#132004 (status was 'open')

Searchable as RT132004$

@p6rt
Copy link
Author

p6rt commented Aug 31, 2017

From @daxim

  â�º perl6 -v
  This is Rakudo version 2017.07 built on MoarVM version 2017.07
  implementing Perl 6.c.

  â�º cat flail.pl
  use v6;
  grammar Flail {
  rule TOP { <B> }
  rule B { <A> 'x' 'y' | <C> }
  rule A { '' | 'x' 'z' }
  rule C { <C> 'w' | 'v' }
  }
  Flail.parse('x z x y').say;
  Flail.parse('v w w w w w w').say;

  â�º perl6 flail.pl
  ï½¢x z x yï½£
  B => ï½¢x z x yï½£
  A => ï½¢x z ï½£
  ^C

The execution simply goes into infinite loop with the second input.
This is the least awesome failure mode.

Compare with Pegex and Regexp​::Grammars, which emit a recursion
warning/error. Compare with Antlr4, where the grammar is effectively a
compile time error. Compare with Eyapp and Marpa, which can consume
this grammar and set of inputs without any problem.

I realise that the parser cannot be simply changed since it also parses
Perl6 source code. But since it is now shown that the parser is not a
general parser able to consume arbitrary valid CFG, then at least the
documentation must mention somewhere

* what the name/classification of the underlying technology/algorithm
  of the parser is and
* what its shortcomings are (with examples)

so that a user can make an informed decision.

@p6rt
Copy link
Author

p6rt commented Aug 31, 2017

From @smls

Shorter example​:

  grammar Flail {
  token TOP { <TOP> 'w' | 'v' }
  }

  Flail.subparse('vwwwwww').say;

@p6rt
Copy link
Author

p6rt commented Aug 31, 2017

The RT System itself - Status changed from 'new' to 'open'

@p6rt p6rt added the regex Regular expressions, pattern matching, user-defined grammars, tokens and rules label Jan 5, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
regex Regular expressions, pattern matching, user-defined grammars, tokens and rules
Projects
None yet
Development

No branches or pull requests

1 participant