Как я могу устранить левую рекурсию в следующей грамматике?

Вот грамматика, которая должна описывать язык вложенных фигурных скобок с запятыми в качестве разделителей:

L ::= {L} | L,L |

Еще несколько примеров строк, которые я ожидаю, что грамматика примет и отклонит:

Принимать:

{,{,,{,}},,{,}}
{{{{}}}}
{,{}}

Отклонять:

{}{}
{,{}{}}
{{},{}

syntax language-agnostic context-free-grammar
person wkf    schedule 08.07.2009    source источник
comment
какой инструмент вы используете, чтобы получить ошибку левой рекурсии?   -  person Simeon Pilgrim    schedule 08.07.2009
comment
Не домашняя работа, просто пытаюсь разобраться в книге по компиляторам. Ради удовольствия, клянусь!   -  person wkf    schedule 08.07.2009

Ответы (2)


arrow_upward
4
arrow_downward

Сделано своими руками:

Л ::= { Л } | { Л } , | , л |

Или, вместо того, чтобы просто использовать его, мы могли бы использовать более систематический подход и применить алгоритм из Википедии к удаление непосредственной левой рекурсии:

L ::= { L } L1 | L1
L1 ::= | , Л Л1

person John Kugelman    schedule 08.07.2009
comment
Не могу придумать, как вывести {{},} из этой грамматики. - person Johannes Schaub - litb; 08.07.2009
comment
@litb: внешний {} - это первое правило {L}, {} - это первое правило L, L, первое из которых {}, а второе пустое. - person Simeon Pilgrim; 08.07.2009
comment
кивок, я только что щелкнул вас, когда имел в виду, что грамматика JK против wkf моя плохая. - person Simeon Pilgrim; 08.07.2009

arrow_upward
0
arrow_downward

Прежде всего, эта грамматика не примет ваш первый пример, поскольку требует, чтобы запятые стояли после закрывающей скобки и перед открывающей скобкой. Я бы предложил переписать его как

L::= {L} | ,L

Это не избавит от левой рекурсии, но, по крайней мере, будет соответствовать вашим приемлемым ответам.

person a_m0d    schedule 08.07.2009
comment
Не правда. Его грамматика примет {,}, где ',' создается L1=L2,L3, где L2 и L3 пусты. - person John Kugelman; 08.07.2009
comment
Ваше право - я не понял, что в этом смысл пустого правила в конце - person a_m0d; 08.07.2009