Чтение Правильная рекурсия

Question

Я понимаю, что в левой рекурсии

A -> Aα |β

так что A может быть или β и останавливаться или продолжаться и иметь Aα бесконечное количество раз, поскольку это объясняется само по себе.Поэтому, если бы я проанализировал βαα:

      A 
     / \
    A   α 
   / \
  Α   α
 /
β 

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

A-> βA '

A'-> αA '| ε

Я могу снова выполнить дерево разбора для βαα, но не могу прочитать правила производства, как в левой рекурсии.Может кто-нибудь объяснить шаги чтения правил производства в этой правильно-рекурсивной грамматике?

Answer 1

Производственные правила применяются в следующем порядке:

A -> 
  -> βA'   (apply A -> βA')
  -> βαA'  (apply A' -> αA')
  -> βααA' (apply A' -> αA')
  -> βαα   (apply A' -> ε)

Дерево разбора будет выглядеть так:

  A 
 / \
β   A' 
   / \
  α   A'
     / \
    α   A'
        |
        ε

---

Удаление прямой левой рекурсии

каждое правило с прямой левой рекурсией:

A -> Aa | Ab | Ac | ... | x | y | z

заменяется на:

A  -> xA' | yA' | zA' | ...
A' -> aA' | bA' | cA' | ε

, где a, b, c, ..., x, y, z - последовательности, которые не начинаются с A.

Повторяйте этот процесс, пока не останется прямой рекурсии слева.