Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 98
Текст из файла (страница 98)
Проблема для исследования 5.3.26. Найдите преобразования, позволяющие превращать грамматики в грамматики простого или слабого предшествовання. Открытая иробле.на 5.3.27. Порождается ли каждый язык простого предшествования грамматикой простого предшествоваиня, у которой начальный символ не встречается в правых частях правил? Хорошо, если бы это было так, ибо в противном случае мы могли бы пытаться сделать свертку, когда в магазине 55, а па входе 5. 479 — .кьм ЛИЛЛИЗ Бнз нозпнлтон Элс ДРУГИН КЛЛСГЫ ГРЛММЛТИК Упражнения иа пролраммирование 5.3.23. Напишите программу, строящую отношения предшествования Вирта — Вебера для КС-грамматики б. Примените Вашу программу к грамматике языка ПЛ 360, данной в приложении.
5.3.29. Напишите программу, строящузо для входной КС- грамматики б алгоритм разбора типа,,перенос — свертка", если б — грамматика простого предшествования. Примените Вашу программу к построению анализатора для языка ПЛ 360. 5.3.30. Напишите программу, проверяющую, является ли грамматика обратимой грамматикой слабого предшествования, 5.3.3!. Напишите программу, строящую алгоритм разбора типа „перенос — свертка" для обратимых грамматик слабого предшествовация.
Замечания по литературе Разбор методом „перенос †сасрт" появился зперные н работе Флойда [1961[ В трактовке этого метода мы следозалн статье Ахо н др. [1972). Грамматнкн простого предшестпонапня были определены Внртом н Вебером (1966) н независима Паром [1904). Метод простого предшсстнозаннн пспользонался з компиляторах для нескольких языков, зключая Еп1ег [Внрт н Вебер, 1966[, Алгол ЪЧ (Бауэр н др., 1968[ н ПЛ 360 [Внрт, 1968[.
Фншер [1969) доказал, что каждый КС-язык, не содержащий е, порождается (не обязательно обратимой) грамматикой предшестнонання (упр, 6.3.19). Расширенное предшестаонанне было предложено Внртом н Вебером. Гпзй [Г969) уназал, что некоторые нз ранних определений рас~пнренного предшестнонання некорректны.
Прн т Ра > 3 расшнрепное (т, л)-предшестэонапне, по-знднмому, прнпесет на практике мало пользы нз-за большнх затрат памятн. Методы сокращения объема таблицы аналнзатора расшнренного предшестнозання научал Мак-((ннан (1966). Грэхем (19?О[ доказала ннтересную теорему о том, что каждый детермнннроааппый нзык определяется обратнмой граммзтнкой (2,1)-прсдшестноэання. Грамматнкн слабого предшестнозання насдены Р)хбна н Морзе [1970). Теорема 6,19 взята нз статьи Ахо н др. [1972). Для анализаторов типа „перенос — свертка' нозмажны несколько схем нспраяленнн ошибок.
В ходе разбора этого типа можно объявить об ошнбке как н фазе переноса, так н з фазе свертки. Если об ошибке сообщает функ. цня переноса„то можно попытаться делать изменения, вставки нлн удаленнж как прн (.ь- нлн Е((-разборе. Если ошибка встречается прн свертке, то можно использовать заранее составленный список ошнбочных праннл, прнмепяя его к верхней части магазнна.
Техника нспразлення ошибок для грамматнк простого предшестнанання рассматривалась Внртом [1968[ н Лейннусом [1970['). Чтобы усилить способ. ность аналнзатора простого предшестзонання обнаруживать ошибки, Лейннус предложнл, а частности, проверять после тою, как сделана свертка, пыпол няется лн допустимое отношенне предшестаонзння между гнмаоламк Х н 4 где А — новый нетерчннал нааерху магазнна, а А' — снмзол, расположенный сраау под ннлс >с. и г, ~~л, т гам а~я.— лл 5,4.
ДРУГИЕ КЛАССЫ ГРАММАТИК, АНАЛИЗИРУЕМЫХ МЕТОДОМ нЛЕРЕНОС вЂ” СВЕРТКАн Рассмотрим еще несколько подклассов [.[(-грамматик, для которых существуют алгоритмы синтаксического анализа типа перенос — свертка". Это грамматики ограниченного правого контекста, грамматики смеп1анного предшествования и грамматики операторного предшествования. Мы рассмотрим также язык Флойда — Эванса, который по существу является языком программирования, предназначенным для записи алгоритмов детерминированного разбора, 5.4А. ГРамматики ограниченного правого контекста Хотелось бы расширить изученный выше класс грамматик слабого предшествования, ослабив требование обратимости. Совсем устранить зто требование нельзя, так как экономный алгоритм разбора для класса всех грамматик предшествования не известен.
Но многие грамматики можно анализировать, используя слабое предшествование для локализации правого конца основы, а затем, если грамматика не является обратимой, с помощью локального контекста найти левый конец основы н определить, каким не- терминалом ее заменить. Широкий класс грамматик, анализируемых подобным способом, образуют грамматики (гп, п)-ограниченного правого контекста (ОПК).
Неформально 6=([З[, Х, Р, 5) будет (т, п)-ОПК- грамматикой, если для каждого правого вывода 5' =:;ь," ссА ш =>, сфгп в пополненной грамматике 0'=(Н()(5'), 2, Р()(5' — 5), 5') основу р и правило А — р, применяемое для свертки основы в цепочке сг[)и!, люжно однозначно определить так: ()) Цепочка а[)гп просматривается слева направо, пока не будет прочитана основа. (2) Решение о том, является ли б основой цепочки а!3пз, где Тб — префикс этой цепочки, принимается только по цепочке 5, т символам слева от б и и символам справа от 5. (3) В качестве основы из кандидатур, предложенных в (2), выбирается самая левая подцепочка, расположенная справа от самого правого нетерминала цепочки сгргп или включающая его. Для удобства обозначений будем добавлять к каждой право- выводимой цепочке т символов 3 слева и и символов 3 справа.
Тогда можно быть уверенным в том, что в расширенной таким образом правовыводимой цеиочкс всегда найдутся по крайней мере пг символов слева от основы и и символов справа. 16 Л„дхо, Дж. Ульмая, т. ! 481 ГЛ. 3. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ ЛНЛЛИЗ БСЗ ВОЗВРАТОВ БН. ДРУГИВ КЛЛССЫ ГРЛММЛ ГИК Определение. 6=(Ь), .й, Р, В) называется грамматикой (т, п)- ограниченного правого контекста (ОПК)„если из условий (1) $а5'$л=:>г, аАш=)о,,сфе и (2) йаВ'5л =Зо „уВх ==.>В 75х = а'()у — правые выводы в пополненной грамматике 6' = (1ч' 11 (5'), Х, Р (1 (Я' — В), Я'), (3) |х! ='(у1, (4) последние т символов цепочек а на', а также первые н символов цепочек ш и у совпадают вытекает, что а'Ау=уВх, т, е.
а'=у, А =В и у=х. Грамматика называется ОПК-грамматикой, если она является (т, н)-ОПК-грамматикой для некоторых т и и. Если мы считаем вывод (2) „настоящим", а (1) рассматриваем как возможную причину недоразумения, то условие (3) гарантирует, что левее „настоящей" основы б не встретится подцепочки, которую можно было бы принять за основу (р, окруженную последними т. символами цепочки а н первыми н символами цепочки ш). Следонательио, в качестве основы можае выбирать самую левую цепочку, которая „выглядит как основа". Условие (4) гарантирует, что решение о том, является лн цепочка основой, можно принять, привлекая лишь т символов левого контекста и и символов правого контекста. Как и для 1 Й (Ь)-грамматик, пополненная грамматика включается в определение только на тот случай, когда В встречается в правой части какого-нибудь правила.
Например, грамматика 6 с двумя правилами В- Ва)а без оговорки относительно пополненной грамматики была бы (1,0)-ОПК-грамматикой. Но так же, как в примере 5.22, ие заглянув на один символ вперед, нельзя решить, как поступить с В в правовыводимой цепочке Ва. Поэтому мы не хотим считать 6 (1,0)-ОПК-грамматикой.
В дальнейшем мы докажем, что каждая (т, Ь)-ОПК-грамматика является 1К(Ь)-грамматикой. Но не для каждой 1й (О)- грамматики найдутся такие числа т и н, чтобы она была (т, н)- ОПК-грамматикой, потому что 1.1(-определение позволяет, говоря неформально, использовать в ходе разбора для принятия решения весь кусок правовыводимой цепочки слева от основы, а ОПК" определение ограничивает нас т символами. Разумеется, оба определения ограничивают использование части цепочки, расположенной справа от основы.
Пример 5.41. Грамматика б, с правилами 3 — аАс А — АЬЬ(Ь является (1, 0)-ОПК-грамматикой. Правовыводимые цепочки (отличные от Я' и В) имеют вид аАЬР"а илн аЬВл"г для н) О. Основами могут быть только аАс, ЛЬЬ и Ь, так что основу любой правовыводимой цепочки можно однозначно определить, про. сматривая зту цепочку слева направо, пока не встретится цепочка аАс илн АЬЬ либо символ Ь, слева от которого стоит а.
3аметим, что ии один из символов Ь в цепочке ЛЬЬ не может быть основой, поскольку слева от него стоит А или Ь. С другой стороны, грамматика 6, с правилами  — аАс А — ЬАЬ) Ь порождает тот же язык, но опа даже не (.К-грамматика. Г3 Пример 5.42. Грамматика б с правилами В- аА (ЬВ А — -ОЛ (1  —,ОВ(1 является 1.К (0)-, ио пе ОПК-грамматикой, так как в правовыводимых цепочках аО"1 и ЬО" 1 основой служит 1, но для выяснения того, какое из правил А — 1 и В 1 применить для свертки основы, недостаточно знать ограниченное число символов, расположенных непосредственно слева от 1. Для формального доказательства рассмотрим выводы 3аВ~Ьл .-Ф" чллаОаА3л =-> бтаОа1$л $тЯ 3л — ~ *$аЬОаВ$л — ~ с)тЬОа1$л По определению ОПК-грамматики а=-$таОт, а'=у=3аЬОа, р=-5=1 и у=ш- Х=Ьл.
Тогда я и а' оканчиваются одними и теми же т символами 0"', ю и у иачипаючся п символами и )х(()у), но а'Ау~ уВх (А и В соответствуют в ОПК- определении сами себе). Грамматика с правилами  — аА (ЬА А- ОА)1 порождает тот же язык и является (О, 0)-ОПК-грамматикой. Условие (3) в определении ОПК-грамматики может сначала показаться лишним. Но именно оно гарантирует, что если в правовыводимой цепочке а'()у самой левой подцепочкой, совпадающей с правой частью некоторого правила А — 13, является 13 и 1бл фвз ГЛ. К ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ она имеет в а'ру корректные правый и левый контексты, то получающаяся после свертки цепочка а'Ау будет правовыводимой. ОПК-грамматики связаны с некоторыми из исследованных в этой главе классов грамматик. Как уже упоминалось, они образуют подмножество 1К-грамматик.
Кроме того, это грамматики расширешюго предшествования, и каждая обратимая грамматика (т, и)-предшествования является ОПК-грамматикой. Класс (1,1)-ОПК-грамматик содержит все обратимые грамматики слабого предшествования. Докажем сначала последнее утверждение. Теорема 5.20. Если 6=( ч, Т, Р, В) — обратимая грамматика слабоео иредшествованил, то она является (1,1)-ОПК-грамматикой. Дока з атель ство. Допустим, что (1, 1)-ОПК-условие нарушается, т. е. существуют два вывода 6В'5 =>," аАш ~, арГс $Я'$ =;>," уВх =)„убх = а'(3у в которых а и а' оканчиваются одним и тем же символом, ш и у начинаются одним и тем же символом и (х!:)у), но уВХФ а'Ау.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
