Левая рекурсия
Алгоритм разбора, используемый в утилите yacc, лучше подходит для так называемых леворекурсивных грамматических правил вида
name : name rest_of_rule ;
Правила, подобные
list : item | list ',' item ;
и
seq : item | seq item ;
часто возникают при спецификации списков и последовательностей. В каждом из этих случаев первое правило будет использовано только для свертки первого элемента, второе правило будет использоваться для свертки второго и всех последующих элементов.
Для праворекурсивных правил, таких как
seq : item | item seq ;
алгоритм разбора немного сложнее; элементы выделяются и свертываются справа налево. Более серьезно то, что есть опасность переполнения внутреннего стека при чтении очень длинной последовательности. Поэтому рекомендуется использовать левую рекурсию.
Стоит рассмотреть случай, когда имеет смысл последовательность из нуля элементов. Спецификация такой последовательности включает правило с пустым телом:
seq : /* пусто */ | item seq ;
И вновь первое правило будет использоваться для свертки только перед тем, как прочитан первый элемент, а второе - для свертки всех прочитанных элементов. Допущение пустых последовательностей часто ведет к увеличению общности. Однако могут возникнуть конфликты, поскольку yacc вынужден решать, пустая последовательность чего прочитана, в то время как он еще недостаточно прочитал, чтобы узнать это.
