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

Implement indirect left-recursion #95

Open
phorward opened this issue Dec 25, 2022 · 1 comment
Open

Implement indirect left-recursion #95

phorward opened this issue Dec 25, 2022 · 1 comment
Labels
bug Something isn't working feature New feature or request help wanted Extra attention is needed

Comments

@phorward
Copy link
Member

For indirect left-recursion in packrat parsing, one rule in the grammar's graph must be declared as "leading", so that subsequent, even left-recursive parselets are considered as not left-recursive.

An implementation of an solution for this issue can be found in the pegen parser generator from Python.

Tokay currently cannot handle this issue properly, and fails to parse abbcb with the grammar

X: Y 'c'
Y: Z 'b'
Z: X | Y | 'a'
Z

only the a is parsed.

@phorward phorward added bug Something isn't working feature New feature or request help wanted Extra attention is needed tokay labels Dec 25, 2022
@phorward phorward pinned this issue Oct 5, 2023
@phorward
Copy link
Member Author

phorward commented Oct 5, 2023

During #105, this problem becomes more present, as the new Opt/Pos/Kle-concept introduces more parselets which might introduce indirect left-recursions.

As provided in tests/parselet_leftrec.tok

# direct
D1: @{
    D1 Char<b>
    Char<a>
}
'D1' print(D1)

# indirect 1: currently not working, see issue #95 for details
I1: @{
    I1? Char<a>
}
'I1' print(I1)

# indirect 2: currently not working, see issue #95 for details
X: Y 'c'
Y: Z 'b'
Z: X | Y | 'a'
'I2' print(Z)

#---
#D1abbb
#I1aaaa
#I2abbcb
#---
#((("a", "b"), "b"), "b")
#a
#a

I1 and I2 do not work as expected, as they introduce indirect left-recursions. I1 can be resolved by #120, but this does not solve the problem directly. Maybe, a refactor of the meaning behind Op::ForwardIfConsumed is also a way to resolve this problem, or parts of it, more precisely.

@phorward phorward removed the tokay label Oct 8, 2023
@phorward phorward unpinned this issue May 23, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working feature New feature or request help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

1 participant