Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 28
Текст из файла (страница 28)
Искл8оченне из ЕЦй) грамматики г-правил. Вход ЕЕ(й)-грамлсатнка 6,=(Хс, 2, Р„В,). Выход. Е1.(й+1)-грамматика 0=(Х, 2, Р, В), для ко~арой 1(6) =Ц6,) — [Е). Мгт д. (1) Сначала воспользуемся алгоритмом 8.1 для построения 1.1ф) грамматики 0,=(ХО 2, Р„ВТ), удовлетворяющей усло- вию (8). (2) Искгпочим из 6, асс негерминалы Л, из которых вы- водятся только пустые цепочки, выбросив А из правых частей правил, где они встречаются, а затем исключим все А-правила. Обозначим полученную грамматику 08 — — (Хл, Е, Ри Вс). (3) Построим граммапску 0 =(Х, 2, Р, 83 (а) Пусть Х вЂ” множество таких символов [Ха], что (8) Х--неисчезающий символ грамматики 6„ (11) а — цепочка исчезающих символов, (1!1) Ха 2 2 (т. е.
не может быть одновременно ХЕ 2 и а — — г), (]е) сс не имеет повторяющихся символов, (е) Ха действительно встречается а качестве надцепочки некоторой левовыводимой в 6, цепочки. сэ! гл л теОРия детагллнниеозяиного Рлзаоел лл. таоеня ль языков (б) 5=-[5,]. (в) Пусть д — такой гомоморфизм, что у([а]) =я для всех [а] из Ы, и пусть д(а) =а для а из Х. Поскольку ц '([3) содержит не больше одного элемента, мы будем писать непосрелственно у л(8), если у '([3) Ф кл. построим мно. жество Р так: (!) Пусть [Аа]ЕМ и А  — правило из Р,. Тогда [Ля] у '(йи) — правило из Р. (Ш Пусть [ааЛ(3]й)лд где або, А ЕХл.
Пусть А у— правило из р„причем у яе. Тогда [падр] ау л(у(3)— правило из Р. (1!!) 11усть [ааА8]6М, где аЕХ. Тогда [аиА(3] ив правило из Р. (З Пример 8.2. Рассмотрим грамматику из примера 8.1. Алгоритм 8.! в этом примере уже применялся.Шаг(2) алгоритма 8.2 не изменяет грамматики. Будем пора'кдать правила грамматики 6 по мере надобности, чтобы убедиться, что каждый рассматриваемый нетерминал встречается в некоторой левовыводимой цепочке. Началытым симвояом служит [5]. Существуют два 5-правила: с правой частью АВ и с правой частью В. Так как Л и  — неисчезагощие символы, а  — исчезающий, то у '(АВ) = [АВ] и у '(В)=.[В].
Следовательно, согласно пункту (П !нага (Зв), получаем правила [5]-[ЛВ]) [В] Рассмотрим нетерминая [ЛВ]. А имеет одно правило, а именно А аА. Так как у '(аАВ)=.[аАВ], добавим правило [ЛВ] [аАВ) Рассмотрев нетерыннал [В], добавим еше прапило [В]-[ЬА] Применим теперь к негеоминалу [аАВ] пункты (И) н ()!!). Для А и В существует по одному правилу, отличному оте-правила.
Так как у '(аАВ) =-[аАВ], добавим правило [аАВ] а[аЛВ] соответствующее А.правилу. Так как ц '(ЬА) =[ЬА], добавим правило [аАВ] а[ЬА] соответствующее В-провис!2. На шаге (Ш) добавится правило [аАВ] а Аналогично нетермипал [ЬА] дает правила [ЬЛ] — Ь [аА] [ Ь Рассмотрев затем новый нетермянал [оА], добавляем правила [аА] — а [аА] ) а Таким образом, для всех новых нетермннэлов введены правила, и построение грамматики 6 закончено. сЗ Теорема 8А. Грамматика 6, логтроенная по 6, алгоритмом 8.2, облодаепг следующими сеоастеимиг (1) (46) =ЬФ,) — [г), (2) если 6, — - Ы(Ь) граммалшка, пш 6 — )Л (Ь -1-1)-грамматика. Дока за тельство. Пусгь д — гомоморфизм, определенныв на шаге (Зв) алгоритма 8.2.
(1) по индукпнн непосредствеюло получаем, что л юь,р (где АРХ и 86(ХВХ)*) тогда и тояько тогда, когда д(А)=ьйд(8) н 8:мг. Следовательно, [Вл]аоою для ш из Х" тогда и только тогда, когда З,ЮЬ,ю н юФе. Значит, 1(6)3 В(бл). Равенство Е(6,) = Е(бл) — (е) представляет собой утверждение (1) теоремы 8 3, н легко видеть, что шаг (2) аягоритма 8.2, превраггшюший 6, в 6„ не изменяет порождаемого языка. (2) Второе свойство доказывается аналогично. По данному левому выводу в 6 найдем соответствующий вывод в 6, и по. кажем, что СВ(Д -1-1)-конфликт в первом вызывает Щй)-конфллгкт во втором.
Параметр Ь 1-1 вместо Д интуитивно можно обосно. вать так: если применяется правило грамматики 6, построенное на шве (Зв) ((!!) или (!1~)), то терминал а все егце остается частью аааннепочкн, когда нужно выяснить, какое правило применить для иА8. Допустим, что 6 пе является (.).(8+1)- грамматикой. Тогда существуют выводы 5 ~ог шА я юо, я()я аког юх 5'' >о~юдиЮогшуиЮЗгюу где р-ру, но ШКЗТ„„(х) =-Р1КЗТ,,(у). Построим ллоотвелсл. вующне выводы в бр (а) Веянии раз, когла применяется правило [Ла] у '(Ря), введенное в Р на шаге (Зв!), применяем правило Л й из 6,. (б) Всякий раз, когда применяется правило [аяЛ)3] ау-'()(3), введенное в Р на шаге (За!1), строим левый вывод е ива, после чего применнем правило А у.
(в) Всякий раз, когда применяется правило [ааАР] а, строим левый вывод е из аАЬ. Заметилк что этот вывод состоит не менее чем из одного шага, так как иАй чае. лл теОРия ль.языков !55 гл л, теогия двтгвминивовлнного влзвовл Таким образом, выводу 5~оПюАя соответствует единственный вывод у(5) йгюйг(А)у(а). Если А — заключенная в скобки цепочка символов, начинающаяся с терминала, например а, то рубежом' ) цепочки шд(А)у(я) служит символ, расположенный через один от т вправо.
В противном случае рубеж расположен непосредственно справа от ю. В обоих случаях, поскольку й, 1 символов цепочек х и у совпадают и б,— ББ(й)-грамлгат!гкв, шаги вьшода в б„соотвегствуюшяе применению правил А — р и А у в б, должны быть одинаковыми. Чтобы показать, что вопреки предположению должно быть 8 — 1, достаточно исследовать три различных источника появления правил грамыатикн6 н их связь с соответствующимв выводами в 6,.
Итак, пусть А=(6). Если 6 начинается с нетерминала, скажем 6 =66', то оба вывода строятся согласно пункту (а). Тогда в бл есть правило, скажем С 6", такое, что й — у —..8 '(6"6'). Если 6 начинается с терминала, например 6=.аб', то построение происходит согласно (б) или (в). Два вывода в 6, замсниюг некоторый префикс цепочки 6 на е, а затем применяещя правило, отличное от е-правила, из пункта (2б), Легко доказать, что в обоих случаях 3=у.
Г) Докажем теперь, что каждый БЦА)-язык порождается ЕЕ(й —,!)- грамматикой в нормальной форме Грейбах. Эта теореыа находит важные применения, мы будем использовать ее для получения дальнейших результатов. Предварительно докажем две леммы. Лемма 8.3. ! Цй)-грамматика не может быте лгеорекурсиенсэ. Доказательство. Предположяч, что 6=(Х, Х, Р, 5) имеет леворекурсивный нетерминал А. Тогда существует вывод А сэ' Ая.
Если я~*е, то легко показать, что б неоднозна ша и, значит, не может быть БЦграмматикой, Поэтому будем считать, что а ~*в длн некоторой цепочки в Е Х . Можно далее предположить, что А -*а для некоторой цепочки иЕХ" н существует вывод 5 ю! юА6 ю', шАа'6 ю,' юко'х Следовательно, существует н вывод 5 ~) юА6 го;юАлб ~;шАяет6 ~;висл 'х Так как Р!ЙБТл(ивлх)Г-Е1ЕБТл(исл *х), то для любого й приходим к противоречию с определением ЕЦй)-грамматики.
Лемма 8.4. Пуспа б= (Х, Х, Р, 5) — КС-граммапшка, у кс. торой е множестве Р есть привело А Ва, где В 6Х. Пусть В-- !)л(бл(...(()„— все В-правила ерамматккк 6, а 6,=(Х, Х, ') Определение псезткя рубеже си. э равд. 5.!.!. Р„5) — грамматика, позученнал е резутгпате удаление яз Р правила А Ва и замены его правилами А й,а(йла),,, (йяа. Тогда Цб,) р 8(6), и если 6 — ЕЦй).грамматика, то и 6,— тоже ЕЦй)-грамматика. Доказательство. Согласиолемме2.!4, Цб ) 6 Е(6). Чтобы показать, что Щй)-свойство сохраняется, заметим, что левые выводы в 6, по существу совпадают с левыми выводами в б, за исключением того, что последовательное применение правил А Вя и В В, в грамматике б осуществляется теперь за одна шаг.
Говоря неформально, поскольку Ва начинается с не- терминала, два шага вывода в грамматике 6 вызваны одной и той же й-сичвольной аванцепочкой. Поэтому при разборе в соответствии с грамматикой 6, эта аванцепочка заставляет при. мецить правило А ()гя. Более подробное доказательство предлагаем в качестве упражнения. С) Алгоритм 8.3. Преобразование БЕ(й)-грамматики в !Х(64-!).грамматику в нормальной форме Грейбах, Вход. 1Л.(й)-грамматика бг=(Хо Х, Р„5,). Вьяод. ББ(й+1)-грамматика 6 =(Х, Х, Р, 5) в нормальной форме Грейбах, для которой Цб)=ЦП,) — (е). Метод.
(1) С помощью алгоритма 8.2 построить ао бг Ы.(6+1) грамматику 6,=(Хм Х, Р„5), не содержагцую е-правил. (2) Перенумеровать не!ерманалы из множества Х„скажем Х, =-(А„ ..., А„), так, чтобы выполнялось условие; если А, А,я принадлежит Р„ то !Р г. Согласно лемме 2.18, это лгожко сделать, так как по лемме 8.3 грамматика б, не лево. рекурсивна. (3) Для 1 =т — 1, т — 2, ..., 1 последовательно заменить все правила вида Аг Агя темя из правил вида А, йя, для которых Аг В уже отйесено к числу новых правил. Мы покажем, что эта операция приведет к тому, что у всех правил правые части будут начинаться с терминалов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
