- •Предисловие
- •Глава 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. Преобразование промежуточной программы в ассемблерный код
5.2. Нисходящий и восходящий разборы
Большинство методов синтаксического анализа делят на два класса разбора, – нисходящего и восходящего. Анализаторы, реализующие методы нисходящего разбора, выдают на выходе левые разборы и называются левыми анализаторами, а реализующие методы восходящего разбора, выдают правые разборы и называются правыми анализаторами. Оказывается, что эти анализаторы можно моделировать при помощи соответствующих МП - преобразователей.
В литературе отмечается, что при сравнении эффективности стратегий нисходящего и восходящего разбора, ни одной из них нельзя отдать окончательного предпочтения. Для приобретения навыков построения анализатора в дальнейшем мы будем рассматривать только нисходящие методы, а восходящие методы рассмотрим только на уровне стратегии. Рассмотрим стратегию нисходящего разбора.
Пусть m = i1 ... in — левый разбор цепочки w Î L(G), где G — КС-грамматика. Зная m можно построить левый вывод и соответствующее дерево вывода цепочки w.
Пример 5.2. Рассмотрим грамматику G с правилами:
(1) Е ® Е + Т,
(2) Е ® Т,
(3) Т ® Т * F,
(4) T ® F,
(5) F ® (E),
(6) F ® a
и цепочку w=a*(a+a). Если m = 23465124646, то дерево вывода имеет вид, показанный на рис.5.1.
С деревом вывода тесно связано дерево разбора. Пока мы не будем делать различий между ними, но дадим соответствующее разъяснение в следующей главе.
Изменим теперь исходные данные. Пусть задана грамматика G=(N,å,P,S) с занумерованными правилами и цепочка w Î L(G). Требуется построить ее левый разбор m, т.е. решить задачу разбора. Можно считать, что нам известны корень и крона дерева. Стратегия нисходящего разбора заключается в попытках построения дерева, начиная с его корня и двигаясь сверху вниз, слева направо, восполняя недостающие вершины, пока не будет достигнута крона дерева. На каждом шаге выбирается только одно правило грамматики (и запоминается его номер), которое приводит к построению очередной внутренней вершины.
Очевидно, что последовательность номеров этих правил, получаемая по завершению процедуры построения дерева, и есть левый разбор цепочки w.
Левый анализатор можно моделировать при помощи МП -преобразователя.
Определение. Пусть G=(N,å ,P,S) – КС-грамматика и ее правила пронумерованы от 1 до р. Определим левый анализатор как недетерминированный МП - преобразователь:
Ml=({q}, S, N È S, {1,2,...,p},d, q, S, Æ),
где d определяется следующим образом:
для всех АÎN d (q, e, A)={(q,a, i) | если А® a - правило с номером i};
для всех аÎS d(q, a, a)={(q, e, e)}. ¨
Пример 5.3. Пусть G-грамматика из примера 5.2 и
Мl=({q}, {a, *, +, (, )}, {E, T, F, a, *, +, (, )}, {1, 2, ..., 6}, d, q, E, Æ),
где d(q, e, E)={(q, E+T, 1), (q, T, 2)};
d(q, e, T)={(q, T*F, 3), (q, F, 4)};
d(q, e, F)={(q,( E), 5), (q, a, 6)};
d(q, b, b)={(q, e, e)} для всех bÎS.
Пусть на входе анализатора цепочка w=a+a*a, и начальная конфигурация анализатора имеет вид (q, a+a*a, E, e).
В результате потактного анализа входной цепочки анализатор проделает траекторию, которая имеет вид дерева, аналогично траектории недетерминированного конечного автомата (см. гл. 2). Мы предлагаем читателю построить эту траекторию самостоятельно. В этой древовидной траектории только один путь приведет к заключительной конфигурации, имеющей вид:
(q, e, e, 12463466).
Легко убедиться, что выходная цепочка m=12463466 - левый разбор входной цепочки w.
Рассмотрим теперь стратегию восходящего разбора. Эта стратегия так же предполагает реконструирование дерева вывода, но восполнение вершин начинается снизу - с кроны дерева, а движение происходит вверх и слева направо — к корню дерева.
При построении очередной вершины запоминается номер применяемого правила грамматики. Получаемая в результате последовательность номеров представляет правый разбор входной цепочки w, соответствующей кроне дерева.
Стратегия восходящего разбора реализуется правым анализатором, моделью которого также служит МП - преобразователь (но здесь он будет расширенным). Мы не будем вводить определение правого анализатора, поскольку в дальнейшем будут рассматриваться только левые анализаторы.