Как преобразовать грамматику в нисходящую оформленную грамматику

Question

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

S ‐> S a | S b a | a | S b c S | S b c b | c S | c b 

и мне нужно, чтобы использовать его для того, чтобы создать несколько наборов SD, а затем на столе разбора.

Но прежде чем это сделать, я должен преобразовать это в грамматику с синтаксисом сверху вниз.

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

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

Не могли бы вы дать мне некоторую помощь?

Answer 1

Вот общая agorithm:

Каждое правило, как

A -> Aa 
A -> b 

становится

A -> bA' 
A'-> aA' 
A'-> e 

где e означает пустой (эпсилон).

Так что для вашего дела, вы можете начать с

S ‐> S a | S b a | a => S -> aS' , S' -> aS' | baS' | e 

И выяснить, остальное