Лекции по конструированию компиляторов. В.А. Серебряков (1134688), страница 2
Текст из файла (страница 2)
1.1На этапе ЛА обнаруживаются некоторые (простейшие) ошибки(недопустимые символы, неправильная запись чисел, идентификаторов идр.).Основная задача синтаксического анализа - разбор структурыпрограммы. Как правило, под структурой понимается дерево,соответствующее разбору в контекстно-свободной грамматике языка.
Внастоящее время чаще всего используется либо LL(1)-анализ (и еговариант - рекурсивный спуск), либо LR(1)-анализ и его варианты (LR(0),SLR(1), LALR(1) и другие). Рекурсивный спуск чаще используется приручном программировании синтаксического анализатора, LR(1) - прииспользовании систем автоматизации построения синтаксическиханализаторов.Результатом синтаксического анализа является синтаксическоедерево со ссылками на таблицу имен. В процессе синтаксического анализатакже обнаруживаются ошибки, связанные со структурой программы.На этапе контекстного анализа выявляются зависимости междучастями программы, которые не могут быть описаны контекстносвободным синтаксисом. Это в основном связи "описание-использование",в частности анализ типов объектов, анализ областей видимости,соответствие параметров, метки и другие. В процессе контекстногоанализа строится таблица символов, которую можно рассматривать кактаблицу имен, пополненную информацией об описаниях (свойствах)объектов.Основным формализмом, использующимся при контекстноманализе, являются атрибутные грамматики.
Результатом работы фазыконтекстного анализа является атрибутированное дерево программы.Информация об объектах может быть как рассредоточена в самом дереве,так и сосредоточена в отдельных таблицах символов. В процессеконтекстного анализа также могут быть обнаружены ошибки, связанные снеправильным использованием объектов.Затем программа может быть переведена во внутреннеепредставление. Это делается для целей оптимизации и/или удобствагенерации кода.
Еще одной целью преобразования программы вовнутреннее представление является желание иметь переносимыйкомпилятор. Тогда только последняя фаза (генерация кода) являетсямашинно-зависимой. В качестве внутреннего представления может17использоваться префиксная или постфиксная запись, ориентированныйграф, тройки, четверки и другие.Фаз оптимизации может быть несколько. Оптимизации обычноделят на машинно-зависимые и машинно-независимые, локальные иглобальные. Часть машинно-зависимой оптимизации выполняется на фазегенерации кода. Глобальная оптимизация пытается принять во вниманиеструктуру всей программы, локальная - только небольших ее фрагментов.Глобальная оптимизация основывается на глобальном потоковом анализе,который выполняется на графе программы и представляет по существупреобразование этого графа.
При этом могут учитываться такие свойствапрограммы, как межпроцедурный анализ, межмодульный анализ, анализобластей жизни переменных и т.д.Наконец, генерация кода - последняя фаза трансляции. Результатомее является либо ассемблерный модуль, либо объектный (илизагрузочный) модуль. В процессе генерации кода могут выполнятьсянекоторые локальные оптимизации, такие как распределение регистров,выбор длинных или коротких переходов, учет стоимости команд привыборе конкретной последовательности команд.
Для генерации кодаразработаны различные методы, такие как таблицы решений,сопоставление образцов, включающее динамическое программирование,различные синтаксические методы.Конечно, те или иные фазы транслятора могут либо отсутствоватьсовсем, либо объединяться. В простейшем случае однопроходноготранслятора нет явной фазы генерации промежуточного представления иоптимизации, остальные фазы объединены в одну, причем нет и явнопостроенного синтаксического дерева.18Глава 2. Лексический анализОсновная задача лексического анализа - разбить входной текст, состоящийиз последовательности одиночных символов, на последовательность слов,или лексем, т.е. выделить эти слова из непрерывной последовательностисимволов.
Все символы входной последовательности с этой точки зренияразделяются на символы, принадлежащие каким-либо лексемам, исимволы, разделяющие лексемы (разделители). В некоторых случаяхмежду лексемами может и не быть разделителей. С другой стороны, внекоторых языках лексемы могут содержать незначащие символы (пробелв Фортране). В Си разделительное значение символов-разделителей можетблокироваться ('\' в конце строки внутри "...").Обычно все лексемы делятся на классы. Примерами таких классовявляютсячисла(целые,восьмеричные,шестнадцатиричные,действительные и т.д.), идентификаторы, строки. Отдельно выделяютсяключевые слова и символы пунктуации (иногда их называют символыограничители).
Как правило, ключевые слова - это некоторое конечноеподмножество идентификаторов. В некоторых языках (например, ПЛ/1)смысл лексемы может зависеть от ее контекста и невозможно провестилексический анализ в отрыве от синтаксического.С точки зрения дальнейших фаз анализа лексический анализаторвыдает информацию двух сортов: для синтаксического анализатора,работающего вслед за лексическим, существенна информация опоследовательности классов лексем, ограничителей и ключевых слов, адля контексного анализа, работающего вслед за синтаксическим, важнаинформацияоконкретныхзначенияхотдельныхлексем(идентификаторов, чисел и т.д.).
Поэтому общая схема работылексического анализатора такова. Сначала выделяем отдельную лексему(возможно, используя символы-разделители). Если выделенная лексема ограничитель, то он (точнее, некоторый его признак) выдается какрезультат лексического анализа. Ключевые слова распознаются либоявным выделением непосредственно из текста, либо сначала выделяетсяидентификатор, а затем делается проверка на принадлежность егомножеству ключевых слов.
Если да, то выдается признаксоответствующего ключевого слова, если нет - выдается признакидентификатора, а сам идентификатор сохраняется отдельно. Есливыделенная лексема принадлежит какому-либо из других классов лексем(число, строка и т.д.), то выдается признак класса лексемы, а значение19лексемы сохраняется.Тип, ЗначениеСинт. анализаторТиплексемыТаблицаФайл лексемРис. 2.1ЗначениеЛекс. анализатор“Дай лексему”Рис. 2.2Лексический анализатор может работать или как самостоятельная фазатрансляции, или как подпрограмма, работающая по принципу "дайлексему". В первом случае (рис.
2.1) выходом лексического анализатораявляется файл лексем, во втором (рис. 2.2) лексема выдается при каждомобращении к лексическому анализатору (при этом, как правило, типлексемы возвращается как значение функции "лексический анализатор", азначение передается через глобальную переменную). С точки зренияформирования значений лексем, принадлежащих классам лексем,лексический анализатор может либо просто выдавать значение каждойлексемы и в этом случае построение таблиц переносится на более поздниефазы, либо он может самостоятельно строить таблицы объектов(идентификаторов, строк, чисел и т.д.). В этом случае в качестве значениялексемы выдается указатель на вход в соответствующую таблицу.Работа лексического анализатора описывается формализмомконечных автоматов.
Однако, непосредственное описание конечногоавтомата неудобно практически. Поэтому для описания лексическиханализаторов, как правило, используют либо формализм регулярныхвыражений, либо формализм контекстно свободных грамматик, а именноподкласса автоматных, или регулярных, грамматик. Все три формализма(конечных автоматов, регулярных выражений и автоматных грамматик)имеют одинаковую выразительную мощность.
По описанию лексическогоанализатора в виде регулярного выражения или автоматной грамматикистроится конечный автомат, распознающий соответствующий язык.202.1. Регулярные множества и регулярные выраженияПусть T - конечный алфавит. Регулярное множество в алфавите Tопределяется рекурсивно следующим образом (знаком '<-' будемобозначать принадлежность множеству, знаком '<=' включение):(1) {} (пустое множество) - регулярное множество в алфавите T;(2) {a} - регулярное множество в алфавите T для каждого a<-T;(3) {е} - регулярное множество в алфавите T (e - пустая цепочка);(4) если P и Q - регулярные множества в алфавите T, то таковы же имножества(а) P U Q (объединение),(б) PQ (конкатенация, т.е.
множество pq, p<-P, q<-Q),(в) P* (итерация: P*={e} U P U PP U...;(5) ничто другое не является регулярным множеством в алфавите T.Итак, множество в алфавите T регулярно тогда и только тогда, когда онолибо {}, либо {e}, либо {a} для некоторого a<-T, либо его можно получитьиз этих множеств применением конечного числа операций объединения,конкатенации и итерации.Приведенноевышеопределениерегулярногомножестваодновременно определяет и форму его записи, которую будем называтьрегулярным выражением. Для сокращенного обозначения выражения PP*будем пользоваться записью P+ и там, где это необходимо, будемиспользовать скобки. В этой записи наивысшим приоритетом обладаетоперация *, затем конкатенация и, наконец, операция U, для записикоторой иногда будем использовать значок '|'.
Так, 0|10* означает(0|(1(0*))). Кроме того, мы будем использовать запись видаd1 = r1d2 = r2.......dn = rnгде di - различные имена, а каждое ri - регулярное выражение надсимволами T U {d1,d2,...,di-1}, т.е. символами основного алфавита и ранееопределенными символами. Таким образом, для любого ri можнопостроить регулярное выражение над Т, повторно заменяя именарегулярных выражений на обозначаемые ими регулярные выражения.Пример 2.1. Несколько примеров регулярных выражений и обозначаемыхими множествИдентификатор - это регулярное выражение21Идентификатор = Буква (Буква|Цифра)*Буква = {a,b,...,z}Цифра = {0,1,...,9}Число в десятичной записи - это регулярное выражениеЦелое = Цифра+Дробная_часть = . Целое | еСпепень = ( Е ( + | - | е ) Целое ) | еЧисло = Целое Дробная_часть СтепеньЯсно, что для каждого регулярного множества можно найти по крайнеймере одно регулярное выражение, обозначающее это множество.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
