КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Int dflag
%}
%%
prog: decls stats
;
decls: /* пусто */
{ dflag=1; }
| определения
;
stats: /* пусто */
{ dflag=0; }
| операторы
;
Флаг dflag равен 0 при чтении операторов и 1 при чтении определений, за исключением первой лексемы первого оператора. Распознаватель должен распознать эту лексему перед тем, как сообщить, что кончился раздел определений и начался раздел операторов. В большинстве случаев это единственное исключение не влияет на процесс лексического анализа. Используя такой подход, можно, конечно и переусердствовать. Тем не менее, это иллюстрирует достижение определенных целей, которые трудно достижимы другими способами.
Обработка ошибок довольно сложное дело, так как большинство ситуаций связано с семантикой. При обнаружении ошибок может понажобиться, например, освободить память для дерева разбора, удалить или изменить строки в таблице символов и, что чаще всего, установить некоторые флаги для подавления генерации выходной информации.
При обнаружении ошибок прекращение обработки обычно неприемлемо. Более полезным является продолжение просмотра для обнаружения возможных ошибок. Это ведет к необходимости повторного запуска распознавателя после ошибки. Существует общий класс алгоритмов для этих действий, который включает в себя отбрасывание из входной строки ряда лексем и попытки изменить состояние распознавателя для продолжения обработки.
Для того, чтобы пользователь мог управлять этим процессом, yacc предоставляет простое, но достаточно универсальное средство. Для обработки ошибок зарезервирована лексема с именем error. Это имя может использоваться в грамматических правилах: им отмечаются места, где может встретиться ошибка и где необходимо провести восстановление. Распознаватель выталкивает состояния из стека до тех пор, пока не найдет состояние, в котором error допустимо. Далее считается что error - очередная лексема, и выполняются соответствующие действия. Затем значение очередной лексемы устанавливается равным лексеме, вызвавшей ошибку. Если никаких других правил не указано, при обнраужении ошибки обработка прекращается.
Для предотвращения потока сообщений об ошибках распознаватель после обнаружения ошибки остается в этом состоянии, пока не будут прочитаны и обработаны три следующие лексемы. Если ошибка обнаружена в момент, когда распознаватель находится в состоянии обработки ошибок, сообщений не выводится и входная лексема удаляется. Рассмотрим в качестве примера правило:
stat: error
Оно означает, что в случае ошибки распознаватель попытается пропустить предложение, в котором она встретилась. Более точно, распознаватель продолжит чтение в поисках трех лексем, которые допустимы после предложения, и начнет обработку первой из них. Если начало предложения недостаточно хорошо различимо, распознаватель может сбиться и начать обработку в его середине. При этом будет выведено сообщение об ошибке, хотя ее на самом деле нет. С правилами обработки ошибок могут быть связаны действия. Они могут выполнять операции по повторной инициализации таблиц, освобождению памяти и пр. Приведенные правила обработки ошибок довольно универсальны, но трудны в управлении.
Несколько легче использовать правила вида:
stat: error';'
При обнаружении ошибки распознаватель попытается пропустить предложение, но будет это делать, пока не встретит символ ';'. Все лексемы после ошибки и вплоть до символа ';' не могут сдвигаться и отбрасываются. При обнаружении этого символа правило свертывается и выполняются соответствующие действия.
Еще один вариант обработки ошибок применяется в интерактивных системах для обеспечения возможности повторного ввода строки в случае ошибки. Правило может выглядеть следующим образом:
input: error'0 {printf("Введите строку:"); }input {$$=$4;}
В этом подходе есть одна потенциальная трудность: распознаватель должен корректно обработать три следующих лексемы перед тем, как восстановить ситуацию после ошибки. Если повторно вводимая строка содержит в двух первых лексемах ошибки, они удаляются без выдачи сообщения, что совершенно неприемлемо. По этой причине существует механизм, заставляющий распознаватель поверить в то, что все последствия ошибки устранены. Оператор yyerrok, употребляемый в действии, переводит распознаватель в нормальное состояние. Перепишем последний пример:
input: error'0 { yyerrok; printf("Введите строку:"); } input {$$=$4;} ;
Как уже было сказано, лексема, прочитанная непосредственно после символа error, считается лексемой, содержащей ошибку. Иногда это неприемлемо, например, действие по обработке ошибок само может определить место возобновления обработки. В этом случае очередная лексема должна очищаться. Этого эффекта можно достичь, применяя в действии оператор yyclearin. Предположим, например, что действие после ошибки заключается в вызове написанной пользователем функции, пытающейся синхронизироваться и установить указатель на начало следующего правильного оператора. После ее вызова следующая возвращаемая yylex лексема будет скорее всего, первой лексемой правильного оператора. Старая неправильная лексема должна быть отброшена, и состояние ошибки должно быть отменено. Этого можно достичь следующими правилами:
stat: error { resynch(); yyerrok; yyclearin; }
Нужно признать, что эти механизмы довольно негибки, но они в действительности позволяют выполнить эффективное восстановление после большинства ошибок. Более того, пользователь может получить управление для обработки ошибок другими участками программы.
Если на вход yacc подать спецификацию, на выходе получается файл с программой на языке С, чаще всего называемый y.tab.c. В нем содержится функция, возвращающая целое, по имени yyparse(). Для получения входных лексем эта функция вызывает функцию лексического анализатора yyerror(). Далее, либо будет обнаружена ошибка и в этом случае (если не задано действий по обработке ошибок) yyparse() вернет 1, либо лексический анализатор вернет конечный маркер и распознаватель завершит обработку возвратом 0. Для получения работающей программы пользователь должен снабдить распознаватель некоторой средой выполнения. Например, как у любой программы на С должна существовать функция main, всегда вызывающая yyparse(). Далее, для печати сообщений об ошибках должна вызываться функция yyerror().
Эти функции в той или иной форме должны задаваться пользователями. Для облегчения этой задачи существует библиотека, содержащая версии по умолчанию для функций main() и yyerror(). Имя библиотеки зависит от системы, во многих системах она задается флагом -ly компоновщика. Эти программы очень просты, их текст приведен ниже:
main() {return(yyparse());}
и
#include <stdio.h>yyerror(s) char *s; {fprintf(stderr, "%s0, s);}
Аргументом функции yyerror() служит строка, содержащая сообщение об ошибке. Прикладная программа наверняка должна выводить некоторую конкретную фразу. Обычно отслеживаются номера строк и при ошибке выводится номер строки ошибочного оператора. Во внешней переменной yychar хранится номер очередной лексемы в момент обнаружения ошибки. Это может помочь при выдаче полезной диагностики. Так как функция main() обычно задается пользователем (для обработки аргументов и пр.), библиотека yacc полезна либо для небольших проектов, либо на ранних стадиях разработки. Внешняя переменная yydebug первоначально равна 0. Если ее значение отлично от 0, распознаватель будет подробно сообщать обо всех действиях, включая информацию о прочитанных лексемах и выполняемых операциях. В некоторых операционных системах эту переменную можно устанавливать с помощью отладчика.
20. Привести к нормальной форме Грейбах следующую грамматику:….
Грамматика G находится в нормальной форме Грейбаха, если все правила G имеют вид A®aa, где а – терминальный символ, а a – цепочка, состоящая их терминалов и нетерминалов, а также пустой цепочки:
"x [xÎaÞ xÎTÈNÈ{e}].
Изменение правил грамматики надо производить так, чтобы первоначальный и конечный языки совпадали.
Теорема 1: Если в грамматике есть правило А®a1Ba2 и правило В®b, то эти правила можно заменить эквивалентным правилом вида А®a1ba2.
Замечание: если А®a1Ba2 и В®b1|b2|…|bn, то А®a1b1a2|a1b2a2|…|a1bna2.
Правила вида А®Аa называются рекурсивными слева.
Теорема 2: Устранение рекурсивных слева правил. Если в грамматике G имеется правило А®Аa и А®b, то эти правила можно эквивалентно заменить правилами А®b|bA’ и А’®a|aA’.
Доказательство: Рассмотрим, какие цепочки порождают первые правила. А®Аa®Аa2®*Aam, где m³1. А®*bam, где m³0.
Покажем, что с помощью эквивалентных правил получаем те же цепочки.
A'®aA’®a2A’®*am, где m³1. A®bA’®*bam, где m³0.
Замечание: Если А®Аa и А®b1|b2|…|bn, то А ???( то А®b1A’|b2A’|…|bn A’. )
Теорема 3: Для любого e-свободного КС-языка можно определить КС-грамматику в нормальной форме Грейбаха. При этом язык сохраняется.
Алгоритм:
G: S®AS|AB
A®BS|a
B®AA|b
Шаг 1: Нумерация нетерминалов. {S, A, B} ~ {A1, A2, A3}
G: A1® A2 A1| A2 A3
A2® A3 A1|a
A3® A2 A2|b
Шаг 2: Преобразовать все правила к виду Ai®aja (i£j).
Воспользуемся теоремой 1. A3®A2A2. Есть правило A2®A3A1|a. Заменяем исходное правило для A3 на два: A3® A3A1A2| aA2
G: A1® A2 A1| A2 A3
A2® A3 A1|a
A3® A3A1A2|aA2|b
Шаг 3: Устранить рекурсию слева: A3® A3A1A2|aA2|b. По теореме 2 заменяем первое правило на A3®aA2|b|aA2A’3|bA’3 и A’3® A1A2|A1A2A’3.
G: A1® A2 A1| A2 A3
A2® A3 A1|a
A3® aA2|b|aA2A’3|bA’3
A’3® A1A2|A1A2A’3
Шаг 4: Преобразовать правила с использованием теоремы 1 по убыванию номеров нетерминалов.
T1:Ai::=aAjb & Aj::=c1|c2|…|cn => Ai::=ac1b|ac2b|…|acnb
1.A’3® A2A1A2| A2A3A2| A2A1A2A’3| A2A3A2A’3
2. A’3® A3 A1 A1A2|a A1A2| A3 A1A2A3A2| aA2A3A2| A3 A1 A2A1A2A’3| |a A2A1A2A’3| A3 A1A2A3A2A’3|a A2A3A2A’3 итд. итп.
Дата добавления: 2015-01-29; просмотров: 119; Мы поможем в написании вашей работы!; Нарушение авторских прав |