Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Глава 8. Основные фазы компиляции

⇐ ПредыдущаяСтр 21 из 21

Транслятор – это программа перевода текста (программы) с одного языка (исходного) на другой (объектный). Трансляторы различают компилирующего и интерпретирующего типов. Компилятор переводит всю программу, затем её выполняет. Интерпретатор переводит по отдельным операторам программу и сразу каждый из операторов исполняет.

Компилятор должен выполнить анализ исходной программы, а затем синтез объектной. Сначала исходная программа разлагается на составные части; затем из них строятся фрагменты эквивалентной объектной программы. Для этого на этапе анализа компилятор использует и строит целый ряд таблиц, структур данных, которые затем используются как при анализе, так и синтезе. Анализ процессов компиляции позволяет выделить 7 различных логических задач – фаз компиляции. В практических реализациях грани между этими фазами размыты, часть из них может отсутствовать, совмещаться одна с другой.

В этой главе мы лишь кратко остановимся на основных фазах и базах данных компилятора.

1). Лексический анализ – распознавание базовых элементов языка, перевод исходной программы в таблицу стандартных символов (лексем), которые в отличие от элементов исходной программы имеют постоянную длину, что делает последующие фазы компиляции более простыми. Лексический анализатор или сканер группирует определенные терминальные символы исходной программы в единые синтаксические объекты – лексемы. Какие объекты считать лексемами, зависит от определения языка программирования. Лексема – это пара вида: тип лексемы, некоторые данные. Первой компонентой пары является синтаксическая категория, такая как “константа”, “идентификатор” или “терминал” (ключевое слово языка или специальный символ: знак операции, разделитель и т.п.), а вторая – указатель: в ней указывается номер элемента таблицы, хранящий подробную информацию об этой конкретной лексеме. Входной информацией сканера является исходная программа и таблица терминалов языка, выходом – цепочка лексем, таблицы идентификаторов и констант.

2). Синтаксический анализ или разбор – использует только первые компоненты лексем – их типы. Информация о каждой лексеме (вторая компонента) используется на более поздних этапах процесса трансляции. Синтаксический анализ призван рассматривать базовые конструкции языка, исследовать цепочку лексем и устанавливать, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Основа синтаксического анализа – синтаксические правила или грамматика языка. По предложенной грамматике можно автоматически построить синтаксический анализатор, который будет проверять, имеет ли исходная программа синтаксическую структуру, определяемую правилами грамматики. В предыдущих разделах изложены несколько методов разбора и алгоритмов построения синтаксических анализаторов по заданной грамматике.

3). Семантический анализ – определение смыслового значения базовых синтаксических конструкций. Этот процесс синтаксически управляем. То есть фазы 2 и 3 тесно связаны (объединены).

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

Когда встречается оператор присваивания вида

<переменная>:=<выражение>

семантическая программа проверяет переменную и выражение на соответствие типов, а затем заносит информацию об инструкции присваивания во внутреннюю форму программы (ВФП).

Таким образом, анализаторы 2 и 3 выполняют сложную и наиболее существенную работу по расчленению исходной программы на составные части, формированию ее внутреннего представления с занесением информации в таблицы идентификаторов и констант, осуществляют полный синтаксический и семантический контроль программы, включая действия по локализации, идентификации и нейтрализации ошибок.

4). Машинно–независимая оптимизация ВФП – вынесение общих подвыражений, вычисления над константами, оптимизация переходов в сложных условных операторах, вынесение инвариантных вычислений за цикл и т.п.

5). Распределение памяти – модификация таблиц идентификаторов и констант. Определение адресов идентификаторов и констант. Вставки в ВФП, для генерации и распределения динамической памяти. Выделение временной памяти, выравнивание и т.п.

6). Генерация кода и машинно–зависимая оптимизация. С каждой операцией из ВФП связана кодовая продукция, которая и выносится в код сборки. Оптимизация же проводится с целью более эффективного использования регистров ЭВМ, удаление “лишних” команд, связанных с сохранением и загрузкой промежуточных данных на этапе вычислений и т.п.

7). Сборка и выдача – разрешение символических адресов (трансляция с языка ассемблера) и формирование объектного модуля (машинного кода и информации для компоновщика и загрузчика).

Сразу же отметим, что фазы 1 – 4 машинно–независимы и определяются только исходным языком, а фазы 5 – 7 машинно–зависимы и не зависят от исходного языка.

а). Исходная программа – это программа на исходном языке программирования, например, С или Паскаль.

б). Таблица терминальных символов – постоянная таблица, в которой записаны все ключевые слова (IF, THEN, ELSE, WHILE и т.п.) и специальные символы языка (пробел, ‘,’, ‘;’, ‘*’, ‘+’ и т.п.) в символьной форме. На них ссылаются стандартные символы – лексемы программы.

в) Таблица (строка) лексем (стандартных символов) – состоит из полного или частичного списка лексических единиц, расположенных в том порядке, в каком они встречаются в программе (например, TRM(1¸n), IDN(1¸m), CON(1¸k)). Они создаются при лексическом анализе и используются на этапах синтаксического и семантического анализа.

г). Таблица идентификаторов – содержит информацию обо всех переменных программы, в том числе и временных переменных, хранящих промежуточные результаты вычислений, и информацию, необходимую для ссылок (адресации) и отведения памяти. Создается на фазе лексического анализа (1) (на элементы таблицы идентификаторов ссылаются лексемы), модифицируется на фазах семантического анализа (3) и распределения памяти (5), используется также на фазах генерации кода (6), сборки и выдачи (7).

д). Таблица констант – содержит все константы исходной программы и дополнительную информацию о них. Создается на фазе лексического анализа (1) (на нее ссылаются лексемы), модифицируется на фазе семантического анализа и распределения памяти, используется при генерации кода, сборке и выдаче.

е). Правила грамматики (продукции) – могут представляться и неявно в самом теле программы синтаксического анализа. Они обеспечивают, в соответствии с заданным алгоритмом, автоматический анализ синтаксиса исходной программы. Зачастую, в грамматике содержится информация и о семантических действиях (транслирующие и атрибутные грамматики), которые надо предпринимать в процессе обнаружения тех или иных языковых конструкций. ж). Внутренняя форма программы (ВФП) – форма обеспечивающая однопроходную генерацию кодов (в компиляторе) или интерпретацию (выполнение интерпретатором). Пример ВФП – ПОЛИЗ (польская инверсная запись) – где арифметические выражения, да и вся программа представляется не в традиционной инфиксной форме, а в постфиксной или суффиксной бесскобочной формах. В ПОЛИЗе операции располагаются за операндами, над которыми они выполняются в порядке их выполнения.

Например, оператор

a:=b+c*d/(b–c)–10; в ПОЛИЗе примет вид abcd*bc–/+10–:=

Еще чаще в компиляторах в качестве ВФП используется матрица тетрад, где выражение представляется в форме тетрад (оператор, операнд, операнд, результат) в порядке их выполнения. Например, присваивание a:=b+c*d будет представлено как

*	C	,	D	,	M1
	B	,	M1	,	M2
	M2	,		,	A

где M1 и M2 временные переменные, образованные компилятором. (При работе компилятора, операндами в приведенных примерах будут не сами символические имена и значения, а лексемы – ссылки на таблицы, где они были описаны.) ВФП создается на фазе семантического анализа, модифицируется (оптимизируется) на фазе машинно–независимой оптимизации и используется при генерации кода.

з). Кодовые продукции – постоянная таблица, имеющая отдельные элементы, определяющие код для каждой возможной операции ПОЛИЗа или матрицы тетрад (т.е. ВФП). Например, тетрада +, операнд_1, операнд_2, результат или более конкретно +, A, B, M10 может быть представлена следующей кодовой продукцией:

MOV ax, A

ADD ax, B

MOV ax, M10

а тетрада :=, операнд_1,, результат (:=, M20,,ABC) – продукцией

MOV ax, M20

MOV ABC, ax

Таблица кодовых продукций используется на фазе генерации кода.

и). Код сборки – версия программы на языке сборки (аналог языка ассемблера). Создается на фазе генерации кода и используется фазой сборки.

к). Перемещаемый объектный модуль – результат фазы сборки и всей трансляции в целом. Является входной информацией для компоновщика или загрузчика.

Более подробно описание каждой фазы компиляции рассмотрено, например в [7,11].

Заключение

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

Приложение

Здесь приведены варианты индивидуальных лабораторных работ, которые можно выполнять на ЭВМ параллельно с изучением рассматриваемого курса. Во всех вариантах заданий цепочки языка, для которого необходимо построить анализатор, заданы в виде правил, близких к расширенной форме Бэкуса-Наура.

Если это не оговорено дополнительно, то используются следующие группы метасимволов: < ... > - нетерминал;

::= - разделитель левой и правой частей правил и обозначает: “это есть” или “состоит из”;

[ ... ] - факультативный (необязательный) элемент;

{ ... } - итерация, т.е. элемент повторяется 0 или более раз;

? ... ¦ ... ¦ ... ? - альтернатива;

Используются также следующие сокращения: @ - произвольный идентификатор; k - константа, если не оговорено, то целая. Терминальные символы, а к ним здесь относятся и идентификаторы, и константы, выделены жирно.

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

Вариант 1

Построить синтаксический анализатор для цепочек автоматного языка операторов присваивания (ПЛ/1), имеющих вид:

<оператор присваивания> ::= {<метка>:}<левая часть>=<правая часть>;

<метка> ::= @

<левая часть> ::= @[(<список индексов>)]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= ? <левая часть>{<оп1><левая часть>} ¦ k ?

<оп1> ::= ? + ¦ - ¦ * ¦ / ?

<правая часть> ::= <операнд>{<оп2><операнд>}

<операнд> ::= ? <левая часть> ¦ k1 ?

где k1 - целая или действительная константа

<оп2> ::= ? <оп1> ¦ OR ¦ AND ?

Примеры правильных цепочек:

abc: ac123: a1(i+j/10,j*k,10,a2(1,i,15)-a2(1,2*i,7)+15,l)=

1234+a2(1,i,15)*1234.56E-3/aqs(3,a2(j,a2(1,2,3),15));

abcde=123; aaa=aaa OR bbb OR ccc AND 1;

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

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

Вариант 2

Построить синтаксический анализатор для цепочек автоматного языка операторов описания типов (Модула-2), имеющих вид:

<описания типов> ::= TYPE <описание типа>; {<описание типа>;}

<описание типа> ::= @=? <простой тип> ¦ <массив> ¦ <множество> ¦ <запись> ¦ <указатель> ?

<простой тип> ::= ? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD ¦ <перечисление> ¦ <диапазон> ?

<перечисление> ::= (@{,@})

<диапазон> ::= [k1..k2]

<массив> ::= ARRAY <диапазоны> OF <тип>

<диапазоны> ::= <диап1>{,<диап1>}

<диап1> ::= ? <диапазон> ¦ @T1 ?

<тип> ::= ? <простой тип> ¦ @T ? ,

где @T - имя типа, определенного выше в анализируемом Вами операторе, @T1 - имя типа-дипазона

<множество> ::= SET OF <простой тип>

<запись> ::= RECORD <элемент> {;<элемент>} END

<элемент> ::= @{,@}: <тип>

<указатель> ::= POINTER TO <тип_1>

<тип_1> ::= ? <простой тип> ¦ @T2 ? ,

где @T2 - имя типа, определенного выше или ниже в анализируемом Вами операторе. Пример правильной цепочки:

TYPE Color = ( Red, Blue, White, Black );

diap = [10..25]; BitSet = SET OF WORD;

Mas = ARRAY [0..100], [0..3], diap OF BitSet;

PTab = POINTER TO Tab;

Tab = RECORD a1, a2, a3: CARDINAL; col: Color;

St: ARRAY [0..79] OF CHAR;

left, right: PTab

END;

MTab = ARRAY [0..100] OF Tab;

Семантика: Сформировать список определяемых типов с указанием объема памяти, отводимого под тип.

Вариант 3

Построить синтаксический анализатор для цепочек автоматного языка операторов описания констант (Модула-2), имеющих вид:

<описания констант> ::= CONST <описание>; {<описание>;}

<описание> ::= @=<выражение>

<выражение> ::= ? <операнд>{<операция><операнд>} ¦ '<текст>'?

<операнд> ::= ? k ¦ @C ? ,

где k - целая или вещественная; @C - имя константы, определенной выше в анализируемом Вами операторе;

<текст> - произвольный набор символов.

<операция> ::= ? + ¦ - ¦ * ¦ / ¦ DIV ¦ MOD ?

Пример правильной цепочки:

CONST Abc = 1024 DIV 7 + 35 MOD 17; text = 'All right';

Cde = 1234 - 32*13; rur = 3.14;

rir= 123.*rur/12.3E-5+rur; Fg = Abc - Cde + 15;

Семантика: Сформировать список - таблицу констант с указанием имени, типа и значения. Сообщать об ошибках при переполнении констант, несовместимости типов и использовании неверных операций для конкретного типа.

Вариант 4

Построить синтаксический анализатор для цепочек автоматного языка операторов описания пеpеменных (ПЛ/1), имеющих вид:

<описания пеpеменных> ::= ? DCL ¦ DECLARE ? <список описаний>;

<список описаний> ::= <описание>{,<описание>}

<описание> ::= ? <пеpеменная> [<атpибут>] ¦ (<список пеpеменных>)<атpибут> ?

<пеpеменная> ::= @[(<список pазмеpностей>)]

<список pазмеpностей> ::= <pазмеpность>{,<pазмеpность>}

<pазмеpность> ::= k1[:k2] ,

где k1 и k2 - целые числа со знаком

<атpибут> ::= ? BIN[ARY] FIXED ¦ FLOAT ¦ CHAR[ACTER](k) ?

Примеры правильных цепочек:

DCL IND1, JIG, LOO, SUM, E123 BIN FIXED, III FLOAT, ST CHAR(10),

STR CHARACTER(25), SUSPEED BINARY FIXED, IMAS(100),

(ABC(10,-15:20,0:23), MICRO, MACRO(5:40), ERCOD) BIN FIXED;

DECLARE SSS(10:20,50) CHAR(1);

Семантика: По умолчанию, пеpеменные, имена котоpых начинаются с букв I,J,K,L,M,N имеют тип BIN FIXED, остальные - FLOAT. Сообщать об ошибках, если k1 > k2, pазмеp стpоки больше 256 символов и pазмеp массива больше 64 Kбайт. Сфоpмиpовать упорядоченный список-табл-

ицу пеpеменных с указанием имени, типа, pазмеpности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух полей формируемой таблицы, все остальные поля в числовой форме). Напоминаем, что переменная типа BIN FIXED занимает 2 байта памяти, FLOAT - 4 байта, CHAR(1) - 1 байт.

Вариант 5

Построить синтаксический анализатор для цепочек автоматного языка операторов описания форматов (ПЛ/1), имеющих вид:

<описание форматов> ::= FORMAT(<элемент>{,<элемент>});

<элемент> ::= ? <формат> ¦ k1(<формат>{,<формат>}) ?

<формат> ::= ? A(k2) ¦ X(k2) ¦ SKIP(k1) ¦ F(k4[,k5]) ¦ E(k6,k7) ¦ <элемент> ?

где k1 - k7 - целые числа без знака.

Семантика: Сообщать об ошибках, если k1 > 10; k2 > 50; k4 > 33 и k4 < 4, если присутствует k5 ; k5 > k4-3; 8 > k6 > 37; k7 > k6-7. Осуществить вывод на экран информации по заданному формату: SKIP - переход на новую строку, с обозначением "|" для пустой стpоки, Х - обозначить символом "-", A - "А", знак числа и порядка - "З", цифр мантиссы и порядка - "Ц".

Пример правильной цепочки:

FORMAT (X(5),3(A(2),X(2),F(3),X(1)), SKIP(3), X(7), 2(F(10,5)), X(2), E(10,4), SKIP(2), 4(X(10), A(5), F(5), 2(X(3), A(2), 3(F(2), A(1))), SKIP(1)), X(20),A(10));

Результат работы программы для данного оператора:

-----АА--ЗЦЦ-АА--ЗЦЦ-АА--ЗЦЦ-

-------ЗЦЦЦ.ЦЦЦЦЦЗЦЦЦ.ЦЦЦЦЦ--ЗЦ.ЦЦЦЦЕЗЦЦ

----------АААААЗЦЦЦЦ---ААЗЦАЗЦАЗЦА---ААЗЦАЗЦАЗЦА

--------------------АААААААААА

Вариант 6

Построить синтаксический анализатор для цепочек автоматного языка операторов описания пеpеменных (Модула-2), имеющих вид:

<описание пеpеменных> ::= VAR <описание>;{<описание>;}

<описание> ::= @{,@}:[ARRAY <диапазон>{,<диапазон>} OF]<тип>

<диапазон> ::= [k1..k2]

<тип> ::= ? CARDINAL ¦ INTEGER ¦ REAL ¦ CHAR ¦ SHORTCARD ¦ SHORTINT ¦ LONGCARD ¦ LONGINT ¦ LONGREAL ¦ BOOLEAN ¦ ADDRESS ¦ BYTE ¦ WORD ?

Пpимеp пpавильного оператора:

VAR abc, A12C3,Ijk: CARDINAL;

s,st,S: ARRAY [0..79] OF CHAR; abcdef: LONGINT;

MasF: ARRAY [10..20],[5..19] OF BOOLEAN; Re: REAL;

Семантика: Сообщать об ошибках, если k1 > k2, объем памяти под переменную больше 64 Кбайт. Сфоpмиpовать упорядоченный по именам список-таблицу пеpеменных с указанием имени, типа, pазмеpности, диапазона изменения индексов и объема памяти, выделяемой под переменную (кроме первых двух символьных полей таблицы, все остальные поля представлять в числовой форме).

Вариант 7

Построить синтаксический анализатор для цепочек автоматного языка операторов заголовка цикла (Модула-2), имеющих вид:

<заголовок цикла> ::= FOR <паpаметp>:=<значение> TO <значение>

[BY <значение>] DO

<параметр> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ?

<значение> ::= <операнд2>{<операция><операнд2>}

<операнд2> ::= ? <параметр> ¦ k ?

Примеры правильных цепочек:

FOR par[1,yy+23 MOD 7 DIV 2-1*3,kkk]:=ijk+aa[1,h-2] TO kkk*24 DIV 3

BY aa[3,4]-3 DO

FOR ijk:=1444-7 DIV 12 * 3 TO 12345 BY 23-1*5 DIV 2 DO

Семантика: Сформировать списки @ и k в числовой форме. Если все значения в операторе представляют собой выражения над константами, то определить сколько раз будет выполняться цикл.

Вариант 8

Построить синтаксический анализатор для цепочек автоматного языка операторов цикла (Модула-2), имеющих вид:

<цикл> ::= REPEAT {<присваивание>;} UNTIL <условие>;

<присваивание> ::= <левая часть>:=<правая часть>

<левая часть> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ >> ¦ << ?

<правая часть> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? <левая часть> ¦ k ?

<условие> ::= <правая часть1>{<операция2><правая часть1)}

<операция2> ::= ? = ¦ # ¦ < ¦ > ¦ >= ¦ <= ¦ <> ¦& ¦ AND ¦ OR ?

<правая часть1> ::= [ ? NOT ¦ ~ ? ]<правая часть2>

<правая часть2>::=? (<правая часть>) ¦ (k IN <левая часть>) ?

Примеры правильных цепочек:

REPEAT UNTIL (7 IN abcd) & ~(5 IN aa[1,i+k MOD 4]);

REPEAT

aaa:=a+b-c[11,i*j DIV 2 -1,k+zzz123z]*1234 MOD 25;

bb[j+i>>2,12,34,ikj]:=bb[j+i>>2,12,34,ikj]+1;

i:=i-2; j:=i*k+3;

UNTIL (aaa) > (j+2) OR (i+c[1,i DIV 2,k+zzz123z] MOD 5)=(0) AND NOT(3 IN xx);

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 9

Построить синтаксический анализатор для цепочек автоматного языка операторов цикла (Модула-2), имеющих вид:

<цикл> ::= WHILE <условие> DO {<присваивание>;} END;

<присваивание> ::= <левая часть>:=<правая часть>

<левая часть> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ >> ¦ << ?

<правая часть> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? <левая часть> ¦ k ?

<условие> ::= <правая часть1>{<операция2><правая часть1)}

<операция2> ::= ? = ¦ # ¦ < ¦ > ¦ >= ¦ <= ¦ & ¦ AND ¦ OR ?

<правая часть1> ::= [ ? NOT ¦ ~ ? ]<правая часть2>

<правая часть2>::=? (<правая часть>) ¦ (k IN <левая часть>) ?

Примеры правильных цепочек:

WHILE (7 IN abcd) & ~(5 IN aa[1,i+k MOD 4]) DO END;

WHILE (aaa) > (j+2) OR (i+c[1,i DIV 2,k+zzz123z] MOD 5)=(0)

AND NOT(3 IN xx) DO

aaa:=a+b-c[11,i*j DIV 2 -1,k+zzz123z]*1234 MOD 25;

bb[j+i>>2,12,34,ikj]:=bb[j+i>>2,12,34,ikj]+1;

i:=i-2; j:=i*k+3;

END;

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Вариант 10

Построить синтаксический анализатор для цепочек автоматного языка операторов ветвления (Модула-2), имеющих вид:

<ветвление> ::= IF <условие> THEN {<присваивание>;}

{ELSIF <условие> THEN {<присваивание>;}}

[ELSE {<присваивание>;}]

END;

<присваивание> ::= <левая часть>:=<правая часть>

<левая часть> ::= @[[<список индексов>]]

<список индексов> ::= <индекс>{,<индекс>}

<индекс> ::= <операнд1>{<операция1><операнд1>}

<операнд1> ::= ? @ ¦ k ?

<операция1> ::= ? + ¦ - ¦ * ¦ MOD ¦ DIV ¦ >> ¦ << ?

<правая часть> ::= <операнд2>{<операция1><операнд2>}

<операнд2> ::= ? <левая часть> ¦ k ?

<условие> ::= <правая часть1>{<операция2><правая часть1)}

<операция2> ::= ? = ¦ # ¦ < ¦ > ¦ >= ¦ <= ¦ & ¦ AND ¦ OR ?

<правая часть1> ::= [ ? NOT ¦ ~ ? ]<правая часть2>

<правая часть2>::=? (<правая часть>) ¦ (k IN <левая часть>) ?

Пример правильной цепочки:

IF (7 IN abcd) & ~(5 IN aa[1,i+k MOD 4]) THEN l:=l+1;

ELSIF (aaa) > (j+2) OR (i+c[1,i DIV 2,k+zzz123z] MOD 5)=(0)

AND NOT(3 IN xx) THEN

aaa:=a+b-c[11,i*j DIV 2 -1,k+zzz123z]*1234 MOD 25;

bb[j+i>>2,12,34,ikj]:=bb[j+i>>2,12,34,ikj]+1;

i:=i-2; j:=i*k+3;

ELSIF aabbcc THEN

i:=i+1;

ELSE i:=j+b<<4*kkk[1,hg]; END;

Семантика: Сформировать безповторные упорядоченные списки @ и k в числовой форме.

Список рекомендуемой литературы

1. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ/ А. Ахо, Д. Ульман. - М.: Мир, 1978.

2. Ахо, А. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция/ А.Ахо, Д. Ульман. - М.:Мир, 1978.

3. Братчиков, И.Л. Синтаксис языков программирования/И.Л. Братчиков. - М.: Наука, 1975.

4. Гилл, А. Введение в теорию конечных автоматов/А.Гилл. - М.: Наука, 1966.

5. Гинзбург, С. Математическая теория контекстно-свободных языков/С.Гинзбург. - М.: Мир, 1970.

6. Гладкий, А.В. Формальные грамматики и языки/А.В.Гладкий. - М.: Наука, 1973.

7. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин/Д.Грис. - М.: Мир, 1975.

8. Гросс, М. Теория формальных грамматик/ М.Гросс, А. Лантен. - М.: Мир, 1971.

9. Донован, Д. Системное программирование/Д.Донован.- М.:Мир, 1975.

10.Лебедев, В.Н. Введение в системы программирования/В.Н.Лебедев.- М.:Статистика, 1975.

11. Льюис, Ф. Теоретические основы проектирования компиляторов/Ф.Льюис, Д.Розенкранц, Р.Стирнз - М.: Мир, 1979.

12. Семантика языков программирования. Сборник статей.- М.:Мир,1980.

13.Шамашов, М.А.Теория формальных языков. Грамматики и автоматы. Учебное пособие./М.А.Шамашов.-Самара: Самарский муниципальный комплекс непрерывного образования «Университет Наяновой», 1996, 92 с.

14.Хантер, Р. Проектирование и конструирование компиляторов/Р.Хантер. – М.:Финансы и статистика, 1984.

15.Хомский, Н. Формальные свойства грамматик/Н.Хомский// Кибернетический сборник, новая серия - вып. 2. - М.: ИЛ, 1966.

16.Хомский, Н. Алгебраическая теория контекстно-свободных языков/ Н. Хомский, М. Шютценберже // Кибернетический сборник, новая серия, вып. 3. - М.: ИЛ, 1966.

17.Хопгуд, Ф. Методы компиляции/Ф. Хопгуд.- М.:Мир, 1972.

18. Форстер, Дж. Автоматический синтаксический анализ/Дж. Фостер.-М.:Мир, 1972.

19.Шамашов, М.А. Основные структуры данных и алгоритмы компиляции: учеб. пособие/М.А.Шамашов.- Самара: Научно-внедренческая фирма «Сенсоры, модули, системы», 1999. –115 с.

20.Шамашов, М.А. Синтаксический анализ автоматных языков. Метод. указания/ М.А. Шамашов, Л.Ф. Штернберг. - Куйбышев: КуАИ, 1990.

21. Штернберг, Л.Ф. Теория формальных грамматик/Л.Ф. Штернберг. - Куйбышев: КуАИ, 1979.

22. Языки и автоматы: сб. статей. - М.: Мир, 1975.

Учебное издание

⇐ Предыдущая 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2021

Поиск по сайту: