Skip to content

Having trouble understanding "Left recurrsion" #786

Answered by zacryol
Thesecondbestname asked this question in Q&A
Discussion options

You must be logged in to vote

Smaller example:

S = { (S ~ "+") | "a" }

On paper, this grammar appears to be able to parse "a" followed by any number of "+"; but with PEG rules, that can't actually happen.

PEGs are eager and top down. When a rule is encountered, pest will try to match that rule entirely before going forward. With the above grammar, when you try to parse an S from some input, pest will try to complete an inner S first, but to parse that S, it will need to parse an S first, but to parse that S, it will need to parse an S first.

No input gets consumed before you end up with trying to parse the same rule, therefore no progress can be made.

"Left recursion" means that a right hand option can start with the…

Replies: 1 comment 1 reply

Comment options

You must be logged in to vote
1 reply
@Thesecondbestname
Comment options

Answer selected by tomtau
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Category
Q&A
Labels
None yet
2 participants