Нужен совет, как сделать эту грамматику BNF пригодной для синтаксического анализа LL(1) (левый факторинг)

Я работаю над проектом синтаксического анализа, в котором используется адаптация этой грамматики для регулярных выражений 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>

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

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

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

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

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


parsing compiler-construction bnf
person Erik Nyquist    schedule 29.11.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Проблема, которую вы пытаетесь решить, заключается в том, что

items → item
items → item items

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

Предлагаемое вами исправление

items → item
items → items item

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

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

def items():
  list = [ item() ]
  while couldStart(item, lookahead):
    list.append(item())
  return list
person rici    schedule 30.11.2015
comment
ага, левая рекурсия. Возможно, мне нужно стряхнуть пыль с книги о красном драконе... Я многое забыл. Спасибо за это. Вы предполагаете, что в реальной реализации рекурсивного спуска эту проблему можно обойти без левого факторинга грамматики? Я не вижу решения, которое вы предлагаете с этим фрагментом Python. - person Erik Nyquist; 30.11.2015
comment
@ErikNyquist: Возможно, код псевдопитона не очень помогает. Дело в том, что практичный синтаксический анализатор RD использует циклы, а не рекурсию, и можно реализовать X+ как цикл: сначала распознать X, а затем повторять до тех пор, пока следующий токен может запустить X. В C я бы написал это как цикл do ... while; может так было бы понятнее. X* также можно распознать с помощью цикла; единственная разница в том, что проверка идет в начале, а не в конце. - person rici; 30.11.2015
comment
Хорошо, я понял тебя. Я действительно буду избегать рекурсии, поэтому скоро дойду до того, что мне придется реализовать это, и я ценю совет. Мне не удалось найти какие-либо комнаты IRC, связанные с дизайном компилятора, или даже более мелкие подобласти (например, синтаксические анализаторы LL, грамматики BNF). Знаете ли вы какие-нибудь хорошие форумы для обсуждения этих вещей... кроме stackoverflow? - person Erik Nyquist; 30.11.2015
comment
@ErikNyquist: Больше нет, извини. Это не значит, что их нет :) - person rici; 30.11.2015