Может кто-нибудь показать мне, как исключить левую рекурсию из этой грамматики, используя правила? - PullRequest
Новая
       26

Может кто-нибудь показать мне, как исключить левую рекурсию из этой грамматики, используя правила?

0 голосов
/ 26 января 2019

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

S --> SX | SSb | XS | a
X --> Xb | Sa | b

Итак, я знаю, что в этом конкретном примере я могу сначала удалить немедленную левую рекурсию из Sправило, а затем после этого я получаю это: 

S --> XSS' | aS'
S' --> XS' | SbS' | epsilon
X --> Xb | Sa | b

Затем, отсюда я могу объединить производство S с производством X, чтобы получить: 

 X --> Xb | XSS' | aS'a | b

и затем я могу удалить немедленнооставил рекурсию оттуда, чтобы получить мой окончательный ответ.НО, может кто-нибудь объяснить мне правила, потому что я не следовал им, чтобы прийти к своему окончательному ответу.Мне вроде повезло.Мне нужно знать, как удалить левую рекурсию из любой данной грамматики.Любая помощь будет принята с благодарностью.Спасибо.

1 Ответ

0 голосов
/ 09 февраля 2019
  1. Найдите тела всех нетерминальных произведений A с левой рекурсией и удалите их.
  2. Добавьте их в новый нетерминальный A '
  3. Для каждого нетерминального A'product:
    • Удалить первый рекурсивный вызов A
    • Добавить вызов A 'в конце
  4. Вы добавляете продукцию epsilon к нетерминалу A'
  5. Для всего остального нетерминального производства A добавьте A' в конец

Пример: A -> Ab |Bb |a

  1. A -> Bb |a
  2. A '-> Ab
  3. A' -> bA '
  4. A' -> bA '|e
  5. A -> BbA '|aA '

Результат: A -> BbA' |aA 'A' -> bA '|е

...