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

<

<-

<•

<•

<•

<•

>

•>

<•

<•

•>

<

->

>

•>

•>

Рис. 6.4. Отношения предшествования Колмерауэра.

Пример 6.16. В примере 6.15 мы видели, что грамматика S -*- aSA I bSA [b, Л -а удовлетворяет нужным условиям. Лемма 6.12 подсказывает, что для этой грамматики отношения предшествования Колмерауэра определяются так, как показано на рис. 6.4. □

УПРАЖНЕНИЯ

6.2.Ь Какие из следующих разборов являются нисходящими для грамматики Gq? Какая выводится цепочка (если таковая существует)?

(а) (1,0) (3.2) (5.4) (2,0) (4,2) (2,5) (4,0) (4,5) (6,5) (6,2) (6,0).

(б) (2,0) (4,0) (5,0) (6,1).

6.2.2. Постройте двухмагазинный анализатор, корректный для грамматики G.

6.2.3. Какие из следующих грамматик являются грамматиками Колмерауэра?

(а) Go

(б) S~aA\bB Л-0Л1101 Б-0111011

(в) S-aAB b A-bSB а В-v-a

*6,2.4. Покажите, что если грамматика G - приведенная и обратимая и }аПр>5 = 0, рр-Пix"*~0, то она однозначная.

6.2.5. Покажите, что каждая обратимая регулярная грамматика является грамматикой Колмерауэра.

6.2.6. Покажите, что каждая обратимая грамматика в нормальной форме Грейбах, для которой р+л Пр=0, является грамматикой Колмерауэра.

6.2.7. Покажите, что двухмагазинный анализатор из примера 6.12 корректен для соответствующей грамматики.

6.2.8. С помощью теоремы 6.6 покажите, что каждая грамматика простого предшествования является грамматикой Колмерауэра.

6.2.9. Докажите лемму 6.9.

6.2.10. Докажите лемму 6.10.

6.2.11. Пусть G -грамматика Колмерауэра с отношениями предшествования Колмерауэра, для которой индуцируемый ек двухмагазинный анализатор не только анализирует каждую цепочку из L{G), но также корректно анализирует каждую выводимую цепочку грамматики G. Покажите, что

(а) 11л.% (б)

(в) р-*-р«>,

(г) р+рХ+< и •>.

*6.2.12. Пусть G-грамматика Колмерауэра и v -подмноже ство отношения р"лХ+ - pi-р,Х. Покажите, что отпошенш <• - p*fiX -V и •> - р"А и V-это отношения предшество вания Колмерауэра, позволяющие анализировать любую выво димую цепочку грамматики G.

6.2.13. Покажите, что каждый двухмагазинный анализато] расходует на обработку цепочки длины п время 0(п).

*6.2.14. Покажите, что если язык L определяется граммати кой Колмерауэра, то и определяется такой грамматикой.

*6.2.15. Является ли каждая (1,1)-0ПК-грамматика грам матикой Колмерауэра?

*6.2.16. Покажите, что существует такой язык определя емый грамматикой Колмерауэра, что ии L, ни не являетсз детерминированным КС-языком. Заметьте, что использовавшийс: в качестве примера язык {t4Jba"E£j = n} не детерминированный хотя его обращение-детерминированный язык.

1) Это утверждение - частный случай леммы 6.7; оно включено тольк для полноты.

Теорема 6.6. Грамматика является грамматикой Колмерауэра тогда и только тогда, когда она однозначная, приведенная, обратимая и ii[]p*\ik0.

Доказательство. Непосредственно следует из лемм 6.8, 6.9 и 6.12. □



) См. также работы Лаврова и Ордяна [I975J и Ордяна 11975]. -Ярыж перев.

ПРИЛОЖЕНИЕ

В приложении даются синтаксические описания четырех языков программирования, среди них

(1) простой язык, служащий базой расширяемого языка;

(2) Снобол 4, язык для обработки строк;

(3) ПЛ 360, машинный язык высокого уровня для вычислительных машии ИБМ 360;

(4) PAL, язык, объединяющий лямбда-исчисление с операторами присваивания.

Эти языки выбраны потому, что они не похожи друг на друга. Кроме того, их синтаксические описания достаточно малы, чтобы ими можно было пользоваться Б некоторых упражнениях на программирование, приведенных в нашей книге, ие расходуя слишком много времени (как человека, так и машины). Прн этом выбранные языки довольно сложны, и в них представлен целый букет проблем, с которыми приходится сталкиваться при реализации более традиционных языков программирования, таких, как Алгол, Фортран, ПЛ/1. Синтаксические описания последних можно найти в следующих источниках:

(1) Алгол 60 в [Наур, 1963].

(2) Алгол 68 в [Ваи Вейнгаарден, 1969],

(3) Фортран Б ГАНС, 1966] (см. также [АНС Подкомитет, 1971]).

(4) ПЛ/1 в отчете Венской лаборатории ИБМ, TR 25.0961).

П.1. СИНТАКСИС РАСШИРЯЕМОГО ЯЗЫКА

Опишем язык, предложенный Ливенвортом [1966] в качестве базового языка, который можно расширять с помощью синтаксических макросов. Синтаксис этого языка будет представлег

1) См. более доступную книгу: Универсальный язык программироваииз PL/I, нзд-во „Мир", М., mS.npuM. перев.

*6.2.17. Говорят, что двухмагазинный анализатор г ролозногт область определения отношения т(Г) независимо от того, связан ли как-нибудь выдаваемый им „разбор* с входной цепочкой. Покажите, что каждый рекурсивно перечислимый язык распознается некоторым детерминированным двухмагазинный анализатором. Указание: Полезно сделать исходную грамматику неоднозначной.

Открытая проблема

6.2.18. Дайте характеристику класса КС-грамматик, однозначных или нет, для которых сушествуют детерминированные двухмагазинные анализаторы, индуцируемые непересекающимися отношениями „предшествования".

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

Грамматики Колмерауэра и теорема б.б впервые были опубликованы в работе Колмерауэра [I970j. Грэн в Харрисон [I9G9I связали этн идеи с понятием множества знаменательных символов. Коэн и Чулнк [1971] рассматривали LR (/г)-схему анализа, эффективно применяющую возвраты



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

Вторая часть описания - множество правил, определяющих механизм расширения, который позволяет описывать новые виды операторов и функций с помощью оператора макроопределения, порождаемого правилом 37. Это правило говорит о том, что частным случаем <оПератора> может быть <макроопределе-ние>, а оно по правилам 39 и 40 может быть либо <макроопре-делением оператора), либо <макроопределением функции).

Правила 41 и 42 показывают, что каждое из этих макроопределении включает <макроструктуру> и <определение>. <Л1акро-структура) определяет форму новой синтаксической конструкции, а <определение> дает ассоциируемый с ней перевод. -(Макроструктура) и <определенне) могут быть любыми цепочками, состоящими из терминальных и нетерминальных символов, но при условии, что каждый нетерминал, встречающийся в <опре-делении), должен также встречаться в <макроструктуре). (Это похоже па правило СУ-схемы, но здесь не налагается ограничений на то, сколько раз можно брать один нетерминал в транслирующем элементе.)

Мы не даем явных правил для <макроструктуры) н <опре-деления). На самом деле определение, говорящее 6 том, что каждый нетерминал из <определения> должен встречаться в <макроструктуре>, нельзя выразить с помощью контекстно-свободных правил.

Правило 37 указывает, что вместо <оператора> в выводцмую цепочку можно подставить любой частный случай <макрострук-туры), определенный в некотором макроопределении оператора. Аналогично, правило 43 позволяет любой частный случай <мак-роструктуры), определенный в некотором макроопределении функции, подставлять в выводимую цепочку вместо <первичного).

Например, оператор суммирования можно определить с помощью вывода

<оператор) => <макроопределение>

=Ф> <макроопределенне оператора) =4>smacro <макроструктура) define <определение> endmacro

Возьмем в качестве <макроструктуры) цепочку

sum <выражеиие)* with <переменная)-«-<выражение)" to

<выражение>*

Перевод этой макроструктуры можно определить, взяв в качестве ее определения цепочку

begin local t\ local s; local r;

<переменная) -f- <выражение>"; if <переменная> > <выражение> then goto s; i t + <выражениеУ; <переменная)-*-<переменная)+ 1; goto г; s: result t

Тогда, если написан оператор

sum а with -с to d то до того, как он будет проанализирован в соответствии с пра вилами высокого уровня, его надо перевести в цепочку begin local t\ local s; local r;

r: if 6 > d then goto s; t-t~\-a; bb+\; goto r; s: result t end

И, наконец, нетерминалы <идентификатор), <метка> и <ко станта)-это лексические единицы (лексемы), которые мы оста ляем неопределенными, а читателя просим либо рассматрнва их как терминальные символы, либо определить их, как еи нравится, и добавить эти определения.

Правила высокого уровня

1 <программа)-»-

<блок>

2 <блок)-

begin <необязат локал идентифры) <список операторов) е

3 <необязат локал идентифры) -*

<необязат локал идентифры) local <идентпфикатор); j е 5 <список операторов)-

<оператор)I<список операторов); <оператор) 7 <оператор)-

<переменная) <выражение) goto <идентификатор) (

if <выражение) then <оператор)( <блок) result <выражени

<метка): <оператор)





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.0035