Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 96
Текст из файла (страница 96)
Так как по предположению Х вЂ” терминал, то из С после нескольких шагов вывода (5.3.2) должна получиться цепочка 7)г для некоторых 77Е)ч) и е Е(!ч ОХ)". Далее, 0 заменяется цепочкой Х,О, и по правилу (2б) отсюда следует требующееся отношение Следствие. Если в теореме 5.17 6 — грамматика (т, и)-пред- шествования, то теорему можно усилить, добавив к каждому из утверждений (1) — (4) слова о том, что между соответствую- и!ими цепочками не выполняются никакие другие отношения. гл Алгоритм разбора типа „перенос-свертка" для обратимых грамматик расширенного предшествования полностью аналогичен алгоритму 5.12 для грамматик простого предшествования, так что мы только вкратце скажем о ием. Первые и необработанных входных символов можно хранить наверху магазина.
Если такими символами являются а, ... а„и непосредственно под ними в магазине расположена цепочка Х„... Х„причем Х„... Х,А а,... а„или Х ... Х,(а,... а„, то надо сделать перенос. Если же Х ... Х,~а,... а„, то делается свертка. Утвержде. нне (1) теоремы 5.17 гарантирует, что один из первых двух случаев пронзондет всегда, когда основа лежит вправо от Х,. В силу утверждения (4) этой теоремы правый конец Основы достигается тогда и только тогда, когда происходит третий случай. 44а Чтобы сделать свертку, надо так же, как в алгоритме 5.12, вернуться назад, проходя через отношения '., в поисках отноп|ения (. Из утверждений (2) и (3) теоремы 5.17 вытекает, что основа будет выделена правильно.
Е.З.4. Граммвтини слабого предшвствоввния Многие естественно встречающиеся грамматики не являются грамматиками простого предшествоваиия, и попытки найти для данного языка грамматику простого предшествования часто приводят к довольно неуклюжим грамматикам. Можно расширить класс грамматик, анализируемых методом предшествования, ослабив ограничение, что отношения ( и ' не должны пересекаться. Отношение > по-прежнему будем использовать для локализации правого конца основы. Тогда для локализации левого конца основы можно использовать правые части правил, подыскав среди них такую, которая совпадает с символами, стоящими непосредственно слева от правого конца основы. Это не намного более трудная работа, чем разбор методом простого иредшествовання.
В ходе разбора для грамматики простого предшествовапия после выделения Основы все равно требуется определить, какое именно правило применить для свертки, так что эти символы так или иначе придется рассматривать. Для того чтобы эта схема разбора работала, надо уметь определить, какое правило применить в том случае, когда правая часть одного правила является суффиксом правой части другого правила. Например, пусть ирубо — правовыводимая цепо ~ха, в которой правый конец основы лежит между у и бо. Если А- у и  — ру — два разных правила, то не ясно, какое из ннх нужно применить для свертки.
Мы ограничимся применением самого длинного из применимых правил. Класс грамматик, для которых такое решение Оказывается правильным, образуют грамматики слабого предшествовання. Определение. Пусть 6=( ч, г.„р, В) — приведенная КС-грамматика без е-правнл. Назовем 6 грамматикой слабого предшествования, если (!) отношение ) не пересекается с объединением отношений ( и (2) для А иХр и В р из Р, где ХЕ)Ч)02, ие выполняется ни Х «В, ни Х вЂ” 'В. 4вэ ГЛ. 3. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ гРАммАТИкИ ПРЕДШЕСТВОВАНИЯ Пример 5.37. Примером грамматики слабого предшествовання может служить грамматика 6') с правилами Š— Е+Т)+Т) Т Т- Т»Р)РР— (Е) )а Матрица предшествования для 6 приведена на рис. 5.14. Заметим, что конфликты возникают только между отношениями ( и ", так что условие (!) определения грамматики слабого предшествования удовлетворяется.
Чтобы убедиться, что Е Т Е а ( ) ч ч й ис. 5.14. А(атрнца предшествовзния. условие (2) тоже не нарушается, рассмотрим сначала три правила Š— Е+Т, Š— +Т и Е- Т'). Из матрицы предшествования видно, что между Е и Е, а также между + н Е (т. е. когда + рассматривается как левый аргумент Отношения) нет никакого отношения предшествования. Таким образом, зти три правила не нарушают условия (2). Остальные правила, в которых одна правая часть служит суффиксом другой,— это Т Т:Р н Т вЂ” Р. Так как между» и Т нет отнопгения предшествования, 1 >~ . Р а '", а Ь чикой бм В самом деле, язмк Е(С) — еао Е(ое) с лишними унарнмми з«з кими +, как, например, в цепочке +ач( Еа-(-а).
Грзммвтикв ое — то>не обратимая граммзтнкв слабого предшествования, но не грамматика простого предшествования. ') Случайно этн три правила имеют одну и ту кге левую часть. 470 и здесь услов л вне (2) нс наРУшено. Итак, 6 — гРамматика слабого предшествования. Хотя ие яв, 6 является грамматикой простого предшествования, она порождае ает язык простого предшествования.
Позже мы увиим, что это верно в в но всегда, т. е. каждая обратимая грамматика б е шествования порождает язык простого предшествосла ого ПР д ванна. П Убедимся теперь в том, что в правовыводимой цепочке грамматики ела О б го предшествования основой всегда будет самая длинпая из правых частей применимых правил. Лемма .. усо ь Л 5.4. Пусть 6=(Х, 2, Р, Б) — гралглгатикаслабогопред' Си>=> >иествования и с во ания и Р содержит >гравило  — 5. Пусть 555~,'у и» с 5Х()ш, Если существует правило А — яХ5, то последнии в вт олг выводе применялось не правило В- Доказательство. Допустим, что, напротив, С=В и у=бХ.
Применив теорему 5,14 к выводу В~",уСИ>, получим Хст В или Х В. Это следует из того, что основа цепочки уСи> оканчивается где-то правее символа С, и, значит, С вЂ” один из символов Х, теоремы 5.14. Но тогда сразу нарушается условие слабого предшествовання.
(з Лемма 5.5. Пусть 6 — такая же грамматика, как в лельке 5.4, и >густо она х тому же обратимая. Если правила види А- яХР нет, то в выводе $55=Р'„уСш=>„ба>в должно быть С=В и у=бХ (т. е. последним применяется правило В 5). Доказательство. Очевидно, что на последнем шаге заменяется символ С. Левый конец основы цепочки бХ))и> ве может быть левее символа Х, так как нет правила Л вЂ” яХ5. Если основа оканчивается где-то правее первого символа цепочки 5, то нарушается лелгма 5.4, в которой В- 1) играет роль правила А — яХ().
Поэтому основа — цепочка 5, и нужный резулыат следует из Обратимости грамматики 6. ( ) Итак, сущность алгоритма разбора для обратимых грамматик слабого предшествования заключается в следующем. Мы просматриваем правовыводнмую цепочку (ограниченную концевыми маркерами) слева направо до тех пор, пока впервые ие встретим отношение ). Это отношение указывает правый конец Основы. Затем по одному рассматриваем символы слева От ). Допустим, что есть правило  — 5 и слева от ) оказывается цепочка Хб. Если правила вида Л вЂ” яХ)) пет, то по лемме 5.5 5 — основа. Если такое правило есть, то по лемме 5.4 правило  — 5 неприменимо, Следовательно, решение о том, свертывать ли р, можно принять, Рассмотрев только один символ слева От 5.
471 гл. а. однопроходный синтаксический Анализ ввз возвратов а.а. ГРАмматики пРедшсствования Таким образом, для каждой обратимой грамматики слабого предшествовапия можно построить алгоритм разбора типа „перенос — свертка". Алгоритм 5.!4, Построение алгоритма разбора типа „перенос — свертка" для грамматик слабого п р е д ш е с т в о в а н и я.
Вход. Обратимая грамматика слабого предшествоваиия 6 =(1а, к, Р, В), правила которой занумерованы числами от 1 до р. Выход. л4=-(1, я), алгоритм разбора типа „перенос — свертка" для грамматики 6. Метод. Построение аналогично тому, которое было в алго- ритме 5.!2. Функция переноса 1 определяется прямо по отноше- ниям предшествования: (1) 1(Х, а) =перенос, если Х (а или Х ' а, (2) 1(Х, а) =-свертка, если Х)а, (3) ~ ($5, 3) =допуск, (3) 1(Х, а)--ошибка в остальных случаях. Функция свертки 8 определяется так, чтобы при свертке применялось самое длинное из применимых правил: (4) и(Х5) =1, если В- )) — правило нз Р с номером 1 и в Р пет правила вида А — аХр, (5) а(сс) =-:ошибка в остальных случаях. Теорема 5.18. Алгоритм 5.14 строит корргктный алгоритм разбора типа „перенос — свертка" для гралалгатики 6. Доказательство.
Теорема непосредственно следует из лемм 5,4 и 5.5, определении обратимой грамматики слабого пред- шествования и конструкции самого алгоритма А. () С помощью некоторых преобразований можно устранить нз грамматики имеющиеся в пей конфликты между отношениями предшсствования. Приведем здесь несколько полезных преобра- зований такого рода, которые часто позволяют переделать грам- матику, ие обладающую нужными свойствамн преднГествования, в эквивалентную грамматику (1,1)-предшествовання илн слабого предшествования.
Допустим, что в грамматике есть конфликт вида Х.— '1' и Х ) У. Так как Х ' )', то в правой части одного или несколь- ких правил встречается подцепочка ХУ. Если в таком правиле заменить Х новым нетермииалом А, то Х ° !' исчезнет и тем самым конфликт будет устранен. Чтобы сохранить эквивалент- ность, добавим к грамматике правило А — Х. Если Х не является правой частью другого правила, то сохранится и обратимость грамматики. Пример 5.38. Рассмотрим грамматику 6 с правилами Я вЂ” 0311 ! 011 В примере 5.35 мы видели, что 6 ие грамматика простого пред- шествования, потому что 1 ' 1 и 1)!.
Однако, если в каждое правило вместо первой единицы поставить новый нетерминал А о 4 0 ! е' Рис. о,!З. Отношения предшеетаованая для грамматики й". и добавить правило А — 1, то получится грамматика простого предшествования 6' с правилами  — ОВА1) ОА1 А — а! Отношения предшествования для этой грамматики приведены иа рис. 5.15 () Аналогичными преобразованиями можно устранять конфликты вида Х -'У, Х >У (а также вида Х ° У, Х ' У, если желательно простое предшествоваиие).
В тех случаях, когда эти преобразования нарушают обратимость, можно попытаться устранить конфликт, удаляя правила, как в лемме 2.14. Пример 5.39. Рассмотрим грамматику 6 с правилами Е Е+Т) Т Т- ТаР)Р Р а)(Е) (а(Е) Е- Е, Е!Е В этой грамматике нз Е выводятся списки выражений, а переменные могут иметь индексы, представляющие собой произвольные последовательности выражений. 6 не является грамматикой слабого предшествования, так как Е ) н Е >). Можно было бы устранить этот конфликт, заменив Е в правиле Р— (Е) на Е' и добавив правило Е* Е. 4.3ь ГРАммАтики пьедшествовлния Š— Е+Т'1 Т Р а)(Е))а(Е, Е)(а(Е) Е Е, Е~)Е 474 гл. к однопгоходныя синтхксичвския анализ вез возвгхтов Но тогда оказалось бы два правила с правой частью.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
