В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов, страница 4

Bk αk , где k > 0, Bi ⇒+ eдля 1 6 i 6 k, и ни из одной цепочки αj (0 6 j 6 k) не выводится e, товключить в P 0 все правила (кроме A → e) видаA → α0 X1 α1 ... Xk αkгде Xi – это либо Bi , либо e.2. Если S ⇒+ e, то включить в P 0 правила S 0 → S, S 0 → e и положить0N = N ∪ {S 0 }.

В противном случае положить N 0 = N и S 0 = S.Легко видеть, что G0 – неукорачивающая грамматика. Можно показать по индукции, что L(G0 ) = L(G).Пусть Ki – класс всех языков типа i. Доказано, что справедливо следующее (строгое) включение: K3 ⊂ K2 ⊂ K1 ⊂ K0 .Заметим, что если язык порождается некоторой грамматикой, это неозначает, что он не может быть порожден грамматикой с более сильными ограничениями на правила. Приводимый ниже пример иллюстрирует этот факт.20ГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕПример 2.8. Рассмотрим грамматику G = ({S, A, B}, {0, 1}, {S → AB,A → 0A, A → 0, B → 1B, B → 1}, S). Эта грамматика является контекстносвободной. Легко показать, что L(G) = {0n 1m |n, m > 0}.

Однако, в примере 2.7приведена праволинейная грамматика, порождающая тот же язык.Покажем что существует алгоритм, позволяющий для произвольного КЗ-языка L в алфавите T , и произвольной цепочки w ∈ T ∗ определить, принадлежит ли w языку L.Теорема 2.2. Каждый контекстно-зависимый язык является рекурсивным языком.Доказательство. Пусть L – контекстно-зависимый язык. Тогда существует некоторая неукорачивающая грамматика G = (N, T, P, S), порождающая L.Пусть w ∈ T ∗ и |w| = n.

Если n = 0, т.е. w = e, то принадлежностьw ∈ L проверяется тривиальным образом. Так что будем предполагать,что n > 0.Определим множество Tm как множество строк u ∈ (N ∪ T )+ длиныне более n таких, что вывод S ⇒∗ u имеет не более m шагов. Ясно, чтоT0 = {S}.Легко показать, что Tm можно получить из Tm−1 просматривая, какие строки с длиной, меньшей или равной n можно вывести из строк изTm−1 применением одного правила, т.е.Tm = Tm−1 ∪ {u | v ⇒ u для некоторого v ∈ Tm−1 , где |u| 6 n}.Если S ⇒∗ u и |u| 6 n, то u ∈ Tm для некоторого m. Если из S невыводится u или |u| > n, то u не принадлежит Tm ни для какого m.Очевидно, что Tm ⊇ Tm−1 для всех m > 1. Поскольку Tm зависит только от Tm−1 , если Tm = Tm−1 , то Tm = Tm+1 = Tm+2 = ...

. Процедура будетвычислять T1 , T2 , T3 , . . . пока для некоторого m не окажется Tm = Tm−1 .Если w не принадлежит Tm , то не принадлежит и L(G), поскольку дляj > m выполнено Tj = Tm . Если w ∈ Tm , то S ⇒∗ w.Покажем, что существует такое m, что Tm = Tm−1 .

Поскольку длякаждого i > 1 справедливо Ti ⊇ Ti−1 , то если Ti 6= Ti−1 , то число элементов в Ti по крайней мере на 1 больше, чем в Ti−1 . Пусть|N ∪ T | = k. Тогда число строк в (N ∪ T )+ длины меньшей или равнойn равно k + k 2 + ... + k n 6 nk n . Только эти строки могут быть в любомTi .

Значит, Tm = Tm−1 для некоторого m 6 nk n . Таким образом, процедура, вычисляющая Ti для всех i > 1 до тех пор, пока не будут найденыдва равных множества, гарантированно заканчивается, значит, это алгоритм.Глава 3Лексический анализОсновная задача лексического анализа – разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этойточки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторыхслучаях между лексемами может и не быть разделителей.

С другой стороны, в некоторых языках лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться (“\” в конце строкивнутри "...").Обычно все лексемы делятся на классы. Примерами таких классовявляются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки.

Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители).Как правило, ключевые слова – это некоторое конечное подмножествоидентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексическийанализ в отрыве от синтаксического.С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.).Таким образом, общая схема работы лексического анализатора такова.

Сначала выделяется отдельная лексема (возможно, используя символыразделители). Ключевые слова распознаются либо явным выделениемнепосредственно из текста, либо сначала выделяется идентификатор, азатем делается проверка на принадлежность его множеству ключевых21ГЛАВА 3. ЛЕКСИЧЕСКИЙ АНАЛИЗ22слов.Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как результат лексического анализа.

Есливыделенная лексема является ключевым словом, то выдается признаксоответствующего ключевого слова. Если выделенная лексема является идентификатором – выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексемапринадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно.Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу “дай лексему”.В первом случае (рис.

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

С точки зрения обработки значений лексем, анализатор может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы,либо он может самостоятельно строить таблицы объектов. В этом случаев качестве значения лексемы выдается указатель на вход в соответствующую таблицу.LbiAgZq_gb_KbglZgZebaZlhjLbie_dk_fuLZ[ebpZZAgZq_gb_E_dkZgZebaZlhj[Рис.

3.1:Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либоправолинейная грамматика. Все три формализма (конечных автоматов,3.1. РЕГУЛЯРНЫЕ МНОЖЕСТВА И ВЫРАЖЕНИЯ23регулярных выражений и праволинейных грамматик) имеют одинаковую выразительную мощность. В частности, по регулярному выражению или праволинейной грамматике можно сконструировать конечныйавтомат, распознающий тот же язык.3.1Регулярные множества и выраженияВведем понятие регулярного множества, играющего важную роль в теории формальных языков.Регулярное множество в алфавите T определяется рекурсивно следующим образом:(1) ∅ (пустое множество) – регулярное множество в алфавите T ;(2) {e} – регулярное множество в алфавите T (e – пустая цепочка);(3) {a} – регулярное множество в алфавите T для каждого a ∈ T ;(4) если P и Q – регулярные множества в алфавите T , то регулярнымиявляются и множества(а) P ∪ Q (объединение),(б) P Q (конкатенация, т.е.

множество {pq|p ∈ P, q ∈ Q}),∞S(в) P ∗ (итерация: P ∗ =P n );n=0(5) ничто другое не является регулярным множеством в алфавите T .Итак, множество в алфавите T регулярно тогда и только тогда, когда оно либо ∅, либо {e}, либо {a} для некоторого a ∈ T , либо его можно получить из этих множеств применением конечного числа операцийобъединения, конкатенации и итерации.Приведенное выше определение регулярного множества позволяетввести следующую удобную форму его записи, называемую регулярнымвыражением.Регулярное выражение в алфавите T и обозначаемое им регулярноемножество в алфавите T определяются рекурсивно следующим образом:(1) ∅ – регулярное выражение, обозначающее множество ∅;(2) e – регулярное выражение, обозначающее множество {e};(3) a – регулярное выражение, обозначающее множество {a};(4) если p и q – регулярные выражения, обозначающие регулярныемножества P и Q соответственно, то(а) (p|q) – регулярное выражение, обозначающее регулярноемножество P ∪ Q,24ГЛАВА 3.

ЛЕКСИЧЕСКИЙ АНАЛИЗ(б) (pq) – регулярное выражение, обозначающее регулярное множество P Q,(в) (p∗ ) – регулярное выражение, обозначающее регулярное множество P ∗ ;(5) ничто другое не является регулярным выражением в алфавите T .Мы будем опускать лишние скобки в регулярных выражениях, договорившись о том, что операция итерации имеет наивысший приоритет, затем идет операции конкатенации, наконец, операция объединения имеет наименьший приоритет.Кроме того, мы будем пользоваться записью p+ для обозначения pp∗ .Таким образом, запись (a|((ba)(a∗ ))) эквивалентна a|ba+ .Наконец, мы будем использовать запись L(r) для регулярного множества, обозначаемого регулярным выражением r.Пример 3.1.