Иванова Г.С., Ничушкина Т.Н. - Основы конструирования компиляторов, страница 3

е. контекста, что также свойственнограмматикам естественных языков;(расширение допускает не более одного правила вида A → e, где A∈VN);тип 2 – контекстно-свободные грамматики:A → β, где A∈VN, β∈ V* – поскольку в левой части правила стоит нетерминал, подстановки не зависят от контекста;тип 3 – регулярная грамматика:A → α, A → αB, где A, В∈VN, α ∈ VT;(расширение допускает не более одного правила вида S → e, но в этом случае аксиома не должна появляться в правых частях правил).Классификация построена по правилам иерархии, т.

е. грамматики типа 3 являютсячастным случаем грамматик типа 2 и т. п. (см. рисунок 3).Грамматики большинства существующих языков про-Тип 0Тип 1Тип 2Тип 3граммирования относятся к типу 2, что связано с рекурсивно-вложенной структурой большинства правил продукцииРисунок 3 – Вложение типовтаких языков.Один и тот же язык может быть описан грамматиками различных типов, поэтомутип языка определяется максимально возможным для него типом грамматики. Так грамматика языка описания целых десятичных чисел, приведенная в примере выше, относитсяк типу 2, хотя этот язык можно описать грамматикой типа 3:<целое>::= + <цбз>| - <цбз>|0<цбз>| 1<цбз>| 2<цбз>| 3<цбз>|4<цбз>|5<цбз>| 6<цбз>| 7<цбз>|8<цбз>| 9<цбз>|0|1|2|3|4|5|6|7|8|9<цбз>::= 0<цбз>| 1<цбз>| 2<цбз>| 3<цбз>|4<цбз>|5<цбз>| 6<цбз>| 7<цбз>|8<цбз>| 9<цбз>|0|1|2|3|4|5|6|7|8|9.Оглавление18Следовательно, язык описания целых десятичных чисел относится к типу 3.Примечание.

Существует простой метод проверки регулярности языка, основанныйна лемме о разрастании, смысл которой заключается в следующем: в строке регулярногоязыка всегда можно найти непустую подстроку, повторение которой произвольное количество раз порождает новые строки того же языка.Пример. Язык описания целых чисел. Из строки «+23» можно построить строки:22222, 23232323 и т. д. того же языка.Еще одно свойство языка позволяет сразу определить, что язык не относится к классу регулярных – это самовложение, т. е. наличие правил вида A ⇒+ α1Aα2, где α1, α2 ∈ V+.Пример.

Язык скобок, описываемый правилами: S → (S), S → SS, S → e. Грамматикаэтого языка является грамматикой с самовложением, принадлежит классу КС и не приводима к регулярной.Лемма о разрастании КС языков формулируется следующим образом: в строке, принадлежащей КС-языку, всегда можно найти две подстроки с ненулевой суммарной длиной, одновременное повторение которых произвольное количество раз порождает новуюстроку того же языка.Пример. Язык скобок. Из строки «()» можно построить строку: ((())) и т.

д. того жеязыка.Проверка соответствия строк языку осуществляется специальной программой – распознавателем. Распознаватели могут использоваться для определения языка также как играмматики. Чем шире класс распознаваемых грамматик, тем сложнее класс соответствующих распознавателей. Доказано, что:- грамматики типа 3 распознаются конечными автоматами;- грамматики типа 2 распознаются автоматами с магазинной памятью;- грамматики типа 1 распознаются линейными ограниченными автоматами;- грамматики типа 0 распознаются машинами Тьюринга.Оглавление19Контрольные вопросы1.

Определите, что такое алфавит языка.Ответ.2. Дайте определение формального языка. Почему формальные языки обычно неопределяют перечислением допустимых предложений?Ответ.3. Дайте определение формальной грамматики.Ответ.4. Что такое «Форма Бэкуса-Наура»? Для чего она используется?Ответ.5. Определите цель грамматического разбора предложений языка.Ответ.6. В чем заключается левосторонний восходящий грамматический разбор? Назовите,в каких случаях он не применим и определите его основной недостаток.Ответ.7. В чем заключается правосторонний нисходящий грамматический разбор? Назовите, в каких случаях он не применим и определите его основной недостаток.Ответ.8. Назовите основные типы грамматик по Хомскому. Какие грамматики используют вязыках программирования?Ответ.Оглавление203Распознавание регулярных грамматик3.1Конечный автомат и его программная реализацияРаспознаватели регулярных грамматик строятся на конечных автоматах. Конечныйавтомат – это математическая модель, свойства и поведение которой полностью определяются пятеркой: M = (Q, Σ, δ, q0, F),где Q – конечное множество состояний;Σ – конечное множество входных символов;δ(qi, сk) – функция переходов (qi – текущее состояние, сk – очередной символ);q0 – начальное состояние;F = {qj} – подмножество допускающих состояний.Конечные автоматы – одна из базовых моделей, используемых при проектированиипрограммного и аппаратного обеспечения средств вычислительной техники.Пример.

Автомат «Чет-нечет» описывается следующим образом:Q = {Чет, Нечет};Σ = {0, 1};δ(Чет, 0) = Чет, δ(Нечет, 0) = Нечет, δ(Чет, 1) = Нечет, δ(Нечет, 1) = Чет;q0 = Чет;F = {Чет}Строка «10110» приведет такой автомат в состояние Нечет, т. е. будет отвергнута, астрока «110011» – в состояние Чет, т. е. будет принята.Для представления функции переходов конечного автомата помимо аналитическойформы могут использоваться: таблица (см. таблицу 4), граф переходов состояний (см. рисунок 4) и синтаксическая диаграмма (см. рисунок 5).Таблица 3 – Функция переходовq00σЧетНечетЧет11Нечет010Чет1НечетНечет ЧетНечетЧет1Чет0Рисунок 4 – Граф переходовРисунок 5 – Синтаксическая диаграммаРазработчик автомата обычно использует представление автомата графом или синтаксической диаграммой.

При реализации в виде программы автомат задают таблицейпереходов.Оглавление21Для идентификации завершения строки обычно применяют специальный символ илимножество символов, которые включают во входной алфавит и учитывают в таблице.Кроме этого, в таблице также предусматривают реакцию автомата на символы, не включенные в алфавит и не являющиеся завершающими. Появление таких символов в строкеоднозначно означает, что предложение языка содержит ошибку (см.

таблицу 5).Таблица 4 – Дополненная таблица конечного автоматаqсЧет0Чет1Не-Символы завершенияКонецДругие символыОшибкаНечетНе-четЧетОшибкаОшибкачетПусть S – строка на входе автомата;Ind – номер очередного символа;q – текущее состояние автомата;Table – таблица, учитывающая символы завершения и другие символы.Тогда алгоритм работы автомата можно представить следующим образом.Ind := 1q := q0Цикл-пока q ≠ «Ошибка» и q ≠ «Конец»q = Table [q, S[Ind]]Ind := Ind +1Все-циклЕсли q = «Конец»то «Строка принята»иначе «Строка отвергнута»Все-еслиОглавление223.2Построение лексических анализаторовПри построении лексических анализаторов конечные автоматы используют для распознавания лексем второго типа (базовых понятий языка). Эти понятия можно описать врамках самых простых, регулярных грамматик и предложить для них эффективную технику разбора. Отделение сканера от синтаксического анализатора позволяет также сократитьвремя распознавания лексем, так как при этом появляется возможность использования оптимизированных ассемблерных команд, специально предназначенных для сканированиястрок.Алфавит автомата лексического анализатора – все множество однобайтовых (ANSI)или двухбайтовых (Unicode) символов.

При записи правил обычно используются обобщающие нетерминалы вида «Буквы», «Цифры». В процессе распознавания может формироваться описываемый объект, например, литерал или идентификатор.Пример. Распознаватель целых чисел. Синтаксическая диаграмма синтаксиса языкаописывается синтаксической диаграммой (см. рисунок 6).1ЦифраЗнак3РазделительК21 – начало разбора; 2 – распознан знак; 3 – целое; К – завершение разбораРисунок 6 – Синтаксическая диаграммаПо диаграмме строим таблицу переходов (см. таблицу 5), обозначая состояниеошибки символом «E». В таблице переходов указываем подпрограммы обработки, которые должны быть выполнены при осуществлении указанного перехода.

При выполненииэтих подпрограмм формируются указанные значения.Таблица 5 – Таблица переходовЗнак Цифра Разделитель Другие1 2, А1 3, А2Е, Д1Е, Д42 Е, Д2 3, А2Е, Д3Е, Д43 К, А3 3, А2К, А3Е, Д4а) Подпрограммы обработки:A0: Инициализация: Целое := 0; Знак_числа := «+».А1: Знак_числа := ЗнакА2: Целое := Целое*10 + ЦифраА3: Если Знак_числа = «-» то Целое := -Целое Все-еслиб) Диагностические сообщения:Оглавление23Д1: «Строка не является десятичным числом»;Д2: «Два знака рядом»;Д3: «В строке отсутствуют цифры»,Д4: «В строке встречаются недопустимые символы»Обозначим: S – строка на входе автомата; Ind – номер очередного символа; q – текущее состояние автомата; Table – таблица, учитывающая символы завершения и другиесимволы.Тогда алгоритм сканера-распознавателя можно представить следующим образом.Ind := 1q := 1Выполнить А0Цикл-пока q ≠ «Е» и q ≠ «К»Если S[Ind] = «+» или S[Ind] = «-»,то j := 1иначе Если S[Ind] ≥ «0» и S[Ind] ≤ «9»,тоj := 2,иначе j := 3Все-еслиВсе-еслиВыполнить Ai := Table [q, j].