Удаление бесплодных символов
В грамматике G(VT,VN,P,S) символ AVN называется бесплодным, если для него выполняется: {α | A*α, αVT*} = , то есть нетерминальный символ является бесплодным тогда, когда из него нельзя вывести ни одной цепочки терминальных символов.
В простейшем случае символ является бесплодным, если во всех правилах, где этот символ стоит в левой части, он также встречается и в правой части. Более сложные варианты предполагают зависимости между цепочками бесплодных символов, когда они в любой последовательности вывода порождают друг друга.
Для удаления бесплодных символов используется специальный алгоритм удаления бесплодных символов. Он работает со специальным множеством нетерминальных символов Yi. Первоначально в это множество попадают только те символы, из которых непосредственно можно вывести терминальные цепочки, затем оно пополняется на основе правил грамматики G.
Алгоритм удаления бесплодных символов по шагам
1. Y0=, i:=1.
2. Yi= {А | (Аα)Р, α(Yi-1VT)*} Yi-1.
3. Если YiYi-1, то i:= i+1 и перейти к шагу 2, иначе перейти к шагу 4.
4. VN’ = Yi, VT’ = VT, в P’ входят те правила из Р, которые содержат только символы из множества (VTYi), S’ = S.
3.3.5. Устранение -правил
-правилами (или правилами с пустой цепочкой) называются все правила грамматики вида А, где AVN.
Грамматика G(VT,VN,P,S) называется грамматикой без -правил, если в ней не существует правил (А)Р, AS и существует только одно правило (S)P, в том случае, когда L(G), и при этом S не встречается в правой части ни одного правила грамматики.
Для того чтобы упростить построение распознавателей цепочек языка L(G), любую грамматику G целесообразно преобразовать к виду без -правил. Существует алгоритм преобразования произвольной КС-грамматики к виду без -правил. Он работает с некоторым множеством нетерминальных символов Wi.
Алгоритм устранения -правил по шагам
1. W0={A:(A)P}, i:=l.
2. Wi=Wi-1 {A: (Aα)P, бWi-1*}.
3. Если WiWi-1, то i:= i+1 и перейти к шагу 2, иначе перейти к шагу 4.
4. VN’ = VN, VT’ = VT, в P’ входят все правила из Р, кроме правил вида А.
5. Если (Аα)Р и в цепочку α входят символы из множества Wi, тогда на основе цепочки α строится множество цепочек {α’} путем исключения из α всех возможных комбинаций символов из Wi, и все правила вида Аα’ добавляются в Р’.
6. Если SWi, то значит L(G), и тогда в VN’ добавляется новый символ S’, который становится целевым символом грамматики G’, а в Р’ добавляются два новых правила: S’|S; иначе S’ = S.
Данный алгоритм часто ведет к увеличению количества правил грамматики, но позволяет упростить построение распознавателя для заданного языка.
Устранение цепных правил
Циклом (циклическим выводом) в грамматике G(VT,VN,P,S) называется вывод вида А*А, AVN. Очевидно, что такой вывод абсолютно бесполезен. Поэтому в распознавателях КС-языков целесообразно избегать возможности появления циклов.
Циклы возможны только в том случае, если в КС-грамматике присутствуют цепные правила вида АВ, A,BVN. Чтобы исключить возможность появления циклов в цепочках вывода, достаточно устранить цепные правила из набора правил грамматики.
Чтобы устранить цепные правила в КС-грамматике G(VT,VN,P,S), для каждого нетерминального символа XVN строится специальное множество цепных символов Nx, а затем на основании построенных множеств выполняются преобразования правил Р. Поэтому алгоритм устранения цепных правил надо выполнить для всех нетерминальных символов грамматики из множества VN.
Алгоритм устранения цепных правил по шагам
1. Для всех символов Х из множества VN повторять шаги 1–4, затем перейти к шагу 5.
2. NX0={X}, i:=1.
3. NXi= NXi-1{В: (AB)P, В NXi-1}.
4. Если NXi NXi-1, то i:=i+1 и перейти к шагу 2, иначе NX= NXi–{x} и перейти к шагу 1.
5. VN’ = VN, VT’ = VT, в Р’ входят все правила из Р, кроме правил вида АВ, S’=S.
6. Для всех правил (Аα)Р’, если BNА, BA, то в Р’ добавляются правила вида Вα.
Данный алгоритм, так же как и алгоритм устранения -правил, ведет к увеличению числа правил грамматики, но упрощает построение распознавателей.