Главная Промышленная автоматика.

множество знаменательных символов тогда и только тогда, когда G-грамматика предшествования.

Определение. Пусть G--(N, 2, Р, 5)-Г-каноническая грамматика. Т-остовная грамматика для G получается заменой в правилах из Р всех вхождений символов из V - Т новым символом и устранением правила S-Sf, если оно при этом появилось.

•>

•>

•>

•>

<

->

<

<

•>

<•

>

<•

<•

<

<•

<•

<

<

->

•>

•>

>

•>

•>

>

>

<

<•

<•

<•

<

Рис. 5.23, Отношения Д-канонического предшествования.

Пример 5.50. Пусть А то же, что и в примере 5.49. Тогда Д-остовной грамматикой для Gq будет

Sq уSq-\-Sq\SqF \ Е F{S,)\a □

5.4.31. Разработайте алгоритм разбора типа „перенос-свертка" для грамматик Г-канопического предшествования, имеющих обратимые Г-остовные грамматики. При этом, разумеется, должны вырабатываться разборы, соответствующие остовной грамматике.

Проблема для исследования

5.4.32. Разработайте преобразования, с помощью которых можно получать ОПК-грамматики, грамматики простого или операторного предшествования.

Упражнения на программирование

5.4.33. Напишите программу, проверяющую, является ли данная грамматика грамматикой операторного предшествования.

5.4.34. Напиип1те программу, строящую соответствующий анализатор для грамматики операторного предшествования.

(1) ДЛЯ каждой правой части правила, скажем ссХКр, нз ХТ следует К € 2;

(2) из Л 6 Г и Л а следует, что а содержит символ из Т.

Таким образом, 2-каноническая грамматика-это то же что операторная грамматика. Для Г-канонической грамматики G будем называть множество Т множеством ее знаменательных символов.

Зададим для Т-канонической грамматики G отношения Т-ка-нонического предшествования на Т[}{}:

(1) Если в Р есть правило Л -i-otXpKy, X и V содержатся в Г и р - либо е, либо содержится в V-Т, то ХУ.

(2) Если Л -аХВ{Р и В=уУб, где X и У содержатся в Т и у-либо е, либо содержится в V-Г, то Х<:У.

(3) Пусть Л-yaBaZtXaP, где -либо е, либо символ из V-Т. Допустим, что Z=>*piap3, где pj-либо е, либо содержится в У-Т и а €2. (Заметим, что по определению Г-кано-нической грамматики этот вывод должен быть тривиальным, т. е. состоять из нуля шагов, если аФе.) Допустим также, что существует вывод

B=yCj6i=yy.fi66j: =i>yi... yk-iCk-ik-i ••i

где на каждом шаге заменяется символ Q, все бу принадлежат {е}{}У-~Г и ХТ. Тогда Ха.

(4) Если 5+аХр и а 6 И и У-Т, то $<Х. Если р€ WUK-Г, то Х>$.

Заметим, что при Т -2 получается определение отношений операторного предшествования, а при ТУ-отношений Вирта- Вебера.

Пример 5.49. Рассмотрим грамматику с множеством знаменательных символов Д{Р, а, (,), + ,*}. Найдем, что (), так как (Е)-правая часть правила и £ не знаменательный символ. Далее, -1- -х-, так как существуют правая часть E-j-Tu вывод Г~>+Г«-£, и Г не знаменательный символ. Кроме того +•> + , так как существуют правая часть Е-\-Т и вывод E=i>E + T, и Т не знаменательный символ. Отношения А-канонического предшествования для Go приведены на рис. 5.23. □

5.4.29, Найдите все множества знаменательных символов для грамматики G.

5.4.30. Покажите, что 2-множество знаменательных символов для G = (N, 2, Р, 5) тогда и только тогда, когда G - грамматика операторного предшествования. Покажите, что Nu2 -



5.4.35. Найдите грамматику операторного предшествования для одного нз языков, приведенных в приложении, и затем постройте для этой грамматики соответствующий анализатор,

5.4.36. Напишите программу, строящую соответствующий анализатор для (I, 1)-0ПК-грамматики.

5.4.37. Напишите программу, строящую соответствующий анализатор для простой ССП-грамматики.

5.4.38. Определите язык программирования, в основе которого лежал бы язык Флойда-Эванса. Постройте для него компилятор.

АЛГОРИТМЫ РАЗБОРА

С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ

Замечания по литературе

Различные методы разбора, ориентированные иа предшествование, применялись в самых первых компиляторах. Формализация понятия операторного предшествования принадлежит Флойду [1963]. Методы, использующие ограниченный контекст и ограниченный правый коитекст, были определены тоже в начале 1960-х годов. Большинство ранних результатов, касающихся разбора методом ограиичеииого контекста и его вариантов, содержится в работах Эйкеля и др. [1963], Флойда [1963, 1964а. 19646], Грэхема [1964J, Лйронса [1964] и Пола [1962].

Приведенное в этом разделе определение ОПК-грамматики эквивалентно тому, которое дал Флойд [1964а]. Локс [1970] разработал алгоритм построения анализаторов для некоторых классов ОПК-грамматик. Вайз [1971] распространил алгоритм Домёлки на ОПК-грамматики.

Смешанная стратегия предшествования была введена Маккиманом и при, менена им с соавторами [1970] в качестве основы системы построения компиляторов XPL.

Язык Флойда -Эванса -это предложеииая Эвансом [1964] модификация языка, первоначально введенного Флойдом [1961]. Фельдман [1966] использовал его в качестве основы системы построения компиляторов, названной Языком Формальной Семантики (FSL). При этом среди действий, входящих в операторы языка, могут быть общие семантические процедуры.

Т-каиоиическос предшествование было введено Грэем и Харрисоном [1969]. Пример 5.47 взят из книги Хопгуда [1969]).

1) Трахтенгерц и Шумей [1971] обобщили идею предшествования иа не КС-грамматики. Трубчанинов [1976] обобщил понятие Т-каноиического предшествования. Интересный класс „строго детерминированных" грамматик ввели Харрисон и Хавел [1973, 1974]. Эти грамматики порождают класс ЬК(0)-язы-ков, но алгоритм разбора для них не восходящий и не нисходящий, а обладает чертами обоих методов.- Прим. перев.

В настоящей главе мы изложим несколько алгоритмов синтаксического анализа, которые, подобно общим нисходящим и восходящим алгоритмам разд. 4.1, могут содержать возвраты. Однако на возвраты, встречающиеся в этих алгоритмах, налагаются ограничения. Поэтому они оказываются экономнее алгоритмов гл. 4. Тем ие менее в случаях, когда достаточно безвозвратного детерминированного алгоритма, ими лучше не пользоваться.

В разд. 6.1 будут рассмотрены два языка высокого уровня, на которых можно записывать нисходящие алгоритмы ра.-бора с ограниченными возвратами. Эти языки, называемые ЯНРОВ и ОЯНРОВ, позволяют задавать распознаватели для всех детерминированных КС-языков с концевыми маркерами и благодаря возможности ограниченных возвратов даже некоторые не КС-языки, но (вероятно) не все КС-языки. Затем дадим метод построения для широкого класса КС-грамматик восходящих алгоритмов разбора, ориентированных иа предшествование и допускающих ограниченные возвраты.

6.1. нисходящий РАЗБОР с ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ

В данном разделе определяются два формализма, предназначенные для описания алгоритмов с ограниченными во.вратами, которые строят дерево разбора сверху вниз, перебирая все альтернативы каждого нетерминала до тех пор, пока не найдется альтернатива, из которой выводится префикс необработанной части входной цепочки. Как только такая альтернатива обнаружена, другие альтернативы уже не проверяются. Конечно, полученный таким способом префикс может оказаться «ошибочным», и тогда, поскольку возврата не будет, попытка разбора окончится неудачей. К счастью, в практических ситуациях это обстоятельство редко создает серьезные проблемы, если альтер-



1) Здесь снова возникает проблема адекватности распознавателя Мс соответствующей грамматике G, упоминавшаяся в доподиении к разд. 5.1 и в разд. SAA. -Прим. перев.

Различие между таким алгоритмом и алгоритмом 4.1 состоит в том, что если последний потерпит неудачу при попытке найти ПОЛНЫЙ разбор, в котором из ау выводится ai...a, то он вернется назад, станет испытывать выводы, начинающиеся правилами Л->-ay4.j, Л-»-ау+2 и т.д., и при этом, возможно, получит другой префикс цепочки выводимый из Л. Наш новый алгоритм так не делает. Если уж оп обнаружил, что нз «у выводится префикс входной тпочкп и что полученный после этого вывод неудачен, т. е. не дает цепочки, совпадающей с входной цепочкой, то он возвращается к процедуре, вызвавшей А, и сообщает о неудаче. Алгоритм будет вести себя так, как будто из Л не выводится никакой префикс цепочки а,..а„. Таким образом, этот алгоритм может не обнаружить некоторые разборы и даже может распознать не тот язык, который определяет лежащая в его основе КС-грамматика). Мы ие будем, следовательно, связывать такой алгоритм с конкретной КС-грамматикой, а будем трактовать его сам по себе как формализм, предназначенный для определения и синтаксического анализа языка.

Возьмем конкретный пример. Если правила

5-.Лс А а\аЬ

рассматриваются в указанном здесь порядке, то алгоритм с ограниченными возвратами не распознает цепочку аЪс. Нетерминал 5, вызванный для входной позиции. 1, вызовет Л для входной, позиции 1. Применяя первую альтернативу, Л сообщит об успехе и передвинет входной указатель на позицию 2. Однако силшол с не совпадает со вторым входным символом, и потому S сообщает о своей неудаче на позиции ]. Так как нетерминал Л сообщил об успехе своего первого вызова, он уже не будет вызываться, для проверки второй альтернативы. Заметим, что этой трудности можно избежать, записав Л-альтернативы в обратном порядке

АаЪ\а

Теперь изложим язык нисходящего разбора с ограниченными возвратами (сокращенно ЯНРОВ), который можно использовать для описания процедур разбора указанного типа. Оператором (или правилом) этого языка называется цепочка одного из видов

Л BC/D

нативы упорядочены так, что первыми испытываются более длинные из них.

Мы рассмотрим взаимоотношения между этими формализмами, их реализацию, а также кратко обсудим их как механизмы, определяющие классы языков. Будет показано, что классы определяемых ими языков отличаются от класса КС-языков.

6.1.1. Язык нисходящего разбора с ограниченными возвратами

Возьмем общий нисходящий алгоритм разбора из разд. 4.1. Допустим, что мы решили вывести некоторую цепочку из нетер-лшнала А и что а, сс, а„-его альтернативы. Предположим, что в каком-то выводе входной цепочки из А выводится некоторый префикс х еще не обработанной части этой цепочки и этот вывод начинается шагом А ia„ {I тп), Причем вывода, который начинался бы шагом Л=:>ау для / < т, не существует.

Нисходящий алгоритм гл. 4 испытывает альтернативы а, по порядку. После неудачи, связанной с альтернативой aj для j <.т, восстанавливается положение входного указателя и делается новая попытка, уже для ay+i. Эта новая попытка предпринимается независимо от того, выводится из терминальная цепочка, являющаяся префиксом необработанной части входной цепочки, или нет.

Изложим технику разбора, в которой нетерминалы трактуются как процедуры, сообщающие о том, обнаружена или нет подходящая цепочка. Чтобы проиллюстрировать этот подход, допустим, что ai.,.a„ - входная цепочка и уже построен частичный левый разбор, для которого первые /-I символов порождаемой им цепочки совпали с соответствующими символами входной цепочки. Если далее нужно «развернуть» нетерминал Л, то его можно«вызвать» как процедуру с входной позицией i в качестве аргумента. Если из А выводится терминальная цепочка, являющаяся префиксом цепочки аа.. то говорят, что для входной позиции i нетерминал А успешен, а в противном случае, что он неудачен для позиции /.

Эти процедуры могут вызывать друг друга рекурсивно. Если нетерминал А вызван подобным образом, то он сам может вызывать нетерминалы, содержащиеся в его первой альтернативе сСд. Если какой-то из этих вызовов закончится неудачно, то входной указатель возвращается туда, где он находился, когда впервые был вызван Л, после этого Л вызывает альтернативу и т. д. Если вызов ау приводит к совпадению с символами ufi,. ,а, то Л возвращается к вызвавшей его процедуре и передвигает входной указатель вперед на позицию k-\-\,





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 [84] 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0037