Сист. прогр. Ч2 (Методические указания к выполнению лабораторных работ по СПО), страница 14

Удобно было бы иметь какое-то обозначение для класса всех возможных конечных строк алфавита Т. Обозначим его через Т*. Для любого множества U множество всех возможных конкатенаций элементов этого множества обозначим через U*. Для обозначения строк будем использовать строчные греческие буквы. Буквой λ будем обозначать «нулевую» или «пустую» строку (т. е. строку, в которой отсутствуют элементы).

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

Определение 2. Язык L есть подмножество множества конечных строк в алфавите Т. Мы будем писать Lс Т*.

ПОСТРОЕНИЕ ФОРМАЛЬНОГО ОПИСАНИЯ

Обратимся к примеру из синтаксиса английского языка. Английский язык - не просто произвольные группы слов, в нем имеется вполне определенная структура.

каречав

предложение

N P VP

а ртикль существительное глагол наречие

T he student studies hard

Рис.16.1

Например, предложение «The student studies hard» может быть представлено в виде структуры, показанной на рис. 16.1. Здесь можно выделить именную группу (NP) и глагольную группу (VP), которые затем подразделяются на отдельные слова. Поскольку все предложения имеют определенную структуру, ее можно порождать последовательными шагами, тем самым строя сложные предложения. Мы будем представлять структуры графически в виде синтаксического дерева; ветви, исходящие из узла дерева, указывают логические разветвления.

Например, мы можем начать разбор с узла «предложение» и заменить его на пару NP и VP, построив тем самым одну из возможных форм предложения. Это удобно записывать в таком виде:

предложение → NP VP

Из контекста ясно, что NP представляет лингвистический класс «именная группа». На рис. 16.1 необходимо различать строку «NP», которая может заменяться строкой «артикль», и строку «The», которая ничем не может быть заменена. Имена классов отличаются от слов языка с помощью метаскобок «﴾» и «﴿», в которые заключаются символы, представляющие лингвистические классы.

Шаг Структура Правила

a) предложение

b) ﴾NP ﴿ ﴾ VP) (D

c) (артикль) (существительное) (VP) (2)

d) (артикль) (существительное) (глагол) (наречие) (4)

e) The (существительное) (глагол) (наречие) (5)

О The student (глагол) (наречие) (6)

g) The student studies (наречие) (7)

h) The student studies hard (8)

Рис. 16.2.

Тогда первые правила принимают вид:

(1) (предложение)→(NP)(VP)

(2) (NP)→ (артикль) (существительное).

Аналогично, глагольная группа (VP) состоит из глагола и наречия

(3) (VP) → (глагол)

(4) (VP)→ (глагол) (наречие)

Принятые нами правила трансформации или переписи структуры позволяют группе (VP) содержать или не содержать одно наречие, в то время как группа (NP) должна иметь в точности один артикль.

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

(5) (артикль) -> The

(6) (существительное) -> student

(7) (глагол) -> studies

(8) (наречие) -> hard

(9) (наречие) -> slowly

Используя эти правила, можно построить любое предложение, заменяя символы лингвистических классов на соответствующие им структуры. На рис. 16.2 дается вывод предложения

«The student studies hard». Используя на последнем шаге правило

(наречие)→ slowly

вместо предыдущего предложения можно получить предложение „The student studies slowly".

Правила трансформации структур определяют форму порождаемого языка. В нашем примере язык является только малым подмножеством английского языка.

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

ФОРМАЛЬНЫЕ ГРАММАТИКИ

Предыдущий пример показал способ формализации процесса порождения строк языка: прежде чем рассматривать формальное описание, необходимо проанализировать структуру предложения. Мы использовали два типа символов: одни, заключенные в скобки, для представления лингвистических классов (грамматических единиц, используемых на промежуточных шагах формального процесса порождения) и другие, состоящие из латинских букв, из которых в конечном итоге формировались генерируемые предложения. Поскольку одни символы появляются в предложении, когда генерация заканчивается, а другие только на промежуточных шагах, они называются терминальными и нетерминальными символами соответственно. Один нетерминальный символ, так называемый начальный символ (в нашем примере <предложение>) выделяется как символ, с которого начинается порождающий процесс.

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

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

17. КОМПИЛЯТОРЫ

В данной главе ставятся две цели:

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

2. Оценить трудоемкость и «стоимость» реализации и ис­пользования отдельных свойств языков.

Чтобы достичь этого, мы разбили главу на три части.

Часть 1 содержит простой пример и начальные представления об общей схеме компилятора.

Часть 2 посвящена тщательному разбору общей схемы и внут­ренней работы компилятора.

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

ПОСТАНОВКА ЗАДАЧИ

Компилятор воспринимает на входе программу, написанную на языке высокого уровня, и производит ее эквивалент на язы­ке машины. В этой части мы рассмотрим простую программу на языке C и познакомимся с задачами, которые возникают при ее компиляции (рис. 17.1).

# include <stdio.h>

void main () {

long k;

int n;

printf ( “\n Введите число \n”);

n=0;

scanf (“ %ld”,&k);

While (k > 0 )

{

k /= 10;

n++;

}

printf (“\n Во введенном числе цифр %d”, n);

}

Рис. 17.1. Пример программы на языке C.

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

1. Предварительно с помощью препроцессора подставить файл stdio.h. Распознать определенные строки как базовые элементы языка, т. е. определить, что k, n переменные, void, scfnf, printf -функции, знаки “=”, “/=” и “++” есть знаки опе­раций.

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

3. Распределить память для переменных данной программы.

4. Сгенерировать соответствующие объектные коды.

ЗАДАЧА № 1 —РАСПОЗНАВАНИЕ БАЗОВЫХ ЭЛЕМЕНТОВ

Грамматический разбор исходной программы на соответ­ствующие синтаксические классы называется лексическим ана­лизом. Программа просматривает исходную строку и делит ее на части.

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

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

Литература.

1. Дж. Донован. Системное программирование. М. Мир. 1975

2. Хемминг Р.В. Численные методы. Наука,М. 1972.

3. Кнут Д. Искусство программирования для ЭВМ. Мир.М. 1975.

4. Абель П. Язык Ассемблера для IBM PC и программирования. Высшая школа. М. 1992.

5. Шагурин И.И., Бердышев Е.М., Микропроцессоры семейства Intel P6.Грааль., Пушкино М.о. 2000.