Лучший способ построить списки матчей в парсера генератора

Question

(я использую Yecc, синтаксический анализатор генератор Erlang, похожий на Yacc, так что синтаксис отличается от Yacc)

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

В Erlang, [1,3,4] есть список, а ++ объединяет два списка.

Мы хотим совместить это 1 (1+2) 3. expression будет соответствовать 1, (1 + 2) и 3. Итак, я сопоставляюсь в списке, за которым следует еще одно выражение, и если нет совпадения, я заканчиваю, чтобы соответствовать одному выражению. Это строит список рекурсивно.

expressionlist -> expressionlist expression : '$1' ++ ['$2']. 
expressionlist -> expression : ['$1']. 

Но я могу сделать это тоже (инвертировать порядок):

expressionlist -> expression expressionlist : ['$1'] ++ '$2'. 
expressionlist -> expression : ['$1']. 

Оба theese похоже на работу, я хотел бы знать, существует ли какая-то разница.

с сепаратором

Я хочу, чтобы соответствовать {name = albert , age = 43}. propdef соответствует name = value. Таким образом, это та же проблема, но с дополнительным разделителем ,. Есть ли разница в первой проблеме?

proplist -> propdef ',' proplist : ['$1'] ++ '$3'. 
proplist -> propdef : ['$1']. 
proplist -> '{' proplist '}' : '$2'. 
proplist -> '{' '}' : []. 

%% Could write this 
%% proplist -> proplist ',' propdef : '$1' ++ ['$3']. 

спасибо.

Answer 1

Поскольку Yecc является генератором парсера LALR, использование левой рекурсии или правильной рекурсии не имеет большого значения. В старые времена люди предпочли бы оставить рекурсию в Yacc/Bison и аналогичные инструменты, потому что это позволяет парсеру продолжать уменьшать, а не переносить все на стек до конца списка, но в наши дни пространство стека и скорость не та, что важно, чтобы вы могли выбрать все, что вам больше подходит. (Обратите внимание, что в LL-парсере левая рекурсия вызывает бесконечный цикл, поэтому для таких парсеров необходима правильная рекурсия.)

Более важным для вашего примера выше является то, что '$ 1' ++ ['$ 2 '] в левой рекурсивной версии вызовет квадратичную временную сложность, так как часть «listlist» - это та, которая будет длиннее и длиннее. У вас никогда не должно быть растущего компонента слева, когда вы используете оператор ++. Если вы проанализируете список тысяч элементов, эта сложность повредит вам. Используя вместо этого рекурсивную версию, ['$ 1'] ++ '$ 2' даст вам линейное время, даже если синтаксический анализатор должен переместить весь список в стек до того, как он начнет уменьшаться. Вы можете попробовать обе версии и проанализировать действительно длинный список, чтобы увидеть разницу.

Использование разделителя как в «propdef», «proplist» не меняет проблему.