Теория языков программирования методов трансляции (стр. 13 )

Каждая следующая цепочка левого вывода получается из предыдущей цепочки заменой самого левого нетерминала правой частью некоторого правила.

Пример. Рассмотрим КС-грамматику G0 с правилами

E®E+T | T

T®Т*F | F

F®(Е) | a.

Нарисуем дерево вывода (рис 3.7).

Рис. 3.9. Пример дерева вывода

Это дерево служит представлением десяти эквивалентных выводов цепочки а+а.

ЕÞ Е+Т ÞТ+Т ÞF+ТÞ а+ТÞ а+FÞа+а – левый вывод.

ЕÞ Е+Т ÞЕ+F ÞЕ+а Þ Т+аÞ F+аÞа+а – правый вывод.

Определение. Цепочку a будем называть левовыводимой, если существует левый вывод S= = a, и писать S. Аналогично a будем называть правовыводимой, если существует правый вывод S= = a, и писать S. Один шаг левого вывода будем обозначать , а правого

3.10.2.  Преобразование КС–грамматик

КС-грамматику часто требуется модифицировать так, чтобы порождаемые ею языки приобрели нужную структуру. Рассмотрим, например, язык L(G0). Этот язык порождается грамматикой G с правилами

Е®Е+Е | Е*Е | (Е) | a.

Но эта грамматика имеет два недостатка. Прежде всего, она неоднозначна из-за наличия правила Е®Е+Е | Е*Е. Эту неоднозначность можно устранить, взяв вместо G грамматику G1 с правилами

Е®Е+Т | Е*Т | Т

Т®(Е) | а.

Другой недостаток грамматики G, которым обладает и грамматика G1, заключается в том, что операции + и * имеют один и тот же приоритет, т. е. структура выражения а+а*а и а*а+а, которую мы придаём грамматике G1, подразумевает тот же порядок выполнения операций, что и в выражениях (а+а)*а и (а*а)+а соответственно.

Чтобы получить обычный приоритет операций + и *, при которых * предшествует + и выражение а+(а*а) понимается как а+(а*а), надо перейти к грамматике G0.

Общего алгоритмического метода, который придавал бы данному языку произвольную структуру, не существует. Но с помощью ряда преобразований можно видоизменить грамматику, не испортив порождаемый ею язык.

Начнём с очевидных, но важных преобразований. Например, в грамматике G=({S, A}, {a, b}, P, S), где Р={S®a, A®b}, нетерминал А и терминал b не могут появляться ни в какой выводимой цепочке. Таким образом, эти символы не имеют отношения к языку L(G) и их можно устранить из определения грамматики G, не затронув языка L(G).

Определение.

Назовём символ ХÎNÈS бесполезным в КС – грамматике G = (N, S, Р, S), если в ней нет вывода вида SÞ* wXy Þ* wxy, где w, x, y принадлежат S* .

Чтобы установить, бесполезен ли нетерминал А, построим сначала алгоритм, выясняющий, может ли этот нетерминал порождать какие - либо нетерминальные цепочки, т. е. алгоритм, решающий проблему пустоты множества {w | A Þ* w, wÎ S*}.

Алгоритм. Непуст ли язык L(G)?

Вход. КС-грамматика G = (N, S, Р, S).

Выход. «ДА» если L(G)¹Æ, «НЕТ» в противном случае.

Метод. Строим множества рекурсивно.

1)  Положить = Æ, i=1.

2)  Положить .

3)  Если ¹ , то положить i=i+1 и перейти к шагу 2), в противном случае - =.

4)  если SÎ, то выдать вывод «ДА», в противном случае – «НЕТ».

Так как символ ÍN, то алгоритм должен остановиться максимум после n+1 повторения шага 2).

Теорема.

Алгоритм, приведённый выше, говорит «ДА» тогда и только тогда, когда SÞ*w для некоторой цепочки w Î S* .

Определение.

Символ XÎNÈS назовём недостижимым в КС – грамматике G = (N, S, Р, S), если х не появляется ни в одной выводимой цепочке.

Недостижимые символы можно устранить из КС – грамматики с помощью следующего алгоритма.

Алгоритм устранения недостижимых символов.

Вход. КС – грамматика G = (N, S, Р, S).

Выход. КС - грамматика G' = (N', S', Р', S), у которой

i) L(G')=L(G),

ii) для всех существуют такие цепочки a и b из (N' ÈS')*, что SÞ*G' aXb.

Метод.

1)  Положить = {S} и i=1.

2)  Положить .

3)  Если , положить i=i+1 и перейти к шагу (2), в противном случае, пусть

-  ,

-  ,

-  Р' – состоит из правил множества Р, содержащих только символы из ,

-  G' = (N', S', Р', S).

Заметим, что шаг 2) алгоритма можно повторить только конечное число раз, т. к. .

На базе двух рассмотренных алгоритмов построим обобщенный алгоритм устранения бесполезных символов.

Алгоритм устранения бесполезных символов.

Вход. КС – грамматика G = (N, S, Р, S), у которой L(G)¹Æ.

Выход. КС - грамматика G' = (N', S', Р', S), у которой L(G')=L(G) и в N' ÈS' нет бесполезных символов.

Метод.

1)  Применив к G алгоритм «не пуст ли язык?», получить , положить G1 = (NÇ, S, , S), где состоит из множества правил Р, содержащих только символы из .

2)  Применив к G1 алгоритм «устранение недостижимых символов», получить G' = (N', S', Р', S).

Таким образом, на шаге 1) нашего алгоритма из G устраняются все нетерминалы, которые не могут порождать терминальных цепочек. Затем на шаге 2) устраняются все недостижимые символы.

Каждый символ Х результирующей грамматики должен появиться хотя бы в одном выводе вида SÞ* wXy Þ* wxy.

Резюме. Грамматика G', которую строит рассматриваемый алгоритм, не содержит бесполезных символов.

В практике построения трансляторов обычно правила А®е бессмысленны. Очень полезно отработать метод устранения таких правил из грамматики.

Определение.

Назовём КС – грамматику G = (N, S, Р, S) грамматикой без е - правил (или неукорачивающей), если либо Р не содержит е – правил, либо есть точно одно правило S®е и S не встречается в правых частях остальных правил из Р.

Алгоритм преобразования в грамматику без е – правил.

Вход. КС – грамматика G = (N, S, Р, S).

Выход. Эквивалентная КС - грамматика G' = (N', S', Р', S) без е – правил.

Метод.

1)  Построить .

2)  Построить Р' следующим образом:

a) если принадлежит Р, k³0 и для 1£i£к, но ни один символ в цепочках (0£j£k) не принадлежит , то включить в Р' все правила вида: