Как удалить Непрямой леворекурсивные

Question

мне нужна помощь удаления косвенную леворекурсивные из этой грамматики:

A -> B (sB)* 
    | dAd 
    | z 

B -> <id> 
    | sB 
    | A 

Таким образом, вы могли бы перейти от A-> B-> A .... без потребления каких-либо символов.

Я попытался это исправить несколько различных способов, но продолжает работать в вопросах из-за этого бита (С.Б.) *

Я не уверен, если я делаю что-то неправильно или если грамматика является неправильным в Генеральная.

Answer 1

Интересно. Я не вижу механического способа сделать это. Является ли это тем, как указан язык, или вы в конечном итоге получили некоторые другие упрощения? В любом случае, решение для конкретной проблемы является "инлайн" B в левой рекурсии части:

А -> (< идентификатор> | зВ | DAD | г) (ШБ) *
B -> < id> | sB | A

Основная идея состоит в том, чтобы заменить нерекурсивные термины в рекурсивной части и переместить рекурсивный термин в конец.

Answer 2

Старт с

A -> B (sB)* | dAd | z 

B -> <id> | sB | A 

Заменитель

A -> (<id> | sB | A) (sB)* | dAd | z 

Определение

C -> (sB)* 

Заменитель

A -> (<id> | sB | A) C | dAd | z 

фактор

A -> <id> C | sBC | AC | dAd | z 

Определение

D -> <id> C | sBC | dAd | z 

Так

A -> D | AC 

Снять левый рекурсии

A -> D (C)* 

Заменитель C и D

A -> (<id> (sB)* | sB(sB)* | dAd | z) (sB)** 

С x** = x*

A -> (<id> (sB)* | sB(sB)* | dAd | z) (sB)* 

С x*x* = x*

A -> (<id> | sB | dAd | z) (sB)* 

B -> <id> | sB | A 

Тот же результат, как Шринивас лет.

---

Редактировать добавлен после просмотра @ ответ Rymoid в.

В этот момент левая рекурсия была удалена, поэтому мы закончили. Но, как указывает @Rymoid, грамматика все еще неоднозначна и поэтому не LL (1). Ниже я попытаюсь справиться с двусмысленностью, но не найти грамматику LL (1).

Одна проблема заключается в том, что с A =>* sB выбор sB | A неоднозначен и не нужен. Начнем с удаления этого выбора. У нас есть

A -> (<id> | sB | dAd | z) (sB)* 

B -> <id> | A 

Аналогично A =>* <id>, поэтому выбор <id> | A неоднозначна и не требуется. У нас есть

A -> (<id> | sB | dAd | z) (sB)* 

B -> A 

И тогда нам не нужно B больше.

A -> (<id> | sA | dAd | z) (sA)* 

Оставшаяся проблема в том, что, поскольку s в последующем наборе A, нет никакого способа узнать, с одной знаком опережающего просмотра, независимо от того, чтобы остаться в петле (sA)* или выйти из нее.

Исходный вопрос не запрашивал грамматику LL (1), но поскольку сообщение помечено [JavaCC], мы можем предположить, что желаемое - это тот, который работает с JavaCC. Это не совсем то же самое, что LL (1), хотя LL (1) подразумевает, что грамматика будет хорошо работать с JavaCC.

Я предполагаю, что все виды использования A вне определения A определенно не следует s. Чтобы быть конкретным в этом, я буду считать, что есть (только) еще одна продукция, которая составляет S -> A <EOF>, и что S является стартовым нетерминалом. Но на самом деле важно то, что у вас никогда не было A, за которым следует s, за исключением того, что в текущем определении A.

Мы

S -> A <EOF> 
A -> (<id> | sA | dAd | z) (sA)* 

Если у вас есть неоднозначная грамматика, но хотят, чтобы устранить неоднозначность, вопрос, чтобы спросить себя: Какой разобрать я хочу в неоднозначных случаях? Два ответа: «Оставайтесь в цикле как можно дольше». и «Выскочите из петли как можно скорее». (Другие ответы возможны, но вряд ли.)

«Пребывание в петлю как можно дольше»

Это JavaCC по умолчанию, поэтому нет необходимости менять грамматику. Это может вызвать предупреждение. Возможно, это можно будет подавить с LOOKAHEAD(<s>) в начале цикла.

«Выход из цикла как можно скорее»

сделать две версии A. A0 никогда не следует s. A1 всегда следует за s. (На самом деле следует возможным первый s, поэтому (sA)* часть не хотела. Этот выбор соответствует выручая из цикла как можно скорее.)

S -> A0 <EOF> 
A0 -> (<id> | sA0 | dA0d | z) [ s (A1s)* A0 ] 
A1 -> <id> | sA1 | dA0d | z 

Я совершенно уверен, что это однозначное и что A0 определяет тот же язык, что и A.Это не LL (1), и JavaCC выдаст предупреждение, которое должно быть учтено.

Чтобы сделать его пригодным для JavaCC, мы можем добавить синтаксическое представление LOOKAHEAD(A1 <s>) к началу цикла.

Answer 3

Прежде чем мы начнем, давайте номер вашего производства, так что у нас есть что-то сослаться:

1: A -> B (s B)* 
2: A -> d A d 
3: A -> z 
4: B -> <id> 
5: B -> s B 
6: B -> A 

Поскольку вы пытаетесь устранить левую рекурсию, я могу только предположить, что вы пытаетесь применить LL разбор. Тем не менее, эта грамматика неоднозначна, поэтому она не может быть грамматикой LL (1). Так, например, фраза zszsz может быть (крайний левый), полученный из A в более чем одним способом:

A ->+ B s B  (1) 
    ->+ A s B  (6) 
    ->+ z s B  (3) 
    ->+ z s B s B (1) 
    ->+ z s z s z (6, 3, 6, 3) 

A ->+ B s B  (1) 
    ->+ A s B  (6) 
    ->+ B s B s B (1) 
    ->+ A s B s B (6) 
    ->+ z s B s B (3) 
    ->+ z s z s z (6, 3, 6, 3) 

---

Первым шагом было бы упростить эту грамматику, так что каждое производство имеет только последовательности терминалов и не-терминалы на «расширенной» стороне. Правило № 1 имеет Клини звезду, так что давайте избавиться от него, заменив его нетерминального C:

1: A -> B C 
2: A -> d A d 
3: A -> z 
4: B -> <id> 
5: B -> s B 
6: B -> A 
7: C -> <empty> 
8: C -> s B C 

Теперь все произведения просты.

---

Далее мы идентифицируем косвенную левую рекурсию (если есть) и превратим ее в прямую левую рекурсию. Рассматривая все производственные процессы, которые начинаются с нетерминала, мы обнаруживаем, что A и B участвуют в косвенной левой рекурсии (через правила № 1 и № 6). Мы можем разбить этот цикл, заменив B в правиле № 1 тем, что он может произвести; мы заменить правило # 1 с

9: A -> <id> C 
10: A -> s B C 
11: A -> A C 

С другой стороны, мы могли бы разорвать петлю, заменяя Постановки # 1, # 2 и # 3 в # 6. Однако мы делаем это, результирующая грамматика не имеет косвенной левой рекурсии.

---

Затем мы устраняем прямую левую рекурсию (если есть) в нашей грамматике. Это происходит в нетерминальным A, в результате нашего замещения:

2: A -> d A d 
3: A -> z 
... 
9: A -> <id> C 
10: A -> s B C 
11: A -> A C 

Введем еще нетерминальный D, и заменить эти правила с

12: A -> d A d D 
13: A -> z D 
14: A -> <id> C D 
15: A -> s B C D 
17: D -> <empty> 
18: D -> A D 

---

Полученная грамматика без левого рекурсии:

4: B -> <id> 
5: B -> s B 
6: B -> A 
7: C -> <empty> 
8: C -> s B C 
12: A -> d A d D 
13: A -> z D 
14: A -> <id> C D 
15: A -> s B C D 
17: D -> <empty> 
18: D -> A D 

Как указано в начале, вы не может построить таблицу разбора LL (1) из этой грамматики, поскольку самый левый вывод zszsz от A по-прежнему неоднозначен.