УСТРАНЕНИЕ ЦЕПНЫХ ПРАВИЛ
ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ КС-ГРАММАТИК
Алгоритм устранения недостижимых символов.
Недостижимые терминалы (группа “в” бесполезных символов) и недостижимые нетерминалы, порождающие терминальные строки (группа “б” бесполезных символов), исключаются из грамматики с помощью алгоритма устранения недостижимых символов.
Вход: КС-грамматика G=(VN, T, P, S)
Выход: Эквивалентная КС-грамматика G’=(N’, T’, P’, S) у которой L(G)=L(G’) и для всех Z Î S’ существуют выводы SÞ*aZb, где a,bÎ (S’)*.
Здесь, как и в предыдущей задаче, сначала решается обратная задача, т.е. определяется множество W достижимых символов Z:
W={Z | Z Î S, $ SÞ*aZb, где a,bÎ (S’)*}.
1. Положить W0=S
2. Вычислить W1= W0 È {X | X Î S, (A®aXb) ÎP, A Î W0 , a,bÎ (S’)*}
3. Если W1¹W0 , то положить W0= W1 и перейти к п.2; иначе положить W= W1
4. Вычислить N’=NÇW, T’==TÇW, Б=S-W, P’=P-PБ, где PБÍP – это множество правил, содержащих недостижимые символы XÎ Б, т.е. PБ = {(X ®a)ÎP для всех XÎ Б , где aÎS}
Пример:Преобразование КС-грамматики с правилами
1) Q ® ab 2)B ® b 3)C ® db
в эквивалентную грамматику, не содержащую бесполезных символов.
| Шаг алгоритма | Действия и результаты |
| W0=Q | |
| W1 = { Q, a,b } | |
| W1 = W0 ? Нет W0 = W1={ Q, a, b } | |
| W1 = { Q, a, b } | |
| W1 = W0 ? Да W ={ Q, a, b } | |
| N’= { Q} T’={a, b} Б={B, C, d} P’= {Q ® ab} |
Цепное правило – это правило вида А®В, где А,В Î N. Цепные правила могут быть причиной нежелательных свойств грамматики, таких, например, как циклы. Алгоритм устранения цепных правил осуществляет замещение правой части каждого цепного правила, используя для этого не цепные правила.
Вход: КС-грамматика G=(N, T, P, S) без e-правил.
Выход: Эквивалентная КС-грамматика G’=(N, T, P’, S) без цепных правил.
1. Для каждого нетерминала А вычислить NA = {B | AÞ*B, где BÎ N }:
1.1. Положить N0A={A}
1.2. Вычислить N1A = N0A È{C | (B®C) Î P, B Î N0A , C Î N }
1.3. Если N1A ¹ N0A , то положить N0A = N1A и перейти к п.1.2, иначе положить
NA = N1A
2. Построить множество P’ так: если (В®a) Î P не является цепным правилом (a Ï N), то включить в P’ правило А®a для каждого А, такого, что В Î NA, т.е.
P’={ А®a для всех (В®a) Î P , где a Ï N и В Î NA }
Пример: Преобразовать грамматику G с правилами:
G: S® X
X® Y
Y®Y; | z
в эквивалентную грамматику без цепных правил:
| Шаг алгоритма | Действия и результаты |
| 1.1 | N0S = {S} |
| 1.2 | N1S = {S, X} |
| 1.3 | N1S = N0S ? Нет N0S = N1S={S, X} |
| 1.2 | N1S = {S, X, Y} |
| 1.3 | N1S = N0S ? Нет N0S = N1S={S, X,Y} |
| 1.2 | N1S = {S, X, Y} |
| 1.3 | N1S = N0S ? Да NS ={S, X,Y} |
| 1.1 | N0X = {X} |
| 1.2 | N1X = {X,Y} |
| 1.3 | N1X = N0X ? Нет N0X = N1X={X, Y} |
| 1.2 | N1X = {X,Y} |
| 1.3 | N1X = N0X ? Да NX ={X,Y} |
| 1.1 | N0Y = {Y} |
| 1.2 | N1Y = {Y} |
| 1.3 | N1Y = N0Y ? Да NY ={Y} |
| P’={S®Y;|z, X®Y; |z , Y®Y; |z} |
Пример:Преобразовать грамматику G с правилами:
G: E® E+T
E®T
T®T*P
T®P
P®i
P®(E)
1. После выполнения шага 1 алгоритма получаем: NE ={E, T, P}, NT ={T, P}, NP ={P}
2. Выберем первый нетерминал E из множества NE. Формируя множество правил , левая часть которых - нетерминальный символ Е, а правые части нецепных правил исходной грамматики, в левой части которых находятся символы из множества NE, получаем: { E® E+T , E®T*P, E®i, E®(E)}. Таким же образом рассматриваем остальные символы из NE, затем символы из NT и NP .
3. Окончательно получаем P’={ E® E+T , E®T*P, E®i, E®(E), T®T*P, T®i, T®(E), P®i, P®(E)}