А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 74

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 74)

Хасс не сообщает о конфликтах "перенос!свертка*', разрешенных с использованием механизма приоритета и ассоциативности. Используемый "терминал" может быть искусственно введенным, как, например, ()М1Н()Я в рассматриваемом калькуляторе. Такой терминал не возвращается лексическим анализатором и объявляется исключительно для того, чтобы определить приоритет продукции.

Объявление на рис. 4.2 Ъгтд)зГ 0М1Н()Я назначает токену ()М1Ы()Я наивысший приоритет, больший, чем у операторов * и /. При описании правил трансляции дескриптор боргес ()М1Н1)Я в конце продукции ехрг . "' -' ехрг делает унарный минус, определяемый этой продукцией, оператором, имеюгцнм наивысший по сравнению с остальными операторами приоритет. 4.9.3 Создание лексического анализатора в Тасс е помощью Хех Бех предназначен для создания лексических анализаторов, которые могут использоваться в Хасс.

Библиотека Ьех 11 предоставляет подпрограмму-драйвер с именем уу1ех( ), которое Хасс использует при вызове лексического аначизатора. При использовании 1ех в качестве генератора лексического анализатора функция уу1ех ( ) в третьей части спецификации Хасс заменяется инструкцией ()1пс1цс(е "1ех.уу.с" 372 Глава 4. Синтаксический анализ и каждый вызов лексического анализатора возвращает известный Хасс терминал.

Указанная инструкция обеспечивает функции уу1ех( ) доступ к именам, используемым Хасс для токенов, поскольку выходной файл Еех компилируется как составная часть выходного файла Хасс у. саЬ. с. В [П([Х, если спецификации Еех находятся в файле йтгзс. 1, а спецификации Хасс — в файле зесопс). у, транслятор может быть скомпилирован последовательностью команд 1ех йтгзг.1 уасс весопс).у сс у.саЬ.с -1у -11 Приведенная на рнс. 4,60 спецификация Еех может использоваться для получения лексического анализатора вместо используемого на рис.

4.2. Последний шаблон спецификации, означающий "любой символ", должен быть записан как ~п ) ., поскольку в Еех точка означает любой символ, кроме символа новой строки. пиатЬег [0-9)+~е. 7 ( [0-9) *~е. [0-9)+ ЪЪ ) /* в)сср Ь1ап)сз */ (пшпЬег) ( ввсапГ(уусехГ, "в1й", Ьуу1тга1)г гегцгп Н()ИВЕВ( ( гегцгп уугехс[0); 'тп) Рис. 4.60. Спецификация ьех лля уу1ех( ) из рис. 4.2 4.9.4 Восстановление после ошибок в Тасс В Хасс восстановление после ошибок может быть выполнено с использованием специальных продукций для ошибок.

Вначале следует решить, какие "крупные" нетерминалы будут иметь связанные с ними продукции ошибок. Типичным выбором является некоторое подмножество нетерминалов, порождающих выражения, инструкции, блоки и процедуры. Затем пользователь добавляет к грамматике продукции ошибок в виде А -+ еггог а, где А — "крупный" нетерминал, а а— строка символов грамматики, возможно, пустая; еггог является в Хасс зарезервированным словом. Хасс генерирует синтаксический анализатор с использованием таких спецификаций, рассматривая продукцию ошибки как обычную. Однако когда синтаксический анализатор, сгенерированный Хасс, сталкивается с ошибкой, он рассматривает состояния, множества пунктов которых содержат 373 4.9, Генераторы синтаксических анализаторов продукции ошибок, особым образом.

При обнаружении ошибки Хасс снимает символы со стека до тех пор, пока на вершине стека не окажется состояние, множество пунктов которого включает пункт вида А — еггог а. Г!осле этого синтаксический анализатор выполняет "перенос" фиктивного токена еггог в стек, как если бы такой токен присутствовал во входном потоке. Если а представляет собой е, немедленно производится свертка в А и выполняется семантическое действие, связанное с продукцией А — еггог (которое может представлять собой пользовательскую программу восстановления после ошибки). После этого синтаксический анализатор отбрасывает входные символы, пока не будет найден символ, позволяющий продолжить нормальный анализ. Если а — не пустая строка, то Уасс пропускает символы входного потока в поисках подстроки, которая может быть свернута в м.

Если о полностью состоит из терминалов, Тасс ищет соответствующую строку во входном потоке и "сворачивает" ее, перенося в стек. В этот момент на вершине стека синтаксического анализатора находится еггог и. После этого синтаксический анализатор сворачивает еггог а в А и продолжает нормальный анализ. Например, продукция ошибки зтгр — еггог говорит синтаксическому анализатору о том, что он должен пропустить весь входной поток до точки с запятой н считать, что был найден нетерминал злнп Семантической подпрограмме для такой ошибки не нужно работать с входным потоком, но она может, например, вывести диагностическое сообщение и выставить флаг, запрещающий генерацию объектного кода.

Пример 4.53. На рис. 4.61 показана спецификация калькулятора с продукцией ошибки 1зпев : еггог '~п' Эта продукция заставляет калькулятор приостановить нормальную работу при обнаружении ошибки во входной строке. Обнаружив ошибку, синтаксический анализатор начинает снимать символы со стека, пока не встретит состояние, имеющее перенос по токену еггог. Состояние 0 является таковым (и в нашем примере единственным), поскольку его пункты включают Йлея — еггог ' ~п' Состояние 0 всегда находится на дне стека. Синтаксический анализатор переносит еггог в стек и пропускает все символы входного потока, пока не обнаружит символ новой строки.

Синтаксический анализатор переносит его в стек, сворачивает егюг ' ~п' в 11пез и выводит диагностическое сообщение "Повторите ввод 374 Глава 4. Синтаксический анализ Ъ( ()1пс1ис(е <сгуре.Ь> ()1пс1ис(е <вЫТо. Ь> ()с(ей1пе УУБТУРЕ с)оиЬ1е /* Тип с)оиЬ1е для стека Уасс */ Ъ) Ъго)сеп И0МВЕЕ 11пев : 11пев ехрг ' тп' ( рг1пГй(чЪд~п", $2); ) 11пев ' 'тп' /* ешргу */ еггог ' тп' ( ууеггог(чПовторите ввод" последней строки:"); ууегго)ст ) ехрг ЪЪ ()1пс1ис(е ч1ех.уу.с" Рис. 4.61. Калькулятор с восстановлением после ошибок последней строки:". Специальная подпрограмма уасс ууегго)с'з переводит синтаксический анализатор в режим обычной работы.

а 'эВ листинге ууеггох приводится без скобок, указывающих, что это функпня, поскольку реально ууеггои — макроопределение. — Прим. ред. Ъ1ейГ '+' Ъ1егт. ' *' ' /' Ъг1дЬГ ПМ1МПВ ЪЪ ехрг '+' ехрг ехрг '*' ехрг '/' ' (' ехрг 1 ' -' ехрг 1 НПМВЕЕ ехрг ехрг ехрг ехрг 1 ) Ъргес ( $3 $Э ( бб ( бб ( бб ПМ1НПЯ б1 + бз; ) $1 — $3; ) б1 * $3; ) б1 / бз; ) $2; бб = - бг; ) 375 4.!О. Резюме к главе 4 4.9.5 Упражнения к разделу 4.9 ! Упражнение 4.9.1. Напишите уасс-программу, которая получает в качестве входа булево выражение (см. грамматику из упражнения 4.2.2, ж) н выводит его значение. ! Упражнение 4.9.2.

Напишите з'асс-программу, которая получает списки (см. грамматику из упражнения 4.2.2, д, но с произвольным символом в качестве элемента, а не только а) и выводит линейное представление списка, т.е. единый список элементов в том же порядке, в котором они поступают на вход. ! Упражнение 4.9.3. Напишите Уасс-программу, которая проверяет, является ли ее вход паяиндромом, т.е. последовательностью символов, одинаково читающихся как в прямом, так и в обратном направлении. !! Упражнение 4.9.4.

Напишите Уасс-программу, которая получает регулярное выражение (см. грамматику из упражнения 4.2.2, г, но с любым произвольным символом в качестве аргумента, а не только а) и выводит таблицу переходов для недетерминированного конечного автомата, распознающего этот же язык. 4.10 Резюме к главе 4 + Синтаксические анализаторы. Синтаксический анализатор получает в качестве входных данных токены от лексического анализатора и рассматривает имена токенов как терминальные символы контекстно-свободной грамматики. Затем синтаксический анализатор строит дерево разбора для входной последовательности токенов; дерево разбора может быть построено фигурально (проходом по соответствующим шагам порождения) или буквально.

+ Контекстно-свободные грамматики. Грамматика определяет множество терминальных символов (входных символов), множество нетерминалов (снмволов, представляющих синтаксические конструкции) и множество продукций, каждая из которых указывает способ, которым строки, представленные одним нетерминалом, могут быть построены из терминальных символов и строк, представленных некоторыми другими нетерминалами.

Продукция состоит из заголовка (заменяемого нетерминала) и тела (замешаюшей строки из символов грамматики). + Порождения. Процесс, начинакпцийся со стартового нетерминала грамматики и последовательно замещающий каждый нетерминал телом одной из его продукций, называется порождением. Если всегда замещается крайний слева (справа) нетерминал, то такое порождение называется левым (правым). ЗУб Глава 4.

Синтаксический анализ + Деревья разбора. Дерево разбора представляет собой рисунок порождения, на котором для каждого нетерминала в порождении имеется свой узел. Дочерние узлы представляют собой символы, которыми заменяется в процессе разбора нетерминал родительского узла. Существует взаимно- однозначное соответствие между деревьями разбора и левыми и правыми порождениями одной и той же строки терминалов.

+ Неоднозначность. Грамматика, у которой некоторая строка терминалов имеет два или более различных деревьев разбора (или, что то же самое, два или более левых (или правых) порождения), называется неоднозначной. В большинстве случаев, представляющих практический интерес, неоднозначную грамматику можно преобразовать так, чтобы она стала однозначной для того же языка.

Характеристики

Список файлов книги