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

PEG order does not apply when left&right options #115

Open
apalala opened this issue Apr 24, 2019 · 3 comments
Open

PEG order does not apply when left&right options #115

apalala opened this issue Apr 24, 2019 · 3 comments

Comments

@apalala
Copy link
Collaborator

apalala commented Apr 24, 2019

    def test_peg_associativity(self):
        left_grammar = '''
            @@left_recursion :: True
            @@nameguard :: False

            start = A $ ;
            A = | A 'a' | 'a' A | 'a' ;
        '''

        assert [['a', 'a'], 'a'] == parse(left_grammar, 'aaa')  # warning: fails

        right_grammar = '''
            @@left_recursion :: True
            @@nameguard :: False

            start = A $ ;
            A = | 'a' A | A 'a' | 'a' ;
        '''

        assert ['a', ['a', 'a']] == parse(right_grammar, 'aaa')
@Victorious3
Copy link
Collaborator

I'm not sure if this one can be fixed with the current algorithm. It doesn't support rules that are only left recursive some of them time, everything with @leftrec on it will go through the bounded left recursion step

@Victorious3
Copy link
Collaborator

Victorious3 commented Apr 24, 2019

Okay, what I think I have to do to fix this is flagging concrete invocations of rules as left recursive instead of assuming that the whole rule is left recursive all the time.
This is how the parser currently sees the second case:

@nomemo (don't memoize this rule)
@leftrec (don't memoize this rule, use bounded left recursion)

start = A $ ;
A = | 'a' A | A 'a' | 'a' ;

But this is is what should happen:

start = A $;
A = | 'a' A | A 'a' | 'a' ;

It already gathers the information necessary to do this but I'd have to figure out how to transfer it to the generated parser as well.

EDIT: I wrongly assumed that the second case is failing when it's always right recursion that wins.

@Victorious3
Copy link
Collaborator

I'll start working on this once the frequency of edits goes down a bit ^^

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants