yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->2 Элементы компиляции. Анализ формальных языков

Информатика

2 Элементы компиляции. Анализ формальных языков

 

2. 1Сведения о регулярных выражениях и грамматиках

Любой язык имеет свой алфавит.

Алфавит – это конечное множество I элементов, называемых символами.

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

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

§                    хn. Цепочка символов х повторяется (пишется без пробелов одна за другой) n раз. Например, abba2 – это abbaabba.

§                    хk. Цепочка символов х записывается в обратной последовательности. Например, portR  - это trop.

§                    xy. За цепочкой символов x без пробела помещается цепочка символов y.

§                    х*. Цепочка символов х в цикле может повторяться нуль и более раз.

Обычно в алгоритмических языках a это действие реализуется циклом с предварительной проверкой условия.

Например: intl iden (‘,’ iden)* ‘;’

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

·                    х+. Цепочка символов х должна повторяться один и больше раз. В алгоритмическом языке Pascal это реализуется оператором repeat, а в языке Си – оператором цикла do while.

·                    |х|. Определение длины цепочки символов х (количество символов в цепочке).

·                    {} или l, или e - обозначение пустой цепочки символов.

·                    [х]. Так обозначается необязательная цепочка символов. Например, такая запись нужна для того, чтобы обозначить, что перед числом знак может быть, а может и отсутствовать.

Кроме алфавита и цепочки символов (слов), важным понятием является язык.

Язык в алфавите I – это произвольное множество цепочек (слов).

 

2. 2 Регулярные выражения

 

 Это цепочки символов, в которые входят не только символы из некоторого алфавита I, но и другие символы, которые часто носят служебный характер. Например, это могут быть запятая для разделения других символов, а также символы для обозначения каких-либо действий над цепочками. Пусть множество {,* |} из перечисленных в фигурных скобках символов не входит в алфавит I. Тогда цепочка символов из объединения  IU{,* |} называется регулярным выражением. Эти выражения обычно используются для описания синтаксиса какого-либо алгоритмического языка.

2. 3 Грамматика

 

Грамматика G=(T,N,P,S),

где  T - алфавит т.н. терминальных символов. Это символы, которые заведомо определены. Например, это символы, используемые в каком-либо алгоритмическом языке. Какие это символы и какое их качество – все это заведомо определено. Только эти символы в дальнейшем используются при написании программ на этом алгоритмическом языке.

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

Множества T и N не пересекаются. Обычно терминальные символы обозначаются строчными буквами, а нетерминальные – заглавными. Р – множество правил вывода для нетерминальных символов. Например, это правила описания переменных, констант, написания выражений, операторов и т.д. S – стартовый (главный) нетерминальный символ. Для алгоритмических языков это обычно нетерминальный символ “программа”.

2. 4 Способы получения одних цепочек символов из других

 

1 Это можно сделать непосредственно, т.е. за одну операцию. Условное обозначение Þ.

Например, dÞh означает, что цепочку символов h можно получить из цепочки d за одну операцию.

Пример. Есть цепочки d=aAb и h=anb. Здесь, a,n,b - терминальные символы (обозначены строчными буквами), а А – нетерминальный символ. Пусть среди множества правил Р есть такое: A®nЄР. То есть нетерминальный символ АЄN можно заменить  на терминальный n. Таким образом, за одну операцию из d можно получить цепочку h.

2 Одну цепочку из другой можно получить не за одну операцию. Условное обозначение Þ*.

Например, a0 Þ*an.

Это имеет место или если a0 = an , или существует последовательность непосредственно получаемых цепочек, таких, что   a0 Þ a1 Þ a2 Þ …Þ

Þ an-1 Þ an.

2. 5 Формальное определение языка

 

Способы получения цепочек символов необходимы, чтобы формально дать определение языка L(G), описываемого заданной грамматикой G. Язык L(G) – это множество цепочек w терминальных (и только терминальных!) символов, выводимых из начального (стартового, главного) нетерминального символа SL(G)={w|S Þ*w, где w – терминальные цепочки}.

Вертикальная черта после w в выражении означает, что w получены при условии, что они выводятся из S. А звездочка означает, что этот вывод может происходить за произвольное количество операций. При этом используется множество P правил, описанное в грамматике G.

Ниже приводятся примеры грамматики и описываемые ими языки.

Пример 1   G=(T,N,P,S).

T={x,y,w,z} – алфавит терминальных символов. Только эти символы можно использовать.

N={S,A,B} – множество нетерминальных символов, из которых S – главный (стартовый) нетерминальный символ. Именно с него должен начинаться вывод цепочек (слов) в соответствии с множеством правил вывода P.

Р={S®AB, A®x, A®y, B®w, B®z}.

 

Эти правила означают, что S можно заменить на последовательность нетерминальных символов AB. A®x, A® y означает, что А можно заменить на x или на y и т.д. Осуществляя эти замены, получаем цепочки w из терминальных символов, составляющих формальный язык L(G).

L(G)={xw, yw, xz, yz}.

Только эти четыре цепочки (слова) и составляют язык, описываемый заданной грамматикой G.

 

2. 6 Расширенные грамматики

 

Существуют т.н. расширенные грамматики. Они порождают те же языки, что и рассмотренные выше грамматики, но являются более наглядными.

Расширенные грамматики задаются парами

Ai ® ri,

где Ai ЄNi-й нетерминальный символ.

ri – i-е регулярное выражение в алфавите NUT.

Нетерминальный символ первой пары является ГЛАВНЫМ (стартовым)для вывода цепочек.

Например, расширенная грамматика, эквивалентная описанной в примере выше, имеет вид:

S®AB ,

A®x|y,

B®w|z.

Напомним, что вертикальная черта читается как  “или”. То есть А может быть заменена на x или y, а В – на w или z.

 

2. 7 Задачи анализа

 

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

Например, цепочка [[x]] принадлежит языку L(G2), описанному грамматикой   G2.

 G2=(T2, N2, P2, A), где

 T= {х, +, [, ]},

 N2 ={А,В},

 P2 = {А®х, А®[В], В®А, В®В+А}.

Действительно, заданную цепочку можно получить, применив последовательно по одному из правил вывода, заданному в Р2.

АÞ [В]Þ [А]Þ [[В]]Þ [[А]]Þ [[х]].

Следовательно, цепочка [[х]]  принадлежит формальному языку L(G2).

Различают две стратегии: стратегия анализа сверху вниз и снизу вверх. При анализе сверху вниз для построения вывода заданной цепочки начинают с ГЛАВНОГО нетерминального символа и выбирают правила из заданного множества так, чтобы прийти к заданной цепочке w.

В примере [[х]] в грамматике G2 главных нетерминальных символов А среди заданного множества правил вывода для А есть два: А ® х и А®[В]. Первое из них не дает возможности вывести  [[х]]. Берем А ® [В], то есть А заменяем на [В]. Теперь нужно выбирать из двух правил вывода для В.

В ® А и В ® В+А.

Выбираем В ® А, заменяем в [В] В на А и получаем [А]. Вновь из двух правил вывода для А выбираем А ® [В]. Заменяем в [А] А на [В]. Получаем  [[В]]. Вновь из двух правил для вывода В выбираем В® А и заменяем в  [[В]] В на А. Получим [[А]]. И, наконец, из двух правил вывода для А выбираем А®х. Заменяем в [[А]] А на х и получаем требуемую цепочку [[х]]. Таким образом, доказано, что заданная цепочка действительно принадлежит языку, определяемому грамматикой G2.

При анализе сверху вниз основная проблема в определении необходимого правила V ® ai для построения следующего шага вывода цепочки w, когда в найденной части А Þ* nVb известны левый нетерминальный символ V и n правил вывода V ® a1 , V ®a2, …V ® an с левой частью V. Решение этой проблемы, в частности, возможно с помощью алгоритма лексического <А(1) – анализа, который определяет необходимое правило V ® ai в зависимости от первого, еще не распознанного символа х в цепочке w.

Для многих грамматик LA(1) – анализ. Осуществляется LA(1) – анализ путем создания для нетерминалов процедур анализа. Эти процедуры, как правило, оказываются взаимно рекурсивными и часто неэффективными.

Для многих грамматик  LA(1) – анализ в таком виде не используется. Тогда приходят к расширенным грамматикам или к синтаксическим диаграммам (графикам).

 

2. 8 Синтаксические диаграммы

 

Это ориентированный граф с двумя фиксированными вершинами: входной, из которой дуги только выходят, и выходной, в которую дуги только входят.

 

 

Дуги этого графа могут быть помечены терминальными и нетерминальными символами. В расширенной диаграмме с терминальным Т и нетерминальным N алфавитами каждому нетерминалу А и его правилу вывода А ® a, где a - регулярное выражение в алфавите TUN, отвечает одна синтаксическая диаграмма. При обозначении дуг помеченными терминальными символами условились эти символы писать строчными буквами и заключать в окружность. Нетерминальные символы условились писать заглавными буквами и размещать в прямоугольнике. Регулярное выражение будет обозначаться греческими буквами внутри ромба.

На рисунке 2 показаны примеры изображения дуг, помеченных терминальным символом а, нетерминальным – А и регулярным выражением – a.

 

 

Рисунок 2

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

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

 

2. 9 Введение в компиляцию

 

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

Транслятором называется компьютерная программа, которая осуществляет переход программы на входном языке (например, алгоритмическом) на эквивалентную ей объектную программу. Если входной язык высокого уровня (алгоритмические языки Паскаль, Си и др.), а выходной – машинные коды или АССЕМБЛЕР (т.е. машинно-ориентированный язык), то такой транслятор называется компилятором.

Интерпретатор -  разновидность транслятора, который переводит программу на язык простых промежуточных команд и выполняет их.

Препроцессор – транслятор, осуществляющий перевод с одного языка высокого уровня на другой язык тоже высокого уровня.

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

 

2. 10 Структура компилятора

 

 

 

 

 

 

 

 

Здесь:

ЛА – лексический анализ;

СА – синтаксический анализ;

ГПК – генерация промежуточного кода;

ОК – оптимизация кода;

ГК – генерация кода.

На всех этапах осуществляется обработка ошибок и происходит заполнение различных таблиц. Рассмотрим более подробно некоторые этапы обработки исходной программы на алгоритмическом языке.

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

·           служебные слова;

·           идентификаторы;

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

·           числа;

·           признак конца считываемого файла.

Служебные (зарезервированные) слова нельзя использовать в программе на алгоритмическом языке в качестве идентификаторов для обозначения переменных и функций. Например, для языка Си это  if, do, while, for, return, goto, char, int, float и др. Поэтому программа-транслятор должна “уметь” отличить эти зарезервированные служебные слова. На следующем этапе происходит построение из лексем синтаксических структур, которые могут быть составляющими других. На всех этапах осуществляются обнаружение ошибок в тексте транслируемой программы, а также заполнение таблиц. Конкретно заполняются таблица идентификаторов переменных и функций, таблица объектов, которые обрабатываются (константы, глобальные и локальные переменные), таблица функций (главная функция main и др.), таблица команд.

 

2. 11 Проходы компилятора

 

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

 

 

5