Устранить левую рекурсию в этой грамматике PEG.js

Хороший вопрос. Начните с отделения вашего первого ident от всего остального, так как он получает специальную обработку (без круглых скобок). Затем обратитесь к правилу для обработки рекурсии spaces ident, которая будет собирать значения, заключенные в круглые скобки. Цикл оборачивает текст ident и добавляет любой новый текст, который собирается рекурсивно.

Вот сокращенная версия правил (обратите внимание, что tail — это отдельное правило):

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

Вот скрипт PEG:

start = head

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

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

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

Изменить. Вот альтернатива, которая выполняет работу в одном правиле и больше похожа на вашу.

start = head

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

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

Выход для a b c d равен "a(b)(c)(d)" для обоих сценариев.

Если я правильно понимаю, ваша проблема не в левой рекурсии, а в структуре дерева разбора.

Вы правильно устранили левую рекурсию, но, к сожалению, единственный способ избавиться от левой рекурсии — это устранить левую рекурсию в необработанном дереве синтаксического анализа. Большая часть теории для этого материала сводится к сопоставлению правильного набора строк. Вы по-прежнему сопоставляете один и тот же набор строк, так что теория хороша, но вам нужно леворекурсивное дерево синтаксического анализа. Подробнее об этой проблеме в Википедии.

Насколько я знаю, вы не можете сделать необработанный вывод парсера PEG леворекурсивным. Однако вы можете делать с выводом все, что хотите. Так что разберите его как массив, а затем постобработайте, чтобы придать ему красивую левую структуру.

Делаем это с упрощенной (без пробелов, без многосимвольных идентификаторов) грамматикой:

 start = call

 id = [a-z]

 call
     = arr:id+ {
         var acc = arr[0]
         for (i = 1; i < arr.length; i++) {
            acc = [acc, arr[i]]
         }
         return acc;
     }

Это анализирует abcd до [ [ [ 'a', 'b' ], 'c' ], 'd' ]. Я просто использовал + вместо рекурсии, а затем пробежался по результирующему массиву, создав нужную нам структуру. В Википедии есть несколько заметок о выполнении левой рекурсии с PEG.

Это предполагает, что вам нужна структура данных. Если вам нужны только скобки, замените действие следующим:

var acc = arr[0]
for (i = 1; i < arr.length; i++) {
    acc = acc + '(' + arr[i] + ')'
}
return acc;

Что дает a(b)(c)(d).

Чтобы вернуть пробелы и многосимвольные идентификаторы, вы можете сделать это:

 start = call

 id = [a-z]+

 _ = [ ]+

 call
      = a:id as:arg* {
          arr = [a].concat(as)
          var acc = arr[0]
          for (i = 1; i < arr.length; i++) {
              acc = acc + '(' + arr[i] + ')'
          }
          return acc;
      }

 arg = _ a:id {return a}

Вы можете переформулировать нетерминал call и поместить его повторяющуюся часть в отдельное правило с помощью оператора + следующим образом:

start = call

ident = i:[a-z]+ { return i.join(''); }
spaces = [ ]+

call = f:ident g:args+ {
    return f + g.join('');
}

args = spaces a:ident { return "(" + a + ")"; }