Алгоритм Устранение e-правил
Вход: КС-грамматика .
Выход: Эквивалентная КС-грамматика без e-правил для всех нетерминальных символов, кроме начального, который не должен встречаться в правых частях правил грамматики.
Шаг 1. В исходной грамматике найти e-порождающие нетерминальные символы , такие, что .
1.1 Положить .
1.2 Вычислить .
1.3 Если , то положить i:=i+1 и перейти к пункту 1.2, иначе считать .
Шаг 2. Из множества правил исходной грамматики перенести во множество все правила, за исключением e-правил, т.е. для всех
Шаг 3. Пополнить множество правилами, которые получаются из каждого правила этого множества путем исключения всевозможных комбинаций e-порождающих нетерминалов в правой части. Полученные при этом e-правила во множество не включать.
Шаг 4. Если , то , где ; иначе
ПримерДана грамматика с правилами . Преобразуем ее в эквивалентную грамматику по алгоритму 4.4.
Шаг 1. N0 = {A, B};
N1 = {S, A, B};
N2 = {S, A, B}.
Т.к. N1 = N2, то искомое множество построено и N = {S, A, B}.
Шаг 2, 3. Множество 1) ; 2) ; 3)
Шаг 4. Т.к. , то введем новый нетерминал С и пополним множество правилом вида . Результирующая грамматика будет иметь вид: с правилами .
Дата добавления: 2016-03-27; просмотров: 1362;