Ищете совет по составлению этой грамматики BNF, подходящей для анализа LL (1) (левый факторинг)

Question

Я работаю над проектом синтаксического анализа, который использует адаптацию этой грамматики для регулярных выражений Perl http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regexp-plg.html. Я упростил эту грамматику для своих собственных целей, например, так (обратите внимание, что, поскольку «|» является лексема, я вместо того, чтобы с помощью запятой «» так раздельные постановки на данный нетерминал):

<RE>  := <union>, <simple> 
<union> := <RE> | <simple> 
<simple> := <concat>, <basic> 
<concat> := <simple><basic> 
<basic> := <zero>, <one>, <onezero>, <elem> 
<zero> := <elem>* 
<one>  := <elem>+ 
<onezero> := <elem>? 
<elem> := <group>, <any>, <literal>, <class> 
<group> := (<RE>) 
<class> := [<items>] 
<items> := <item>, <item><items> 
<item> := <range>, <literal> 

I хотите написать парсер LL (1) для обработки этой грамматики, а для анализатора LL (1) производные для <items> имеют некоторую двусмысленность. Чтобы это исправить, я бы оставил-фактор их, добавив новый нетерминал <X>, например, так:

<items> := <item><X> 
<X>  := <items>, epsilon 

Но что мне интересно, я мог просто перевернуть вокруг порядка второго производства в <items>, как это:

<items> := <item>, <items><item> 

и не добавлять новые нетерминальные? Похоже, что это ничего не сломает, ведь вся цель этой продукции - разрешить любое переменное число последовательных символов <item>, и мы по-прежнему получаем это, если мы отменим порядок. Я что-то упускаю, или просто отменяет порядок достижения той же цели, что и левый фактор в этой ситуации?

Answer 1

Проблема вы пытаетесь исправить что

items → item 
items → item items 

не слева учтены; обе постановки начинаются с item.

предложил Ваше затруднительное

items → item 
items → items item 

не помогает (независимо от начала item все еще может начать либо производство items), но что более важно, он остается рекурсией, которая Verboten для LL грамматик ,

В принципе, «новый нетерминал» является правильным решением, но в метод рекурсивного спуска, вы, вероятно, сделать что-то вроде этого:

def items(): 
    list = [ item() ] 
    while couldStart(item, lookahead): 
    list.append(item()) 
    return list