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

Question

(Примечание: я читал другие вопросы, такие как this, но я не смог это понять).

Я написал эту грамматику:

start = call 

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

call = f:ident spaces g:(call/ident) { 
    return f + "(" + g + ")"; 
} 

С этим входом

a b c d 

возвращает

"a(b(c(d)))" 

И я хочу

"a(b)(c)(d)" 

Я думаю, что это левое рекурсивное правило может дать мне что-то подобное, но PEG.js не поддерживает левую рекурсию.

call = f:(call/ident) spaces g:ident { 
    return f + "(" + g + ")"; 
} 

Как устранить левую рекурсию в этом случае?

PS: Вы можете проверить это на online PEG.js demo

Answer 1

Хороший вопрос. Начните с отделения вашего первого 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 
} 

---

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

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)" для обоих сценариев.

Answer 2

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

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

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

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

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' ]. Я просто использовал + вместо рекурсии, а затем пробежал результирующий массив, построив нужную нам структуру. В Википедии есть замечания по выполнению left recursion with a PEG.

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

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

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

Чтобы поместить пробелы и обратно multicharacter ID, вы можете сделать это:

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} 

Answer 3

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

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 + ")"; }