Как преобразовать грамматику в грамматику, разбираемую сверху вниз

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

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

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

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

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

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

Не могли бы вы мне помочь?


compiler-construction grammar ll left-recursion context-free-grammar
person Cosmin    schedule 13.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вот общий агоритм:

Каждое правило нравится

A -> Aa
A -> b

становится

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

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

Итак, в вашем случае вы можете начать с

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

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

person Pyetras    schedule 18.03.2015