Как да трансформираме граматика в граматика с анализ отгоре надолу

Имам тази част от граматиката

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

и трябва да го използвам, за да създам някои SD набори и по-късно върху таблица за анализ.

Но преди да направя това, трябва да преобразувам това в анализируема граматика отгоре надолу.

Въпросът ми е как го правиш? Знам, че трябва да се отървете от ляво-рекурсивността, но как да го направя?

Прочетох статията в wikipedia и още една от университета, но не мога да си обясня как трябва да го направя.

Можете ли да ми помогнете?

compiler-construction grammar ll left-recursion context-free-grammar

Cosmin 13.03.2015 източник

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

И разберете останалото

Pyetras 18.03.2015