Преобразование контекстно-свободной грамматики в LL(1)

Question

У меня есть следующая грамматика:

S -> S+S|SS|S*|(S)|a

Как мне преобразовать его в грамматику LL(1)?

Я пытался устранить левую рекурсию, поэтому я получил

S->(S)S'|aS'
S'->+SS'|SS'|*S'|epsilon

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

S->(S)S"|aS"
       S"->S'S"|epsilon
       S'->+S|*|S

Но я до сих пор не получаю идеального ответа. Я чувствую, что грамматика все еще не LL(1). Пожалуйста помоги.

Answer 1

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

S → Срок

Срок → CoreTerm OptMore

CoreTerm → a | (Срок)

OptMore → ε | Срок | + Срок | * OptMore

Например, вы бы получили (a + a) * a как

S

⇒ срок

⇒ CoreTerm OptMore

⇒ OptMore

⇒ Срок

⇒ CoreTerm OptMore

⇒ (CoreTerm OptMore) OptMore

⇒ (OptMore) OptMore

⇒ (+ термин) OptMore

⇒ (CoreTerm OptMore) OptMore

⇒ a (a + a OptMore) OptMore

⇒ a (a + a) OptMore

⇒ a (a + a) * OptMore

⇒ a (a + a) * Срок

⇒ a (a + a) * CoreTerm OptMore

⇒ a (a + a) * OptMore

⇒ а (а + а) * а

Чтобы увидеть, что это грамматика LL(1), вот ПЕРВЫЕ наборы:

• FIRST (S) = {
• FIRST (Term) = {a, (}
• FIRST (CoreTerm) = {a, (}
• FIRST (OptMore) = {ε, a, (, +, *}

Вот СЛЕДУЮЩИЕ наборы:

• СЛЕДУЙТЕ ЗА (S) = {$}
• СЛЕДУЙТЕ (Срок) = {$,)}
• FOLLOW (CoreTerm) = {a, (, +, *, $}
• FOLLOW (OptMore) = {$,)}

Итак, теперь мы можем заполнить таблицу разбора:

         | a                | (                | +      | *         | )   | $
---------+------------------+------------------+--------+-----------+-----+------
S        | Term             | Term             |        |           |     |
Term     | CoreTerm OptMore | CoreTerm OptMore |        |           |     |
CoreTerm | a                | (Term)           |        |           |     |
OptMore  | Term             | Term             | + Term | * OptMore | eps | eps

Так что эта грамматика действительно LL(1).