Анализ с помощью Happy: left-recursion and right-recursion

Question

Section 2.2 of the Happy user manual советует вам использовать левую рекурсию, а не рекурсию справа, потому что правильная рекурсия «неэффективна». В основном они говорят, что если вы попытаетесь проанализировать длинную последовательность элементов, правильная рекурсия переполнит стеки синтаксического анализа, в то время как в левой рекурсии используется постоянный стек. Приведенный канонический пример:

items : item   { $1 : [] } 
     | items "," item { $3 : $1 } 

К сожалению, это означает, что список предметов возвращается назад.

Теперь достаточно легко применить reverse в конце (хотя раздражающе раздражает то, что вам нужно сделать, это везде анализатор называется, а не один раз, когда он определен). Однако, если список предметов велик, то reverseтакже собирается переполнить стек Haskell? Нет?

В принципе, как это сделать, чтобы я мог разбирать произвольно большие файлы и все еще получать результаты в правильном порядке?

Answer 1

Если все, что вы хотите, это все items быть reverse d каждый раз, вы можете определить

items : items_   {reverse $1} 

items_ : item    { $1 : [] } 
     | items_ "," item { $3 : $1 } 

reverse не произойдет переполнение стека. Если вам нужно убедиться в этом, попробуйте оценить length $ reverse [1..10000000]