Главная
страница 1страница 2страница 3страница 4




Курс "Основы построения трансляторов"
Здесь размещены методические материалы по курсу "Основы построения трансляторов", который включен в дисциплину "Системное программное обеспечение". Курс читается в 8 семестре студентам заочного отделения специальности 2201 факультета Автоматики и вычислительной техники (АВТФ) Новосибирского государственного технического университета (НГТУ).

По всем вопросам обращайтесь к автору курса Романову Евгению Леонидовичу romanow@vt.cs.nstu.ru или на сайт кафедры вычислительной техники НГТУ http://ermak.cs.nstu.ru .

Все изложенное уложено в http://ermak.cs.nstu.ru/trans/tr.arj архив - 97Kb(Word) или http://ermak.cs.nstu.ru/trans.arj архив - 356Kb(HTML).

1. Введение. Сущность трансляции. Основные термины и определения

1.1. Фазы трансляции и выполнения программы

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

Подготовка программы начинается с редактирования файла, содержащего текст этой программы, который имеет стандартное расширение для данного языка. Затем выполняется его трансляция, которая включает в себя несколько фаз: препроцессор, лексический, синтаксический, семантический анализ, генерация кода и его оптимизация. В результате трансляции получается объектный модуль -некий "полуфабрикат" готовой программы, который потом участвует в ее сборке. Файл объектного модуля имеет стандартное расширение ".obj". Компоновка (сборка) программы заключается в объединении одного или нескольких объектных модулей программы и объектных модулей, взятых из библиотечных файлов и содержащих стандартные функции и другие полезные вещи. В результате получается исполняемая программа в виде отдельного файла (загрузочный модуль, программный файл) со стандартным расширением -".exe", который затем загружается в память и выполняется.

Препроцессор


Собственно говоря, препроцессор не имеет никакого отношения к языку. Это предварительная фаза трансляции, которая выполняет обработку текста программы, не вдаваясь глубоко в ее содержание. Он производит замену одних частей текста на другие, при этом сама программа так и остается в исходном виде.
ПРЕПРОЦЕССОР -- предварительная фаза трансляции на уровне преобразования исходного текста программы

В языке Си директивы препроцессора оформлены отдельными строками программы, которые начинаются с символа "#". Здесь мы рассмотрим наиболее простые и "популярные".


#define идентификатор строка_текста
Директива обеспечивает замену встречающегося в тексте программы идентификатора на соответствующую строку текста. Наиболее часто она применяется для символического обозначения константы, которая встречается многократно в различных частях программы. Например, размерность массива:
#define SIZE 100

int A[SIZE];

for (i=0; iВ данном примере вместо имени SIZE в текст программы будет подставлена строка, содержащая константу 100. Теперь, если нас не устраивает размерность массива, нам достаточно увеличить это значение в директиве define и повторно оттранслировать программу.
#define идентификатор(параметры) строка_с_параметрами
Директива отдаленно напоминает определение функции с формальными параметрами, где вместо тела функции используется строка текста. Если препроцессор находит в тексте программы указанный идентификатор со списком фактических параметров в скобках, то он подставляет вместо него соотвествующую строку из директивы define с заменой в строке формальных параметров на фактические. Основное отличие от функции: если функция реализует подобные действия (подстановка параметров, вызов) во время работы программы, то препроцессор -еще до трансляции. Кроме этого, директива define позволяет оформить в таком виде любую часть программы, независимо от того, законченная это конструкция языка или ее фрагмент. В следующем примере стандартный заголовок цикла for представлен в виде директивы define с параметрами:
#define FOR(i,n) for(i=0; i

FOR(k,20) A[k]=0; // for(k=0; k<20; k++) A[k]=0;

FOR(j,m+2) {...} // for(j=0; jВ таком варианте директива define представляет собой МАКРООПРЕДЕЛЕНИЕ, а замена в тексте программы идентификатора с параметрами на строку - МАКРОПОДСТАНОВКУ.
#include <имя_файла>

#include "имя_файла"


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

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

Аналогичные средства в других языках программирования носят название МАКРОПРОЦЕССОР, МАКРОСРЕДСТВА.

Трансляция и ее фазы

Собственно трансляция начинается с лексического анализа программы. ЛЕКСИКА языка программирования -это правила "правописания слов" программы, таких как идентификаторы, константы, служебные слова, комментарии. Лексический анализ разбивает текст программы на указанные элементы. Особенность любой лексики - ее элементы представляют собой регулярные линейные последовательности символов. Например, ИДЕНТИФИКАТОР - это произвольная последовательность букв, цифр и символа "_", начинающаяся с буквы или "_".

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

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

ГЕНЕРАЦИЯ КОДА - это преобразование элементарных действий, полученных в результате лексического, синтаксического и семантического анализа программы, в некоторое внутреннее представление. Это могут быть коды команд, адреса и содержимое памяти данных, либо текст программы на языке Ассемблера, либо стандартизованный промежуточный код (например, P-код). В процессе генерации кода производится и его оптимизация.

Модульное программирование, компоновка

Полученный в результате трансляции ОБЪЕКТНЫЙ МОДУЛЬ включает в себя готовые к выполнению коды команд, адреса и содержимое памяти данных. Но это касается только собственных внутренних объектов программы (функций и переменных). Обращение к внешним функциям и переменным, отсутствующим в данном фрагменте программы, не может быть полностью переведено во внутреннее представление и остается в объектном модуле в исходном (текстовом) виде. Но если эти функции и переменные отсутствуют, значит они должны быть каким-то образом получены в других объектных модулях. Самый естественный способ - написать их на том же самом Си и оттранслировать. Это и есть принцип МОДУЛЬНОГО ПРОГРАММИРОВАНИЯ - представление текста программы в виде нескольких файлов, каждый из которых транслируется отдельно. С модульным программированием мы сталкиваемся в двух случаях:

- когда сами пишем модульную программу;

- когда используем стандартные библиотечные функции.

БИБЛИОТЕКА ОБЪЕКТНЫХ МОДУЛЕЙ - это файл (библиотечный файл), содержащий набор объектных модулей и собственный внутренний каталог. Объектные модули библиотеки извлекаются из нее целиком при наличии в них требуемых внешних функций и переменных и используются в процессе компоновки программы.

КОМПОНОВКА - это процесс сборки программы из объектных модулей, в котором производится их объединение в исполняемую программу и связывание вызовов внешних функций и их внутреннего представления (кодов), расположенных в различных объектных модулях. Подробно процесс компоновки применительно к языку Си рассмотрен в 4.6.

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

Сущность трансляции. Компиляция и интерпретация


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

КОМПИЛЯЦИЯ - преобразование объектов (данных и операций над ними) с входного языка в объекты на другом языке для всей программы в целом с последующим выполнением полученной программы в виде отдельного шага.

ИНТЕРПРЕТАЦИЯ - анализ отдельного объекта на входном языке с одновременным выполнением (интерпретацией).

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

Если посмотреть на эти различия несколько с другой стороны, то можно заметить, что интерпретатор непосредственно выполняет действия, связанные с определением или преобразованием объектов программы, а компилятор - переводит их на другой (не обязательно машинный язык). Отсюда можно сделать несколько выводов:

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

- процессор и память любого компьютера (а в широком смысле и вся программная среда, создаваемая операционной системой, является ИНТЕРПРЕТАТОРОМ машинного кода);

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

Выходной язык компилятора может быть машинным языком для компьютера с другой архитектурой, нежели тот, в котором работает компилятор. Такой компилятор называется КРОСС-КОМПИЛЯТОРОМ, а сама система программирования КРОСС-СИСТЕМОЙ. Такие системы используются для разработки программ для архитектур, не имеющих собственных операционных систем или систем программирования (контроллеры, управляющие микропроцессоры).

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

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

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

- язык программирования Java аналогично был разработан для обеспечения переносимости различных приложений в среде Internet.

Структура транслятора

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

Отдельные фазы трансляции могут быть связаны между собой различным образом, через данные в памяти или через файл, что не меняет сущности процесса:

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

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



1.2. Связывание. Сравнительная характеристика языков программирования
Трансляция и последующие действия по подготовке программы к выполнению представляют собой процесс преобразования программы, записанной на некотором формальном языке, в другую формальную систему - архитектуру компьютера, в которой она может быть выполнена (интерпретирована). Для понимания этого процесса, а также отличий, имеющихся в различных языках программирования, в [3] введено понятие СВЯЗЫВАНИЯ, а также ВРЕМЕНИ СВЯЗЫВАНИЯ.
СВЯЗЫВАНИЕ -- процесс установления соответствия между объектами и их свойствами программы на формальном языке программирования (операции, операторы, данные) и объектами архитектуры компьютера (команды, адреса.
ВРЕМЕНЕМ СВЯЗЫВАНИЯ называется соответственно фаза подготовки программы к выполнению (трансляция, компоновка, загрузка), на которой производится это действие. Заметим, что различные характеристики одного и того же объекта (например, переменной) могут связываться с различными элементами архитектуры в разное время, то есть процесс связывания не является одномоментным. Для начала перечислим возможные времена связывания:

  • при определении языка;

  • при реализации компилятора;

  • во время трансляции, включающей в себя:

  • препроцессор (макропроцессор)

  • лексический, синтаксический и семантический анализ, генерацию кода и его оптимизацию;

  • компоновку (связывание);

  • во время загрузки программы;

  • во время выполнения программы, в том числе:

  • при входе в модуль (процедуру, функцию);

  • в произвольной точке программы.

В качестве примера рассмотрим простейший фрагмент программы, для которого перечислим более-менее полный перечень времен связывания его различных свойств с элементами архитектуры компьютера:
int a,b; … a+b …


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

  2. Конкретная размерность переменной int определяется при реализации соответствующего компилятора.

  3. Имя a может быть определено в конструкции вида #define a 0x11FF. В этом случае имя (псевдо-переменная) связывается со своим значением на первой фазе трансляции - в препроцессоре.

  4. Если переменная определяется обычным способом в виде int a; то связывание переменной с соответствующим ей типом происходит во время трансляции (на фазе семантического анализа).

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

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

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

- при загрузке программы в некоторую область памяти (например, в DOS или в режиме эмуляции DOS в WINDOWS) она может размещаться не с самого начала этой области. В этом случае осуществляется привязка адресов переменных, заданных в относительных адресах от начала программного модуля к адресам памяти с учетом перемещения программного модуля (так называемый ПЕРЕМЕЩАЮЩИЙ ЗАГРУЗЧИК, которая имеет место для exe-файлов в DOS).

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



  1. Если переменная определяется как автоматическая (локальная внутри тела функции или блока), то она размещается в стеке программы:

- во время трансляции определяется ее размерность и генерируются команды, которые резервируют под нее память в стеке в момент входа в тело функции (блок). То есть в процессе трансляции переменная связывается только с относительным адресом в стеке программы;

- связывание локальным переменной с ее адресом в сегменте стека осуществляется при выполнении в момент входа в тело функции (блок). Благодаря такому способу связывания в рекурсивной функции существует столько “экземпляров” локальных переменных, сколько раз функция вызывает сама себя.



  1. Тип операции “+” в конкретном выражении a+b определяется при трансляции в зависимости от типов операндов. В данном случае генерируется операция целого сложения.

  2. С точки зрения времени связывания понятие ИНИЦИАЛИЗАЦИЯ внешних переменных можно определить как связывание переменных с их значениями в процессе трансляции программы (int a=10;) С этой точки зрения обычное присваивание можно рассматривать как связывание переменной с ее значением во время выполнения программы.

С понятием связывания тесно переплетаются понятия СТАТИЧЕСКОГО и ДИНАМИЧЕСКОГО определения данных. Статически определенные данные имеют раннее время связывания - обычно во время трансляции программы, динамические данные - позднее, во время выполнения. Этот принцип легко проиллюстрировать средствами языка Си, в котором все действия, связанные с динамическими данными и поздним связыванием производятся только в явном виде. Возьмем, к примеру, массивы:

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


int A[100];
- динамический массив, размерность которого определяется в процессе работы программы, может быть вычислена в момент создания, но затем не меняется, может быть представлен в Си указателем на динамическую переменную (массив) соответствующей размерности, создаваемую и уничтожаемую внешними функциями. Легко представить себе язык программирования, в котором массивы такого рода определяются в самом трансляторе, в этом случае можно говорить о связывании массива с его размерностью и памятью во время выполнения программы, например, в момент входа в модуль (блок):
double *p;

p = malloc(sizeof(double)*n); // или

p = new double[n];

for (i=0; i

// ПРИМЕР СИНТАКСИСА ДИНАМИЧЕСКОГО МАССИВА

// n = getnum();

// ReDim double A[n];
- виртуальный массив, размерность которого может меняться уже в процессе работы программы, по мере заполнения его данными, в Си также может быть смоделирован с использованием функций перераспределения динамической памяти realloc. При определении таких массивов в самом трансляторе можно говорить о связывании массива с его размерностью и памятью во время выполнения программы, причем многократной, во время заполнения его данными, то есть в любой точке программы:
double *p; int n=10;

p = malloc(sizeof(double)*n);

for (i=0; i<10000; i++)

{

if (i >= n) // Если надо,



{ n = n+10; // увеличить размерность

p = realloc(p, sizeof(double)*n);

}

p[i] = 5.44



}

// ПРИМЕР СИНТАКСИСА ВИРТУАЛЬНОГО МАССИВА

// ReDim double A[];

// for (i=0; i<10000; i++) A[i]=5.44;


- виртуальный массив, в котором может меняться не только размерность, но и типы хранящихся в нем элементов, можно смоделировать в Си с помощью динамического массива указателей на переменные - элементы массива:
void **p; int n=10;

p = malloc(sizeof(void*)*n);

int b; double c;

i = 5;


if (i >= n) // Если надо,

{ n = i+10; // увеличить размерность

p = realloc(p, sizeof(void *)*n);

}

p[i] = &b;



// ПРИМЕР СИНТАКСИСА ВИРТУАЛЬНОГО МАССИВА

// С ПРОИЗВОЛЬНЫМИ ТИПАМИ ЭЛЕМЕНТОВ

// ReDim A[];

// int b; double c;

// A[5] = b;

// A[66]= c;


Из рассмотренного примера видно, что реализация позднего связывания в языках программирования связана с использованием неявных (скрытых) указателей на структуры данных. Это предположение можно подтвердить и примером связывания для к такого объекта, как функция:

- тело функции является статическим объектом. То есть память под нее выделяется во время трансляции (когда генерируется программный код) в создаваемом объектном модуле. Что же касается вызова функции, то связывание вызова функции с самой функцией может производиться на разных этапах;

- если функция вызывается в том же самом модуле, где она определена, то связывание вызова функции с ее телом (адресом) осуществляется в процессе трансляции;

- если функция определена в другом модуле (частный случай, библиотека), то связывание вызова функции с ее телом (адресом) осуществляется при компоновке. Для этой цели тело функции в объектном модуле сопровождается информацией, именуемой “точкой входа”, сам вызов сопровождается “внешней ссылкой”, а для корректного формирования вызова Си-компилятору необходимо объявить прототип внешней функции. Для библиотечных функций необходимо подключить заголовочный файл, в котором они содержатся.

В технологии объектно-ориентированного программирования существует термин ПОЛИМОРФНАЯ ФУНКЦИЯ. В Си++ она называется ВИРТУАЛЬНОЙ. На самом деле она представляет собой группу одноименных функций, определенных соответственно для группы родственных (производных классов). При вызове такой функции для объекта обобщающего их класса (базового класса) программа должна идентифицировать, к какому конкретно классу относится текущий объект и выбрать соответствующую ему функцию. С точки зрения понятия связывания это означает, что связывание вызова функции с ее телом может осуществляться в таком случае во время, и только во время работы программы. Действительно, в Си++ механизм виртуальных функций реализуется при помощи массива указателей на функции, который назначения объекту в момент его создания, то есть при выполнении программы.

К позднему (динамическому) связыванию функций относятся и используемые в Windows ДИНАМИЧЕСКИ СВЯЗЫВАЕМЫЕ БИБЛИОТЕКИ (DLL-Dynamic Linking Library) . Фактически в них процесс связывания вызова и тела внешней функции, выполняемый при компоновке, откладывается до момента загрузки программы. В этом случает программный файл содержит несвязанные вызовы внешних функций (внешние ссылки) и перечень используемых библиотек. Загрузка требуемых библиотек и связывание внешних ссылок и точек вход производится в момент загрузки программного файла. Этот способ дополнительно позволяет разделять одну и ту же библиотеку несколькими программами в общем адресном пространстве.

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

2.1. Сущность лексического анализа

Лексический анализ (ЛА) является первой фазой трансляции. Термин “лексика” в обычном языке подразумевает правила составления слов из букв. В языке программирования ЛА соответствует фаза трансляции, в которой из последовательности отдельных литер (символов, букв языка) выделяются слова (лексемы, символы следующей фазы - синтаксического анализа). Типичными словами в языке программирования являются такие компоненты как КОММЕНТАРИИ, ИДЕНТИФИКАТОРЫ, КОНСТАНТЫ, СЛУЖЕБНЫЕ СЛОВА, ЗНАКИ ОПЕРАЦИЙ.

ЛА является наиболее простой и формализованной фазой трансляции. Любой алгоритм ЛА базируется на последовательном просмотре текста, с возвратом и перечитыванием из входной последовательности не более чем одного символа, поэтому программу ЛА иногда называют СКАНЕРОМ. Формальной основой описания процесса ЛА являются конечные автоматы.

Простейший лексический анализатор
Простейший лексический анализатор можно построить, не прибегая ни к каким формальным методам, просто анализируя последовательности символов, образующих лексические единицы. Соответствующий пример приведен в файле hardlex.cpp. Из приведенного ниже фрагмента видно, что программа "зацепляет" первый символ, определяющий начало лексической единицы (букву, цифру и т.д.) а затем просматривает строку до конца элемента лексики (идентификатора, константы). Некоторые лексические единицы при этом имеют еще и собственное значение, которое выходит за рамки алгоритма распознавания. Например, для идентификатора и константы важен не только факт их распознавания, но и их значение, заключенное в цепочке символов. Поэтому анализатор перед началом очередного цикла фиксирует начало распознаваемой последовательности символов, для сохранения ее значения.
while (1)

{ fix=i;


switch(s[i])

{

case '"': // Распознавание строковой константы ". . ."



// с двойными "" внутри

mmm: i++; while (s[i] !='"') i++;

i++; if (s[i]=='"') goto mmm;

lexem(1); break;

case '/': i++; // Распознавание / и /*

if (s[i]!='*')

{ lexem(14); break; }

// Распознавание комментария /* ... */

n1: while (s[i] !='*') i++;

i++; if (s[i]=='/')

{ i++; lexem(2); break; }

goto n1;


case '+': i++; // Распознавание += и +

if (s[i]=='=')

{ i++; lexem(5); }

else lexem(15);

break;

case '<': i++; // Распознавание << и <



if (s[i]=='<')

{ i++; lexem(6); }

else lexem(16); break;

default: if (isalpha(s[i]))

// Распознавание идентификатора

{ i++; while (isalpha(s[i])) i++;

lexem(11); break; }

// Распознавание константы

if (isdigit(s[i]))

{ i++; while (isdigit(s[i])) i++;

lexem(12); break; }

2.2. Лексический анализатор как конечный автомат

Формальной основой ЛА являются конечные автоматы (КА). КА является формальным математическим аппаратом, широко используемым в компьютерной технике. В проектировании аппаратных средств КА используются при разработке управляющей схемы, реализующей заданный алгоритм. Точно так же, в любой программе достаточно сложная логика последовательности действий может быть реализована как напрямую в виде последовательности условных и циклических конструкций, так и в виде программного КА. Для начала дадим неформальное определение КА.

КОНЕЧНЫМ АВТОМАТОМ является система, которая в каждый момент времени может находится в одном из конечного множества заданных состояний. Каждый шаг (переключение) автомата состоит в том, что при нахождении в определенном состоянии при поступлении на вход одного из множества входных сигналов (воздействий) он переходит в однозначно определенное состояние и вырабатывает определенное выходное воздействие. Легче всего представить себе поведение КА в виде его диаграммы состояний-переходов.

Таким образом, если поведение какого-либо объекта можно описать набором предложений вида: находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D - то такая система будет представлять собой конечный автомат. На диаграмме состояний-переходов каждому состоянию соответствует кружок, каждому переходу - дуга со стрелкой. Каждое состояние имеет свой “смысл”, заключенный в подписи. Каждый переход осуществляется только при выполнении определенного условия, которое обозначено подписью под дугой. Кроме того, при выполнении перехода производится действие, при помощи которого автомат обнаруживает свое поведение извне.

У конечного автомата есть еще несколько условий работоспособности:

- автомат имеет некоторое начальное состояние, из которого он начинает работу;

- автомат имеет конечное число состояний;

в каждом состоянии не может быть одновременно справедливыми несколько условий перехода, то есть автомат должен быть ДЕТЕРМИНИРОВАННЫМ. Автомат не может перейти одновременно в несколько состояний и не может иметь таких условий перехода.

О том, что конечный автомат может использоваться при анализе последовательностей различных символов в строке, несложно убедиться на простом примере. Пусть требуется написать программу, которая исключает из строки комментарии вида “ /* ... */ ”

Прежде всего, необходимо определить состояния конечного автомата. Таковыми являются состояния программы, возможные при просмотре очередного символа строки:

- состояние 0 - идет обычный текст;

- состояние 1 - обнаружен символ “/”;

- состояние 2 - обнаружено начало комментария “/*”;

- состояние 3 - в комментарии обнаружен символ “*”.
Программа, представляющая собой КА, будет выглядеть следующим образом:
void f(char in[],char out[])

{int i, s, j;

for(i=0,s=0,j=0; in[i]!=0; i++)

switch(s)

{

case 0: if (in[i])!=’/’ out[j++] = in[i];



else s=1;

break;


case 1: if (in[i]!=’*’)

{out[j++]=in[i-1]; out[j++]=in[i]; s=0;}

else s=2;

break;


case 2: if (in[i]==’*’) s=3;

break;


case 3: if (in[i]==’/’) s=0;

break;


}

}
Подробнее рассмотрим характерные особенности этой программы:

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

- программа имеет переменную s, которая и представляет собой текущее состояние КА. В теле основного цикла программы выполняется переключение (switсh) по всем возможным значениям этой переменной - состояниям КА.

- в каждом состоянии реализуется логика его перехода в другие состояния на основе анализа текущего символа - входного сигнала и вырабатывается соответствующее действие. Например, в состоянии 1, когда программа уже обнаружила символ “/” - возможное начало комментария, она проверяет, не является ли текущий символ “*”. Если это так, автомат переводится в состояние 2 - нахождение внутри комментария, если нет, то в выходную строку переписывается предыдущий “/” и текущий символы, а автомат возвращается в состояние 0.

Диаграмма состояний и переходов лексического анализатора


Пониманию сущности конечного автомата может в значительной степени помочь ДИАГРАММА СОСТОЯНИЙ-ПЕРЕХОДОВ. Каждому состоянию автомата, которое на диаграмме отображается кружочком, соответствует “поведение” конечного автомата. Например, если автомат распознает константу как последовательность цифр, то он должен иметь состояние, которое можно назвать как “ожидание очередной цифры”. Переход автомата из одного состояния в другое отображается направленной дугой. Условие, при котором происходит этот переход, а также действие, которое осуществляет конечный автомат при переходе, подписываются над дугой. В лексическом анализаторе условием перехода является значение очередного символа строки, который анализируется, а неявным действием является продвижение к очередному символу в строке.

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


Используя диаграмму состояний-переходов, можно напрямую написать программу ЛА, опираясь на приведенный выше пример реализации автомата, обрабатывающего текст:

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

- программа имеет переменную состояния, по которой в теле цикла организуется переключение;

- каждой ветке переключателя соответствует одно состояние КА и один узел диаграммы состояний, в ней программируется “поведение” КА для данного состояния - анализируется текущий символ и по нему определяется новое состояние КА и производимое действие;

Лексический анализатор на основе конечного автомата

Диаграмма состояний-переходов является наглядным средством неформального проектирования ЛА. На самом деле существует другой способ проектирования таких программ, основанный на более регулярном и естественном представлении КА, и, в частности, КА для лексического анализа.

В программе определяется переменная - текущее состояние КА (ST);

Все множество входных символов разбивается на непересекающиеся множества - классы. Классы выбираются таким образом, чтобы обеспечивалось однозначное переключение КА, если анализируются не сами символы, а их классы. Например, если ЛА должен различать комментарии, идентификаторы, восьмеричные, десятичные и шестнадцатеричные и строковые константы, то множество символов необходимо разбить на следующие классы:

- цифра 0.

- цифры 1-7.

- цифры 8-9.

- буквы A-F,a-f.

- буква “x”.

- остальные буквы.

- символ “/”.

- символ “*”.

- символ “””.

- остальные символы.

Проще говоря, символы, на которые КА должен обеспечивать различную реакцию, должны быть разнесены в отдельные классы. Естественно, что определением класса символа должна заниматься отдельная функция. Для приведенного примера она имеет вид:
int class(char c)

{ switch ( c)

{

case ‘*’: return(7);



case ‘”’: return(8);

case ‘/’: return(6);

case ‘0’: return(0);

case ‘8’: return(2);

case ‘9’: return(2);

case ‘x’: return(3);

default: if (isdigit(с)) return(1);

if (isalpha(c))

{if ((touppeк(с)>=’A’)&&(toupper(с)<=’F’))

return(4);

return(5);

}

return(9); }}


Далее в программе необходимо определить матрицу переходов. Матрица переходов - это двумерный массив, который для каждой пары “состояние (строка) и класс символа (столбец)” определяет новое состояние, в которое он переводится. Номер этого состояния и находится в матрице. Матрица переходов строится по соответствующей диаграмме состояний-переходов и фактически определяет поведение КА. Принцип заполнения матицы прост: если в состоянии S1 и входном символе L1 на диаграмме имеется дуга (переход) в состояние S2 то элемент массива D[S1][K1] должен быть инициализирован значением S2, где K1=class(L1). В рассматриваемом примере матрица будет выглядеть так:

.

int D[11][10]= {



{ 2, 5, 5, 1, 1, 1, 6,-8, 9,-9 },

{ 1, 1, 1, 1, 1, 1,-1,-1,-1,-1 },

{ 5, 4, 5, 3,-4,-4,-4,-4,-4,-4 },

{ 3, 3, 3,-2, 3,-2,-2,-2,-2,-2 },

{ 4, 4,-3,-3,-3,-3,-3,-3,-3,-3 },

{ 5, 5, 5,-4,-4,-4,-4,-4,-4,-4 },

{-5,-5,-5,-5,-5,-5,-5, 7,-5,-5 },

{ 7, 7, 7, 7, 7, 7, 7, 8, 7, 7 },

{ 7, 7, 7, 7, 7, 7,-6, 7, 7, 7 },

{ 9, 9, 9, 9, 9, 9, 9, 9,10, 9 },

{-7,-7,-7,-7,-7,-7,-7,-7, 9,-7 } };
Тогда поведение конечного автомата программируется в первом приближении таким простым циклом:
for (ST=0,i=0;S[i]!=0;i++) {CL=class(S[i]);ST=D[ST][CL];}
Специфика программирования КА применительно к лексическому анализу заключается только в действиях, производимых автоматом. Целью ЛА является распознавание и выделение лексемы (слова) - последовательности символов. Поэтому в КА вводится множество заключительных состояний, в которых завершается распознавание. Действия, связанные с распознаванием, практически одинаковы для всех типов лексем (слов), поэтому в КА вводится множество заключительных состояний, по одному на каждый тип лексемы. Они имеют отрицательное значение, и по их обнаружении программа выполняет следующие действия:

формирует цепочку из накопленных символов - значение лексемы;

устанавливает тип распознанной лексемы в соответствии с номером конечного состояния КА;

- возвращает КА в исходное (нулевое состояние);

- поскольку обнаружение лексемы иногда происходит в тот момент, когда КА обрабатывает символ, уже к ней не относящийся, то программа должна “вернуть” во входную последовательность заданное число символов для повторного просмотра. Например, любая десятичная константа распознается, когда уже прочитан следующий за ней символ - не цифра. Его то и необходимо вернуть. Для этого в программе определяется массив, в котором для каждого заключительного состояния указано количество возвращаемых символов. Естественно, что его содержимое определяется конкретной лексикой.
int W[]={ 1,1,1,1,1,0,1,0,0 };

if (ST < 0)

{ int j; ST = -ST-1; // тип лексемы

i=i-W[ST]; // вернуть символы

printf(“%s “,out[ST]); // вывести цепочку

for (j=FIX; j

puts(“”);

ST=0; FIX=i; }


Для фиксации начала цепочки символов, образующих лексему (слово), в программе вводится переменная FIX, которая при любом переходе в начальное (нулевое) состояние запоминает расположение в строке текущего символа. Заготовка программы ЛА на основе конечного автомата находится в файле lexan.cpp.
3. Синтаксический анализ

3.1. Сущность синтаксического анализа

Сущность синтаксического анализа программы достаточно сложна, чтобы излагать ее "на пальцах". Даже такое средство представления как конечный автомат является недостаточно "мощным" для этого. В первом приближении это можно доказать, ссылаясь на вложенный характер конструкций языка. Элементы лексики представляют собой линейные последовательности, анализ которых и производится конечными автоматами. Синтаксис же предложения не является линейной структурой. Если определения элементов синтаксиса языка (выражения, операторы) являются теми единицами, из которых строится программа, то взаимоотношение этих единиц в конкретной программе может быть представлено в виде дерева. А с деревом тесно связаны такие понятия, как рекурсия и стек. Таким образом, интуитивно становится ясным, что для определения и анализа синтаксиса языка необходим математический аппарат, который допускает рекурсивное определение и порождение своих элементов, а при их анализе используются деревья, рекурсивные функции и работа со стеком.

Формальные грамматики и языки

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

множество терминальных символов T;

множество нетерминальных символов N;

начальный нетерминальный символ Z из множества N;

множество порождающих правил вида A ::= B, где B - цепочка из любых символов грамматики (N U T), A-цепочка, содержащая хотя бы один нетерминальный символ.

В дальнейшем мы будем представлять правила грамматики в таком виде:

.


следующая страница >>
Смотрите также:
Курс "Основы построения трансляторов"
925.66kb.
4 стр.
Программа по дисциплине «Лингвистические основы информатики» для специальности прикладная информатика в юриспруденции (351400)
78.73kb.
1 стр.
Пояснительная записка. Элективный курс "Основы журналистики"
113.4kb.
1 стр.
Учебный курс «Основы религиозных культур и светской этики»
33.93kb.
1 стр.
2 глава Теоретические основы построения агентно-ориентированной модели финансового рынка 6
418.53kb.
5 стр.
Курс лекций (введение в профессию "социальный педагог", основы социальной педагогики, основы социально-педагогической деятельности) "
4415.49kb.
24 стр.
Методологические основы построения платежного баланса России
49.72kb.
1 стр.
Принципы построения и основы конструирования приборов индивидуальной оптометрии
683.94kb.
5 стр.
Основы построения бизнес-инкубаторов Москва • Издательская корпорация «Логос» • 1999 ббк 65. 9(2)09
2957.87kb.
16 стр.
Программа дисциплины Основы театроведения для специальности 030200. 62 «Политология» подготовки бакалавра
55.11kb.
1 стр.
Программа дисциплины Основы театроведения для специальности 030200. 62 «Политология» подготовки бакалавра
55.26kb.
1 стр.
Курс «Основы кибернетики» для студентов специализации 01. 02. 09. 01
83.88kb.
1 стр.