Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 37
Текст из файла (страница 37)
Так же просто доказывается, что если (2.4.4) и (2А.5) истинны для значений параметров, предшествующих г', то (2.4.4) истинно для г'. Оставляем это в качестве упражнения. Из (2 4.4) заключаем, что нетерминалы А„ ..., А„ не являются леворекурсивпыми, так как если А, =; Ага для некоторого а, то й > г. Теперь нужно показать, что петерминалы А;, появляющиеся на шаге (2), пе могут быть леворекурсивными. Это непосредственно следует из того, что грамматика 6 приведенная. На шаге (2) все цепочки а„..., а„не пустые, и потому А; не может быть первым символом правой части правила, 18$ Гл. к алемг.нты таогш1 языкОВ 2.а контекстно-сВОБОдные языки Пример 2.28.
Пусть 6 определяется правиламн А — ВС(а В- СА(АЬ С вЂ” АВ (СС(а Положим А,=А, А,=В и А,=В. После каждого применения шага (2) или (4) алгоритма 2.13 получаются такие грамматики (мы указываем только новые правила): Шаг (2) для 1=1: 6 не меняется Шаг (4) для Г =-2„1=-1:  — СА(ВСЬ(аЬ Шаг (2) для 1=2: В СА(аб(САВ'(аЬВ' В'- СЬВ') СЬ Шаг (4) для 1=-3, у=-1: С- ВСВ)аВ!СС(а Шаг (4) для 1=3, 1=-2: С- САСВ(аЬСВ(САВ'СВ(аЬВ'СВ~аВ(СС)а Шаг (2) для г'=-3: С вЂ” - аЬСВ ) аЬВ СВ ) аВ ( а ! аЬСВС' ) аЬВ СВС (аВС' ! аС' С' — АСВС' ( АВ'СВС' ( СС' ( АСВ ) АВ'СВ (С ( ) Интересный частный случай не леворекурсивной грамматики †граммати в нормальной форме Грейбах. Определение. КС-грамматнка 6=(Х, Х, Р, 5) называется грамматикой в нормальной форме Грейбах, если в ней нет е-правил и каждое правило нз Р, отличное от 5 — е, имеет вид А — аи, где а ба.
и аЕ Я ". Если грамматика не леворекурсивна, то на множестве ее нетерминалов можно определить естественный частичный порядок. Этот частичный порядок можно вложи~ь в линейный порядок, полезный при преобразовании грамматики к нормальной форме Грейбах. Лемма 2.19. 1»усть 6 === (Я, г., Р, 5) — не леворекурсивная грамл~атика.
Суи(ествует такой линейный порядок < на 14, что если А — Ва принадлежит Р, то А < В. Доказательство. Пусть )т — такое отношение на Ь(, что А)ТВ тогда и только тогда, когда А=О' Ва для некоторого а. Так как грамматика 6 не леворекурсивна, то Я--частичный порядок (транзитивность легко доказывается). Отношение можно расширить до линейного порядка <, обладающего нужным свойством (см. алгоритм 0.1). Г) 18» А л г о р н т м 2.14. П р е о б р а з о в а н и е к н о р м а л ь н о й форме Грейбах.
Вход. Не леворекурсивная приведенная КС-грамматика 6 = (Ь), Е„Р, В). Выход. Эквивалентная грамматика 6' в нормальной форме Грейбах. Метод. (1) Построить с помощью леммы 2,16 такой линейный порядок < на ч, что каждое А-правило начинается либо с терминала, либо с такого нетермипала В, что А < В. Упорядочить 1х = (А„..., А„) так, что А, < А, «...
А„. (2) Положит™ь с' — и — 1. (3) Если 1=-0, перейти к шагу (5). В противном случае заменить каждое правило вида А, — А,а, где 1') 1, правилами А,.— (),и(...((),„а, где Ат — (),(, (И3 — все А,-правила. Позже мы убедимся, что каждая из непочек 5„..., Гз начинается терминалом. (4) Положить 1=1 — 1 и вернуться к шагу (3). (5) Сейчас правая часть каждого праввла (кроме, возможно, 5- е) начинается терминалом.
В каждом правиле А- аХ,...Х заменить Хт Е Х новым нетермнналом Х;. (6) Для новых нетермнналов Х~, введенных на шаге (5), добавить правила Х; — Х . П Теорема 2.19. Если Š— КС-язык, то Е=-Е(6) для некоторой грамматики 6 в нормальной форме Грейбах, Доказательство. Индукцией по а — 1' (т. е. по 1, но в обратном порядке, начиная с ~'=-н — 1 и кончая 1'=1) можно показать, что после выполнения шага (3) алгоритма 2.14 для ( правая часть каждого Акправила начинается терминалом.
Ключевой момент здесь †использован линейного порядка После шага (5) грамматика преобразуется к нормальной форме Грейбах и по лемме 2.14 порождаемый ею язык не изменится. Д Пример 2.29. Рассмотрим грамматику 6 с правиламн Š— Т(ТЕ' Е + Т(+ТЕ т Р,'РТ' Т'- ВР)»РТ' Р— (Е) (а Т<Р, Упорядочим нетерминалы следующим образом: Е' < Е < Т' < 183 ГЛ. 2. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЫКОВ Правая часть каждого Р-правила начинается терминалом, как и должно быть, так как Р— наибольший нетерминал в этом упорядочснии. Предшествующий ему нетерминал Т имеет правила Т вЂ” Р(РТ', так что, заменив в них Р, получаем à — (Е) ( а ~ (Е) Т' ! аТ'. Переходя к Т', обнаруживаем, что здесь ничего менять не надо. Затем заменяем Е-правила правилами Š— (Е)(а/(Е)Т'/аТ'/(Е) Е'(аЕ'((Е) Т'Е'(аТ'Е' В Е'-правилах ничего менять не надо.
На шагах (6) и (6) появляются новый нетермпнал )' и правило )' ), поэтому все вхождения ) в предыдущих правилах надо заменить на )'. Таким образом, в результате получится грамматика в нормальной форме Грейбах с правилами .Е (Е)' (а )(Е)'Т' '!аТ' !(Е)' Е' ! аЕ' ! (Е)'Т'Е' ~!аТ'Е' Е' — « -4с Т !+ ТЕ' Т вЂ” (Е)' ! а ) (Е)' Т' ( ОТ' Т' — «Р) «РТ' Р— (Е)' (а )' — +) П Недостагок описанной техники преобразования грамматики к нормальной форме Грейбах в том, что она дает много новых правил. Чтобы не вводить слишком много новых правил, можно применить другой метод, который излагается в следукхцем разделе. Однако он может давать болыпе нетерминалов. 2А.5.
Другой метод преобразования н нормальной форме Грейбвх Изложим другой способ построения грамматики, в которой каждое правило имеет внд А аа. Здесь грамматика псрспясывается только один раз. Пусть 6=(.'ч, Х, Р, 3) — КС-грамматика, в которой нет е-правил (даже вида 5 — е) и цепных правил. Вместо того чтобы оппсывагь этот метод в терминах правил, воспользуемся системами определяющих уравнений того типа, что был введен в разд.
2.2.2. Например, множество правил А — АаВ (ВВ) Ь В аА(ВАа)Вй(с можно представить в виде системы уравнений А =-АаВ+ВВ+Ь В =- аА + ВАа+ Вй+с где А и  — неизвестные, представляющие множества. 2.4. КОНТЕКСТ!Ю-СВОБОДНЫЕ ЯЗЫКИ Определение. Пусть Л и Š— два непересекающихся алфавита. Системой определяющих уравнений в алфавитах Х и Л назовем систему уравнений нида А = а, + а«+... +а„, где А Е Л и а4Е(Л!)Х)*.
Если й=«0, то уравйение имеет вид А — 8. Для каждого А ЕЛ в системе есть одно уравнение. Ре!иением системы определяющих уравнений назовем такое отображение Г' множества'Л в 5! (Х'), что если подставить Г (А) в каждое уравнение вместо каждого А ЕЛ, уравнения станут равенствами. Решение ! Назовем наименьшей неподвижной точкой, если !'(А):— =д(А) для любого решения д и любого А ЕЛ. Чтобы получить КС-грамматику, соответствующую системе определяющих уравнений, надо для каждого уравнения А — —— =- а,+...
+а» построить правила А — а, !а,(...(а». Нетерминалами будут символы алфавита Л. Очевидно, что это соответствие взаимно Однозначно. Г!риведем несколько результатов о системах определяющих уравнений, обобщающих результаты о стандартных системах уравнений с регулярными коэффициентами (частном случае систем определиющих уравнений), Доказательства оставим в качестве упражнений. Лемма 2.17. Наименьшая неподвижная точка систе,чы определяющих уравнений в алфавитах Л и Х единственна и ил!ест вид !' (А) =- (ш ! А =:>о ш и и Е г *), где б — соответствующая КС-грамматика. Доказательство. Упражнение.
с! Мы будем пользоваться матричным представлением систем определяющих уравнений. Допустим, что Л =(А„А„..., А„) Матричное уравнение А=«Ай+В представляет п уравнений. Здесь А — вектор-строка [А„А„ ..., А„1, (х †матри порядка п, элементами которой служат регулярные выражения, и  — вектор-строка, состоящая из и регулярных выражений. В качестве «скалярного» умножения возьмем конкатенацию, а в качестве сложения — операцию + (т.
е. объединение). Сложение и умножение векторов и матриц определяются, как обычно. Элементом матрицы 2(, стоящим в 4-й строке и )им столбце, будет регулярное выражение а,+... +а„, если А4а„... „А а»вЂ” все члены уравнения для А,, первым символом которых является А, В качестве )сй компоненты вектора В возьмем сумму тех членов уравнения для Аэч которые начинаются символом из множества Х. Таким образом, Вт и )с47 — такие выражения, что уравнение для АТ (в КС-грамматике ему соответствует множе- 185 Гл. 2.
Элементы теОРии языггов ство А -правил) можно записать в виде Ал— .— АгПгл+А2Пгл+... +Аг)717+... +Ачй„+Вл где  — сумма выражений, начинающихся терминалами. Система определяющих уравнений (2.4.5) примет вид Теперь для матричного уравнения А==-Ай+В найдем такую эквивалентную систему определяющих уравнений, что все правые части соответствующих ей правил начинаются терминальными символамн. Этот переход основан на следующей лемме: пений. Лемма 2.18. Пуслгь А.=А!4+ — система определяющих р ". Тогда ве наименьшеи неподвижной точкой будет А —. В!4*, — у ав.
+ К+ П + П, ..., 1 — гдиничнан матрица (г на диагонали и В' — в остальных мгспгах), В"-=- В)1, Гт' =В14К и гп. д. Доказательство, Упражнение. () мат ич Если положить П~ = ПВ*, то наименьшую неподвгж ную точку А=-В е р ного уравнения А = АВ !- В можно зацисат ь в виде — (П +1)=-Вгг +В1=ВК'+В. К сожалению, для этой яв системы нельзя найти соответствующую грамматику: она н ляется системой определяющих уравнений, так как элементы е матрицы В" могут быть бесконечными суммами членов исходных уравнений. Однако К~ можно заменить новой матрицей „неязвестпых" 0 О, каждый элемент уг, которой, расположенный в г-й строке и )чм столбце,— это новйй символ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
