Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 103
Текст из файла (страница 103)
УА СА ,ба д ... бт ~ у, ... уаХб„ ... б, где на каждом шаге заменяется символ Сг, все бу принадлежат (е) 07 — Т н Х Е Т. Тогда Х в а. (4) Если В=э+ яХ5 и я Е (е) 0 7 — Т, то ф Х. Если 5Е(е)0)г — Т, то Х.>$. Заметим, что при Т=-А' получается определение отношений Операторного предшсствования, а при Т =- $' — отношений Вирта— Вебера. Пример 5.49. Рассмотрим грамматику 6, с множеством знаме. нательных символов б=(Р, а, (,), +, е). Йайдем, что ( ' ), так как (Е) — правая часть правила и Е не знаменательный символ. Далее, -!- ( е, так как существуют правая часть Е-)-Т и вывод Т вЂ” А+ ТеЕ', и Т не знаменательный символ.
Кроме того +) так как существуют правая часть Е+Т и вывод ЕееЕ+Т, и Т не знаменательный символ. Отношения б-канонического пред- шествования для 6„приведены на рис. 5.23. С) 5.4.29. Найдите все множества знаменательных символов для грамматики 6,. 5.4.30. Покажите, что А — множество знаменательных символов для 6 — --(г(, Аз Р, В) тогда и только тогда, когда 6 — грамматика операторного предшествовання. Покажите, что Р(0Х— множество знаменательных символов тогда и только тогда, когда 6 — грамматика предшествовани я. Определение. Пусть 6==(М, Х, Р, В) — Т-каноническая грамматика. Т-вставная грамматика для 6 получается заменой в правилах из Р всех вхождений символов из )г — Т новым символом В, и устранением правила Ве- В„ если оно при этом появилось.
а + * С > г Рис. о.аЗ. Отиогпеиии Ь-каиоиичеекого предгоестаоааиип. Пример 5.50. Пусть б то же, что и в примере 5.49. Тогда Л-остовной грамматикой для 6, будет Во 'Во+Во!Веер!Р Р (Ве) !а Б 5.4.31. Разработайте алгоритм разбора типа „перенос — свертка" для грамматик Т-канонического предшествования, имеющих абра. тимые Т-останные грамматики. При этом, разумеется, должны вырабатываться разборы, соответствующие остовной грамматике. Проблема для исследования 5,4.32. Разработайте преобразования, с помощью которых можно получать ОПК-грамматики, грамматики простого или операторного предшествования.
бгпразснения на программирование 5.4.33. Напишите программу, проверяющую, является ли данная грамматика грамматикой операторного предшествования. 5А.34. Напишите программу, строящую соответствующий анализатор для грамматики Операторного предшествования. Замечания по литературе 611 гл, з, ОднОпРОхОдный синтАксический Анализ Вез ВозВРАТОВ 5.4.35. Найдите грамматику операторного предшествования для одного нз языков, приведенных в приложении, н затем постройте для этой грамматики соответствующий анализатор. 5.4.36.
Напишите программу, строящую соответствующий анализатор для (1, 1)-ОПК-грамматики. 5.4.37. Напишите программу, строящую соответствующий анализатор для простой ССП-грамматики. 5.4.38. Определите язык программирования, в основе которого лежал бы язык Флойда — Эванса. Постройте для него компилятор. Различные методы разбора, арнентнрапаиные на предшеетэаэанне, при- менялись э самых первых компиляторах, Формализацияпанятняаператариага прелшестпаааиня принадлежит Флайду [1963).
методы, использующие огра- ннченный контекст н ограниченный правый контекст, были определены тоже а нзчале !960.х годов. Бальшннстаа ранних результатов, касаюшнхея раз- бора методам ограниченно!а контекста н ега вариантов, содержится и работах Эйкеля н пр. [1963], Флойда [!963, 1964а, 19646], Грэхема [!964], Лйранса [1964) я Пола [1962]. Прнэелениае и этом разделе определение ОПК.грамматики экэнпэлентна тому, которое дал Флойд [1964«). Лаке [!970) разработал алгоритм построения аналнзатараа для некатарык классов ОПК-грамматик. Вайз [197!] распро- странил алгоритм Дамйлкн на ОПК-грамматика. Смешанная стратегия предшестэааания была эаедена Маккиманам н прн, менена нм с соавторами [!970) э качестве основы енстемы построения кампн. лятараз ХИ., Язык Флойда — Ээанса- эта предложенная Эаансам [!964) мадкФнкацня языка, перэанзчальна ээедениага Флайпам [196!).
Фельдман [!966] испальза- аал ега а качестве основы системы построения компиляторов, названной языкам Формальной Семантики [Р31). Прн этом среди действий, экадящнх н операторы языка, могут быть общие семантические процедуры. Т-каноническое предшестпаэанне было пэелена Грэем н Харри«оном [1969), Пример 6,47 эзят нз книги Хапгуда 11969] '). з) Трэхтенгерц я Шумен [1971) обобщили идею прелшеетэоаання на не КС-грамматики. Трубчанннаэ [19761 обобщил понятие Т-кананнчеекага предшеетэаэаиня.
Интересный класс „строго детерминированных" грамматик паелн Харрисон н Хавел [1973, 19741 Этн грамматики порождают класс ЬК(0)-языкап, на алгоритм разбора для ннк не па«ходящий и не нисходящий, а обладает чертами обоих метадон.— Прим. перез. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ В настоящей главе мы изложим несколько алгоритмов синтаксического анализа, которые, подобно общим ннсходязцнм н восходящим алгоритмам разд, 4.1, могут содержать возвраты. Однако на возвраты, встречающиеся в этих алгоритмах, налагаются ограничения. Поэтому они оказываются экономяее алгоритмов гл. 4.
Тем пе менее в случаях, когда достаточно безвозвратного детерминированного алгоритма, ими лучше не пользоваться. В равд. 5.1 будут рассмотрены два языка высокого уровня, на которых можно записывать нисходящие алгоритмы разбора с ограниченными возвратами. Этн языки, называемые ЯНРОВ н ОЯНРОВ, позволяют задавать распознаватели для всех детср. минированных КС-языков с концевыми маркерами и благодаря возможности ограниченных возвратов даже некоторые не КС-языки, но (вероятно) не все КС-языки. Затем дадим метод построения для широкого класса КС-грамматик восходящих алгоритмов разбора, ориентированных на предшествованне и допускающих ограниченныс возвраты.
6.4. НИСХОДЯЩИЙ РАЗБОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ В данном разделе Определяются два формализма, предназначенные для описания алгоритмов с ограниченными возвратамн, которые строят дерево разбора сверху вниз, перебирая все альтернативы каждого нетермннала до тех пор, пока не найдется альтернатива, из которой выводится префикс необработанной части входной цепочки.
Как только такая альтернатива обнаружена, другие альтернативы уже не проверяются. Конечно, полученный таким способом префикс может оказаться «ошибочным», н тогда, поскольку возврата не будет, попытка разбора окончится неудачей. К счастью, в практических ситуациях это обстоятельство редко создает серьезные проблемы, если альтер- Гл. 6. АЗГОРитмы РА3БОРА с ОГРАниче!и!ыми зоззРАтАми нативы упорядочены так, что первыми испытываются более длинные из них. и Мы рассмотрим взаимоотношения между этими формализм ми, х реализацию, а также кратко обсудим их как механизмы, а определяющие классы языков.
Будет показано, что классы определяемых имн языков отличаются от класса КС-языков. бЛЛ. Я зын нисходящего разбора с ограниченными возвратами Возьмем общий нисходящий алгоритм разбора из разд. 4.1. Допустим, что мы решили вывести некоторую цепочку нз нетерминала А и что а;, а„..., а„— его альтернативы. Предположим, что в каком-то выводе входной цепочки из А вйводится некоторый префикс х еще не обработанной части этой цепочки и этот вывод начинается шагом А =р!Сс (1 =т(п), причем вывода, который начинался бы шагом Л ~!Сс для 1<т„не существует. Нисходящий алгоритм гл.
4 испытывает альтернативы сс, иы а,, ..., а„по порядку. После неудачи, связанной с альтернативой ау для 1 < т, восстанавливается положение входного указателя и делается новая попытка, уже для а е!. Эта новая попытка предпринимается независимо от того, выводится из а терминальная цепочка, являющаяся префиксом необработанной части входной цепочки, или нет. Изложим технику разбора, в которой нетерминалы трактуются как процедуры, сообщающие о том, обнаружена или нет подходящая цепочка. Чтобы проиллюстрировать этот подход, допустим, что а,,а„— входная цепочка и уже построен частичный левый разбор, для которого первые ! — 1 символон порождаемой им цепочки совпали с соответствующими символами входной цепочки. Если далее нужно «развернуть» нетерминал Л, то его можно'«вызвать» как процедуру с входной позицией ! в качестве аргумента. Если из А выводится терминальная цепочка, являющаяся префиксом цепочки а а!+!...а„, то говорят, что для входной позиции 1 нетерминал А усйса!ен, а в противном случае, что он неудачен для позиции 1.
Эти процедуры могут вызывать друг друга рекурсивно. Если нетерминал А вызван подобным образом, то он сам может вызывать нетермииалы, содержащиеся в его первой альтернативе Ес Е ли какой-то из этих вызовов закончится неудачно, то входной указатель возвращается туда, где он находился, когда впервые был вызван А, после этого Л вызывает альтернативу сс, и т. д.
Если вызов с»у приводит к совпцдеиию с символами а,.а,.ег„..а», то А возвращается к вызвавшей его процедуре и передвигает входной указатель вперед на позицпю А+1. $12 е.! нисходящий РАЭБОР с ОГРАниченными ВоззРАТАми рассматриваются в указанном здесь порядке, то алгоритм с ограниченными возвратами не распознает цепочку аЬс. Нетерминал 3, вызванный для входной позиции 1, вызовет Л для входной. позиции 1. Применяя первую альтернативу, А сообщит об успехе и передвинет входной указатель на позицию 2. Однако символ с не совпадает со вторым входным символом, и потому 3 сообщает о своей неудаче на позиции 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
