Упражнения 395

Б.З. Выполните упр. 5.2 для следующего синтаксиса:

А::=В\М С then if С then А else Л £::=£) = С

С ::= if С then С else С D

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

5.4. Рассмотрите нисходящий грамматический разбор для следующего синтаксиса:

S ::= А

A::B + A\DC B:~D\D*B

\ D::==x\(C) ,

С ::= +х I -x

На сколько символов вперед нзжно смотреть, чтобы анализировать предложения согласно этому синтаксису?

5.5. Преобразуйте описание ПЛ/О (рис. 5.4) в эквивалентное множество порождающих правил БНФ.

Б.6. Напишите программу, которая определяет множества начальных и внешних симоволов L{S) и F(S) для каждого нетерминального символа 5 в заданном множестве порождающих правил.

Примечание. Используйте часть программы 5.3 для построения внутреннего представления синтаксиса в виде структз'ры данных. Затем работайте с этой связанной стрзктурой.

5.7. Расширьте язык ПЛО и его транслятор, включив в него следующие операторы:

(a) Условный оператор вида

(оператор) ::= if {условие) then {оператор) else {оператор)

(b) Оператор цикла вида

(оператор) ::= repeat {оператор) {; {оператор)} until {условие)

Есть ли какие-либо особые трудности, которые могли бы привести к изменению формы или интерпретации указанных операторов? Вводить какие-то дополнительные команды в систему машины ПЛ/О вы не должны.

5.8. Расширьте язык ПЛ/О и его транслятор, добавив в него параметры процедзф. Рассмотрите два возможных решения и выберите одно из них для реализации:

(a) Параметры-значения. Фактические параметры обращения являются выражениями, значения которых присваиваются локальным переменным, представляющим формальные параметры, заданные в заголовке процедуры.

(b) Параметры-переменные. Фактические параметры являются переменными. При вызове они подставляются на место формальных

параметров. Параметры-переменные реализуются с помощью редачи адресов фактических параметров в места, выделенные для формальных параметров. Доступ к фактическим параметрам ocv ществляется косвенно через переданный адрес. Следовательно па раметры-переменные обеспечивают достп к переменным, определенным вне процедзф, и поэтому правила области определения можно изменить следующим образом: в каждой процедз^ре непосредственно доступны только локальные переменные; доступ к нелокальным переменным возможен только через параметры.

5.9. Расширьте язык ПЛ/0 н его транслятор, добавив переменные-массивы. Пусть диапазон индексов такой переменной а указывается в ее описании как

var a(low: high)

Б.ЛО. Модифицируйте транслятор ПЛ/0, чтобы он формировал рабочую программу для имеющейся у вас вычислительной машины.

Примечание. Формируйте программу на языке ассемблера, чтоби избежать проблем, связанных с загру^ой. На первом этапе пе пытайтесь оптимизировать рабочую программу, например использовать регистры. Возможная оптимизация должна включаться лишь на четвертом этапе уточнения транслятора.

5J1. Расширьте программу 5.5 в программу, называемую prettyprint ( красивая печать ). Задача этой программы - читать тексты ПЛ/0 и печатать их в форме, которая естественным образом отражает структуру текста при помощи соответствующего разделения иа строки и абзацы. Вначале аккуратно определите правила деления на строки и абзацы, основанные на синтаксической структуре ПЛ/0; затем реализуйте их, вставив операторы печати в программу 5.5. (Разумеется, нз сканера нужно убрать операторы печати.)

ЛИТЕРАТУРА

5.1. AMMANN и. The Method of Structured Programming Applied to the Development of a Compiler. - International Computing Symposium 1973, A Giinther et al., eds., Amsterdam: North-Holland Publishing Co., 1974 93-99.

5.2 COHEN D. J., GOTLIEB C. C. A List Structure Form of Grammars for Syntactic Analysis. - Сотр. Surveys, 2, No. 1, 1970, 65-82.

5.3. FLOYD R. W. The Syntax of Programming Languages - A Survey.- IEEE Trans.. EC-13, 1964, 346-353.

Б.4. CRIES D. Compiler Construction for Digital Computers. - New-York: Wiley, 1971. [Имеется перевод: ГРИС Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир, 1975.)

5.5. KNUTH D. Е. Top-down Syntax Analysis.- Лс<о Informatica, 1, No. 2, 1971,79-110.

5.6. LEWIS P. M., STEARNS R. E. Syntax-directed Transduction, J. ACM, 15, No. 3, 1968, 465-488. ,

5.7. NAUR P. Report on the Algorithmic Language ALGOL W. - ACM, b, No. 1, 1963, 1-17.

Б.8. SCHORRE D. V. META II, A Syntax-oriented Compiler Writing Language.- Proc. ACM Natl. Conf., 19, 1964, D 1 3. 1-11.

..9. WIRTH N. The Design of a PASCAL Compiler. - Softoare -Practice and Experience, 1. No. 4, 1971, 309-333.

ПРИЛОЖЕНИЕ А \

МНОЖЕСТВО СИМВОЛОВ ASCII

Порядковый номер символа определяется по его координатам в таблице как

ord(cft) = 16 х + jr.

Символы с порядковыми номерами от О до 31 и 127 - так называемые управляющие символы, используемые для передачи данных и управления устройствами. Символ с порядковым номером 32 есть пробел.