Приведение КС-грамматики к нормальному виду
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
вые части других правил грамматики, то следует ввести новый начальный символ S и заменить правило S > l двумя новыми правилами: S' > l и S'> S.
В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики:
G ({a,b}, {S}, P = { S > aSbS, S > bSaS, S > l }, S).
Выполняя все возможные замены символа S в первом правиле грамматики, получаем четыре правила вида:
S > aSbS, S > abS, S > aSb, S > ab.
Поступая аналогично со вторым правилом, имеем:
S > bSaS, S >baS, S > bSa, S > ba.
Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило S > l правилами вида S' > l и S' > S.
Построенная совокупность правил образует множество правил искомой неукорачивающей грамматики.
S' > S | l, S > aSbS | abS | aSb | ab | bSaS |?baS | bSa | ba
Все приведенные выше преобразования грамматик могут быть использованы при построении как конечных, так и магазинных автоматов.
Исключение цепных правил
Определение. Правило грамматики вида A > B, где A, B СФ VN, называется цепным.
Для КС-грамматики G, содержащей цепные правила, можно построить эквивалентную ей грамматику G', не содержащую цепных правил.
Идея доказательства заключается в следующем.
Если грамматика G имеет правила A > B, B > C, C > aX, то такие правила могут быть заменены одним правилом А > aX, поскольку вывод А => B => C => aX цепочки aX в грамматике G может быть получен в грамматике G' с помощью правила A > aX.
. Для каждого А СФ N построить NA={BВжA =>*B} следующим образом:
а) Положить N0 = {A} и i=1.
б) Положить Ni ={CВжB>C принадлежит Р и В СФ Ni-1 } U Ni-1.
в) Если Ni ? Ni-1, положить i = i+1 и повторить шаг (б).
В противном случае положить NA = Ni.
. Построить Р так: если В > ? принадлежит Р и не является цепным правилом, включить в Р правило А > ? для всех таких А, что В СФ NА.
. Положить G = (VT, VN, P, S).
В качестве примера выполним исключение цепных правил из грамматики G:
G = ({+,*, (,),a}, {E,T,F}, P={E > E+T | T, Т > T*F | F, F > (E) | a}, E).
Разобьем правила грамматики на два подмножества:
P1 = {E > T, T > F},2 = {E > E+T, T > T*F, F > (E) | a }
На шаге (1) NЕ = {E, T, F}, NT = {T, F}, NF = {F}. После шага (2) множество Р станет таким
E > T+T | T*F | (E) | a> T*F | (E) | a
F > (E) | a
Описание процедур
1)Анализ
Входные данные: правила, введенные в Memo1.
Выходные данные: правила, выведенные в Memo2.
procedure TForm1. btn1Click (Sender: TObject);l;. Clear;i: =0 to mmo1. Lines. Count doLength (mmo1. Lines [i]) >2 then begin: = []; s: =mmo1. Lines [i];j: =0 to Length (s) do begin(s [j] in ['А'. 'Я']) or (s [j] in ['а'. 'я']) then mmo1. Lines. Delete (i);: =mm+ [s [j]]; end;(not (s [1] in ['A'. 'Z'])) or (s [2] 2) then mmo2. Lines. Add (s);:;i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];[i]: = [];j: =3 to Length (p [i]) do if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];;
END;
Пример выполнения:
Введем в Мемо1 следующие правила и нажмем на кнопку 1
грамматика алгоритм символ правило
2)Удаление бесплодных символов
Входные данные: правила из Мемо2
Выходные данные: правила в Мемо2 (без бесплодных символов)
procedure TForm1. btn2Click (Sender: TObject);vn2: set of Char;: =mmo2. Lines. Count;i: =0 to v do p [i]: ='';i: =0 to v do begin p [i]: =mmo2. Lines [i];[i]: = [];j: =3 to Length (p [i]) dop [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];;. Clear;: = [];i: =0 to v-1 do if mn [i] = [] then vn: =vn+ [p [i,1]];: = [];: =0;vn2 then mmo2. Lines. Add (p [i]);;i: =0 to v do p [i]: ='';i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];[i]: = [];j: =3 to Length (p [i]) dop [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];;;
Пример использования:
.Введем в Мемо1 правила
2.Нажмем на кнопку 1
.Нажмем на кнопку 1
3)Удаление недостижимых символов
Входные данные: правила из Мемо2
Выходные данные: правила в Мемо2 (без недостижимых символов)
procedure TForm1. btn3Click (Sender: TObject);
: =mmo2. Lines. Count;i: =0 to v do p [i]: ='';i: =0 to v do begin p [i]: =mmo2. Lines [i];[i]: = [];j: =3 to Length (p [i]) dop [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];;. Clear;: = [];i: =0 to 3 doLength (p [i]) >1 then begin vn: =vn+ [p [i,1]] +mn [0]; Break; end;: =0;m2 then mmo2. Lines. Add (p [i]);i: =0 to v do p [i]: ='';i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];[i]: = [];j: =3 to Length (p [i]) dop [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];;;
Пример использования:
.Введем правила в Мемо1
2.Нажмем на кнопку 1
.Нажмем на кнопку 3
4)Устранение правил с пустой правой частью
Входные данные: правила из Мемо2
Выходные данные: правила в Мемо2
procedure TForm1. btn4Click (Sender: TObject);: =mmo2. Lines. Count;i: =0 to v do p [i]: ='';i: =0 to v do begin p [i]: =mmo2. Lines [i];[i]: = [];j: =3 to Length (p [i]) dop [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];;. Clear;: =0;i: =0 to v doLength (p [i]) >2 thenp [i,3] ='e' then begin(j); r [j]: =p [i,1]; p [i]: ='';;: =j; k: =0;i: =1 to n doj: =0 to v do beginLength (p [j]) >1 thenr [i] in mn [j] then begin: =p [j];(s,1,2);: =s;: =Pos (r [i],s);(s,m,1);: =Pos (r [i],s);(m>0) and (l>0) then begin(k);[k+v]: =Copy (p [j],1,2) +s;(k); l: =Pos (r [i],s); Delete (s1,l+1,1);[k+v]: =Copy (p [j],1,2) +s1;(k); l: =Pos (r [i],s1); Delete (s1,l,1);[k+v]: =Copy (p [j],1,2) +s1;;(m>0) and (l=0) then begin(k);[k+v]: =Copy (p [j],1,2) +s;;; end;i: =0 to v+ (k-1) doj: =i+1 to v+k do beginp [i] =p [j] then p [j]: ='';(Length (p [i]) =3) and (p [i,1] =p