Как бороться с Treetop левой рекурсии - PullRequest
Новая
       27

Как бороться с Treetop левой рекурсии

6 голосов
/ 25 мая 2011

У меня есть файл грамматики для нового языка программирования общего назначения, который я пытаюсь создать.Я пытаюсь сделать язык устойчивым и естественным для использования (он в значительной степени вдохновлен Ruby, и при этом я ввел некоторые леворекурсивные правила.

Я видел несколько примеровкоторые, кажется, указывают на следующее леворекурсивное правило: 

rule l_recurse
  l_recurse / 'something else'
end

можно сделать нерекурсивным, изменив его на: 

rule r_recurse
  'something else' / r_recurse
end

Для меня это выглядит так, как если быдругая проблема и все равно не получится.Я прав или это «просто сработает»?

Конкретные левые рекурсии, которые я пытаюсь (найти и) устранить, находятся в этом файле грамматики .Я не уверен, какие правила затрагиваются, но, по крайней мере, некоторые из них указали на левую рекурсию.(Кстати, я пытался устранить конкретную проблему диапазона, которую он упомянул, ужесточив правило диапазона.)

1 Ответ

4 голосов
/ 25 мая 2011

Особый случай 

rule l_recurse
  l_recurse / 'something else'
end

упрощается до 

rule l_recurse
   'something_else'
end

(как и правильное правило рекурсии), поэтому мне нужно увидеть ваш конкретный пример, чтобы узнать, что вы хотите знать Ответ на на этот вопрос дает общее правило устранения левой рекурсии.

Одним из типичных легко удаляемых левых случаев рекурсии являются списки: 

rule l_list
    item | l_list ',' item
end

и это можно изменить на правильную рекурсию 

rule r_list
    item r_tail?
end

rule r_tail
    ',' r_list
end

(что является частным случаем исключения общей рекурсии).

...