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) и ее левый и правый разборы. Имеем:

левый вывод: Е₂ Þ Т₃ Þ Т*F₄ Þ F*F₆Þa*F₅ Þ a*(E)₁ Þ a*(E+T)₂Þ a*(T+T)₄Þ a*(F+T)₆ Þa*(a+T)₄Þa*(a+F)₆ Þ a*(a+a) ;

левый разбор: 23465124646;

правый вывод: Е Þ ₂Т Þ ₃Т*F Þ ₅ T*(E) Þ ₁ T*(E+T) Þ ₄ T*(E+F) Þ₆ T*(E+a) Þ ₂ T*(T+a) Þ ₄ T*(F+a) Þ ₆ T*(a+a) Þ ₄ F*(a+a) Þ ₆ a*(a+a);

правый разбор: 64642641532.

Понятию разбора можно дать и графическую интерпретацию: говорят, что для некоторой КС-грамматики G цепочка w Î L(G) разобрана, или проанализирована, если известно одно (или, быть может, все) из ее деревьев выводов. При трансляции такое дерево можно “физически” построить в памяти машины.