Eliminate Left Recursion on this PEG.js grammar

grammar, parsing, peg, pegjs

Solution

Good question. Start by separating your first `ident` from everything else, since it gets special treatment (no parentheses). Next, defer to a rule to handle the `spaces ident` recursion that will collect the values that go inside parentheses. The loop wraps the `ident` text and appends any new text that is collected recursively.

Here is a short-hand version of the rules (note that `tail` is a separate rule):

head: ident tail?;        //the "head" ident is separated
tail: spaces ident tail?; //each "tail" ident is looped over

Here is the PEG script:

start = head

ident = [a-z]+
spaces = [ ]+

head = head:ident tail:tail? {
    return head + tail;
}

tail = spaces next:ident tail:tail? {
    return "(" + next + ")" + tail
}

Edit: Here is an alternative that does the work in one rule and is more similar to yours.

start = head

ident = [a-z]+
spaces = [ ]+

head = head:ident tail:(spaces next:ident{return "(" + next + ")" })* {
    return head + tail.join("")
}

The output for `a b c d` is `"a(b)(c)(d)"` for both scripts.

Problem

(Note: I've read other questions like this, but I haven't been able to figure this out). I wrote this grammar: ``` start = call ident = [a-z]+ spaces = [ ]+ call = f:ident spaces g:(call / ident) { return f + "(" + g + ")"; } ``` With this input ``` a b c d ``` it returns ``` "a(b(c(d)))" ``` And I want ``` "a(b)(c)(d)" ``` I think this left recursive rule can give me something like that, but PEG.js doesn't support left recursion. ``` call = f:(call / ident) spaces g:ident { return f + "(" + g + ")"; } ``` How can I eliminate the left recursion in this case? PS: You can test this on the online PEG.js demo

Original source