В.А. Серебряков, М.П. Галочкин - Основы конструирования компиляторов (1131395), страница 3
Текст из файла (страница 3)
Нумеруемупорядоченные пары целых положительных чисел – (1,1), (2,1), (1,2),(3,1), (2,2), ... . При нумерации пары (i, j) генерируем i-ю цепочку изV ∗ и применяем к цепочке первые j шагов процедуры P. Как только мыопределили, что сгенерированная цепочка принадлежит L, добавляемцепочку к списку элементов L. Если цепочка i принадлежит L, это будет определено P за j шагов для некоторого конечного j. При перечислении (i, j) будет сгенерирована цепочку с номером i.
Легко видеть, чтоэта процедура перечисляет все цепочки L.Если мы имеем процедуру генерации цепочек языка, то мы всегдаможем построить процедуру распознавания предложений языка, но невсегда алгоритм. Для определения того, принадлежит ли x языку L, просто нумеруем предложения L и сравниваем x с каждым предложением. Если сгенерировано x, процедура останавливается, распознав, что xпринадлежит L. Конечно, если x не принадлежит L, процедура никогдане закончится.Язык, предложения которого могут быть сгенерированы процедурой,называется рекурсивно перечислимым.
Язык рекурсивно перечислим,если имеется процедура, распознающая предложения языка. Говорят,2.3. ГРАММАТИКИ17что язык рекурсивен, если существует алгоритм для распознавания языка. Класс рекурсивных языков является собственным подмножествомкласса рекурсивно перечислимых языков. Мало того, существуют языки, не являющиеся даже рекурсивно перечислимыми.2.32.3.1ГрамматикиФормальное определение грамматикиДля нас наибольший интерес представляет одна из систем генерацииязыков – грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков.
Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примеромможет служить способ описания синтаксиса языков программированияпри помощи БНФ – формы Бэкуса-Наура.Определение. Грамматика – это четверка G = (N, T, P, S), где(1) N – алфавит нетерминальных символов;(2) T – алфавит терминальных символов, N ∩ T = ∅;(3) P – конечное множество правил вида α → β, где α ∈ (N ∪ T )+ ,β ∈ (N ∪ T )∗ ;(4) S ∈ N – начальный символ (или аксиома) грамматики.Мы будем использовать большие латинские буквы для обозначениянетерминальных символов, малые латинские буквы из начала алфавита для обозначения терминальных символов, малые латинские буквыиз конца алфавита для обозначения цепочек из T ∗ и, наконец, малыегреческие буквы для обозначения цепочек из (N ∪ T )∗ .Будем использовать также сокращенную запись A → α1 |α2 | ...
|αn дляобозначения группы правил A → α1 , A → α2 , ... , A → αn .Определим на множестве (N ∪T )∗ бинарное отношение выводимости⇒ следующим образом: если δ → γ ∈ P , то αδβ ⇒ αγβ для всех α, β ∈(N ∪ T )∗ . Если α1 ⇒ α2 , то говорят, что цепочка α2 непосредственновыводима из α1 .Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения ⇒, а также его степень k > 0 (обозначаемые соответственно ⇒∗ , ⇒+ и ⇒k ). Если α1 ⇒∗ α2 (α1 ⇒+ α2 , α1 ⇒k α2 ),то говорят, что цепочка α2 выводима (нетривиально выводима, выводима за k шагов) из α1 .Если α ⇒k β (k > 0), то существует последовательность шаговγ0 ⇒ γ1 ⇒ γ2 ⇒ ... ⇒ γk−1 ⇒ γkГЛАВА 2. ЯЗЫКИ И ИХ ПРЕДСТАВЛЕНИЕ18где α = γ0 и β = γk .
Последовательность цепочек γ0 , γ1 , γ2 , ... , γk в этомслучае называют выводом β из α.Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа.Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е.L(G) = {w|w ∈ T ∗ , S ⇒+ w}Грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык, т.е. L(G1 ) = L(G2 ).Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), гдеP = {S → aSBC, S → aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc},порождает язык L(G) = {an bn cn |n > 0}.Действительно, применяем n − 1 раз правило 1 и получаем an−1 S(BC)n−1 ,затем один раз правило 2 и получаем an (BC)n , затем n(n − 1)/2 раз правило 3 иполучаем an B n C n .Затем используем правило 4 и получаем an bB n−1 C n . Затем применяем n − 1раз правило 5 и получаем an bn C n .
Затем применяем правило 6 и n − 1 раз правило 7 и получаем an bn cn . Можно показать, что язык L(G) состоит из цепочектолько такого вида.Пример 2.6. Рассмотрим грамматику G = ({S}, {0, 1}, {S → 0S1, S → 01}, S).Легко видеть, что цепочка 000111 ∈ L(G), так как существует выводS ⇒ 0S1 ⇒ 00S11 ⇒ 000111Нетрудно показать, что грамматика порождает язык L(G) = {0n 1n |n > 0}.Пример 2.7. Рассмотрим грамматику G = ({S, A}, {0, 1}, {S → 0S,S → 0A, A → 1A, A → 1}, S). Нетрудно показать, что грамматика порождаетязык L(G) = {0n 1m |n, m > 0}.2.3.2Типы грамматик и их свойстваРассмотрим классификацию грамматик (предложенную Н.Хомским),основанную на виде их правил.Определение. Пусть дана грамматика G = (N, T, P, S). Тогда(1) если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений.(2) еслиа) каждое правило грамматики, кроме S → e, имеет вид α → β,где |α| 6 |β|, и2.3.
ГРАММАТИКИ19б) в том случае, когда S → e ∈ P , символ S не встречается в правых частях правил,то грамматику называют грамматикой типа 1, или неукорачивающей.(3) если каждое правило грамматики имеет вид A → β, где A ∈ N ,β ∈ (N ∪T )∗ , то ее называют грамматикой типа 2, или контекстносвободной (КС-грамматикой).(4) если каждое правило грамматики имеет вид либо A → xB, либоA → x, где A, B ∈ N , x ∈ T ∗ то ее называют грамматикой типа 3,или праволинейной.Легко видеть, что грамматика в примере 2.5 – неукорачивающая, впримере 2.6 – контекстно-свободная, в примере 2.7 – праволинейная.Язык, порождаемый грамматикой типа i, называют языком типа i.Язык типа 0 называют также языком без ограничений, язык типа 1 –контекстно-зависимым (КЗ), язык типа 2 – контекстно-свободным (КС),язык типа 3 – праволинейным.Теорема 2.1. Каждый контекстно-свободный язык может быть порожден неукорачивающей грамматикой.Доказательство.
Пусть L – контекстно-свободный язык. Тогда существует контекстно-свободная грамматика G = (N, T, P, S), порождающая L.Построим новую грамматику G0 = (N 0 , T, P 0 , S 0 ) следующим образом:1. Если в P есть правило вида A → α0 B1 α1 ... 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) смысл лексемы может зависеть от ее контекста и невозможно провести лексическийанализ в отрыве от синтаксического.С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.).Таким образом, общая схема работы лексического анализатора такова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
