- •Предисловие
- •Глава 1 введение в проблематику конструирования компиляторов
- •1.1. Понятие компилятора и его структура
- •1.2. Применение компиляторов и задачи их разработки
- •Глава 2 способы задания формальных языков
- •2.1. Математический аппарат теории
- •Формальных языков, перевода и компиляции
- •1) AR*a для всех aÎa;
- •2.2 Цепочки и языки
- •2.3 Грамматики
- •2.4. Распознаватели
- •2.5 Регулярные выражения и синтаксические диаграммы
- •2.6. Автоматы с магазинной памятью (мп - автоматы )
- •2.7. Соответствия между способами описания языков
- •Глава 3 основы теории перевода
- •3.1. Определение перевода
- •3.2. Модели простейших трансляторов
- •3.2.1. Конечные преобразователи
- •3.2.2. Преобразователи с магазинной памятью
- •Глава 4 конструирование сканеров
- •4.1. Общая характеристика процесса сканирования
- •4.2. Описание лексем в языке расширенных регулярных выражений
- •4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению
- •4.4. Преобразование недетерминированного конечного автомата в детерминированный
- •Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
- •4.5. Преобразование синтаксической диаграммы в конечный автомат
- •4.6. Представление результатов сканирования
- •4.7. Методики конструирования сканеров
- •Глава 5 конструирование однопроходных нисходящих анализаторов
- •5.1. Определение синтаксического разбора
- •5.2. Нисходящий и восходящий разборы
- •5.3. Ll(k) - грамматики
- •5.4. Предсказывающие алгоритмы разбора
- •5.5. Алгоритмы построения управляющих таблиц для левых анализаторов
- •5.6. Приведение грамматик к ll - форме
- •Глава 6 основы генерации кода
- •6.1. Перевод и генерация кода
- •6.2. Представления промежуточной программы
- •6.3. Преобразование промежуточной программы в ассемблерный код
4.7. Методики конструирования сканеров
Подводя итог содержанию этой главы, сформулируем методики конструирования сканера.
Методика 1. Эта методика состоит из пяти этапов, на каждом из которых решается одна из задач построения сканера:
1) описание лексем языка при помощи регулярных выражений;
2) преобразование полученных выражений в соответствующие НКА;
3) преобразование НКА в КА для тех лексем, где такое преобразование необходимо (для некоторых лексем соответствующие КА могут быть получены в результате выполнения 2-го этапа);
4) конструирование сканера из полученных КА, работающих последовательно - в случае прямого лексического анализа, или параллельно (по мере вызова) - в случае непрямого лексического анализа;
5) разработка таблицы имен (и других связанных с ней таблиц) и методов работы с таблицами.
Каждый из этих этапов рассмотрен в соответствующем разделе данной главы.
Методика 2. Если некоторые лексемы проще описать синтаксическими диаграммами, то можно воспользоваться соответствием, имеющим место между диаграммой, регулярной грамматикой и КА, о котором шла речь в гл.2. В этом случае первые три этапа методики 1 можно заменить следующими этапами:
1) описание лексем при помощи синтаксических диаграмм (диаграммы должны содержать только терминальные символы);
2) разметка диаграмм нетерминальными символами и получение соответствующих регулярных грамматик (см. п.4.6);
3) преобразование полученных грамматик в соответствующие КА.
Далее следует выполнить этапы 4 и 5 методики 1. Вообще говоря, применение методики2 не гарантирует получение детерминированного КА для любой лексемы.
Для этого необходимо, чтобы соответствующая грамматика удовлетворяла двум ограничениям, суть которых мы рассмотрим в следующей главе.
Глава 5 конструирование однопроходных нисходящих анализаторов
5.1. Определение синтаксического разбора
В предыдущих разделах мы уже неоднократно сталкивались с понятием синтаксического анализа при изучении распознавателей и сканеров. До сих пор под этим понятием подразумевался процесс анализа символьных цепочек с целью распознавания “правильных” или “неправильных” языковых конструкций. При этом не требовалось выдачи информации о структуре самой конструкции. Основная же функция анализатора в фазе синтаксического анализа состоит в получении и представлении этой информации в виде дерева разбора или другой структуры. Эта структура называется промежуточной программой и используется для генерации кода.
Синтаксический анализ, в ходе которого уясняется структура анализируемой цепочки лексем, называется синтаксическим разбором. Выделяют два вида разбора. Введем их формальное определение.
Определение. Пусть G=(N,S,P,S) - КС-грамматика, правила которой пронумерованы 1,2, ...,р, aÎ(NUS)*. Тогда
левым разбором цепочки a называется последовательность правил, примененных при левом выводе цепочки a из S;
правым разбором цепочки a называется обращение последовательности правил, примененных при правом выводе цепочки a из S.¨
Эти разборы можно представить в виде последовательности номеров из множества {1, 2, . . . , р}.
Пример 5.1. Рассмотрим грамматику с такой нумерацией правил:
(1) E ® E+T,
(2) E ® T,
(3) T ® T*F,
(4) T ® F,
(5) F ® (E),
(6) F ® a,
а так же цепочку a*(a+a) и ее левый и правый разборы. Имеем:
левый вывод: Е2 Þ Т3 Þ Т*F4 Þ F*F6Þa*F5 Þ a*(E)1 Þ a*(E+T)2Þ a*(T+T)4Þ a*(F+T)6 Þa*(a+T)4Þa*(a+F)6 Þ a*(a+a) ;
левый разбор: 23465124646;
правый вывод: Е Þ 2Т Þ 3Т*F Þ 5 T*(E) Þ 1 T*(E+T) Þ 4 T*(E+F) Þ6 T*(E+a) Þ 2 T*(T+a) Þ 4 T*(F+a) Þ 6 T*(a+a) Þ 4 F*(a+a) Þ 6 a*(a+a);
правый разбор: 64642641532.
Понятию разбора можно дать и графическую интерпретацию: говорят, что для некоторой КС-грамматики G цепочка w Î L(G) разобрана, или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно “физически” построить в памяти машины.