Устранение левой рекурсии

Question

У меня есть эта грамматика

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

Я хочу знать, как исключить левую рекурсию из этой грамматики, потому что S+S действительно сбивает с толку...

Answer 1

Посмотрим, сможем ли мы упростить данную грамматику.

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

Мы можем написать это как;

S -> S*|SQ|SS|B|a
Q -> +S
B -> (S)

Теперь вы можете устранить левую рекурсию на знакомой территории.

S  ->  BS'|aS'
S' ->  *S'|QS'|SS'|e
Q  ->  +S
B  ->  (S)

Обратите внимание, что e это эпсилон / лямбда.

Мы удалили левую рекурсию, поэтому нам больше не нужны Q и B.

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

Вы найдете это полезным, когда имеете дело с устранением левой рекурсии.

Answer 2

Мой ответ с использованием теории из этой ссылки

Как устранить левую рекурсию в контекстно-свободной грамматике.

S -->  S+S | SS | S*    |        a | (S)
      --------------            -------   
      Sα form                   β form    
      Left-Recursive-Rules      Non-Left-Recursive-Rules       

Мы можем написать как

S ---> Sα₁ | Sα₂ | Sα₃ | β₁ | β₂

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

S ---> β₁ | β₂
Z ---> α₁ | α₂ | α₃
Z ---> α₁ Z | α₂ Z | α₃ Z
S ---> β₁ Z | β₂ Z

куда

α₁ = + S
α₂ = S
α₃ = *

А также β-продукция не начинается с S:

β₁ = а
β₂ = (S)

Грамматика без левой рекурсии:

Нелевая рекурсивная продукция S -> β_n

S -->  a | (S)   

Введите новую переменную Z со следующими производствами: Z ---> α_n и Z -> α_n Z

Z --> +S | S | * 

and 

Z --> +SZ | SZ | *Z  

И новый S производства: S -> β_n Z

S -->  aZ | (S)Z     

---

Вторая форма (ответ)

Продукция Z --> +S | S | * а также Z --> +SZ | SZ | *Z можно сочетать как Z --> +SZ | SZ | *Z| ^ где ^ является нулевым символом.

Z --> ^ использовать для удаления Z из правил производства.

Итак, второй ответ:

S --> aZ | (S)Z а также Z --> +SZ | SZ | *Z| ^