Recursive / circular rules leads to an infinite loop

[lovenunu]

Hello, It seems that when a rule is recursive or have a circular dependecy with other rules, the parser goes to an infinite loop. During the execution of Hoa\Compiler\Llk\Parser::unfold, instead of decreasing, Hoa\Compiler\Llk\Parser::_todo keeps growing, so the while loop never stops.

I have this behavior with hoa/compiler 3.17.08.08 Example to reproduce:

<?php
use Hoa\Compiler\Llk\Llk;
use Hoa\Compiler\Visitor\Dump;
use Hoa\File\ReadWrite;

$file = new ReadWrite('php://temp');
$file->writeString(<<<PP
%skip whitespace \s
%token and &&
%token integer \d+
%token foo_ \(
%token _foo \)

rule:
    _rule() | ::foo_:: _rule() ::_foo::  
_rule:
    (::integer:: | rule()) ::and:: (::integer:: | rule())
PP
);

$ast = Llk::load($file)->parse(<<<CODE
1 && (2 && 3) && 4
CODE
);

echo (new Dump())->visit($ast);

[Hywan]

Hello :-),

Indeed, it is a LL parser, so the grammar must not be left-recursive. You should rewrite your grammar to avoid such recursions.

Hint: https://en.wikipedia.org/wiki/Left_recursion.

[lovenunu]

Thanks for the hint :-) Shouldn't the parser throw an exception when such recursive grammar is loaded, to let the user know he did something wrong ?

[Hywan]

You should take a look at https://github.com/hoaproject/Compiler/issues/14.