Л.Е. Карпов - Системы программирования (1119429), страница 33
Текст из файла (страница 33)
Так же обрабатываютсявспомогательные процедуры, входящие в третий раздел программы lex.l.Правила трансляции программы lex.l имеют видpi{действиеi}где каждое pi есть регулярное выражение, а каждое действиеi есть фрагментпрограммы, описывающий выполняемые лексическим анализатором действия, еслилексема соответствует регулярному выражению (шаблону) pi. Действия записываютсяна том же языке программирования, на котором должен быть сгенерирован анализатор(например, на том же языке Си):{spaces}{id}{number}“<”“<=”.{{{{{{/* Действия не определены, возврата нет */ }yylval = found_id (); return ID; }yylval = found_num (); return NUMBER; }yylval = LT; return RELATION; }yylval = LE; return RELATION; }/* Такое правило обычно ставится последним.Оно позволяет фиксировать ошибку,связанную с появлением символа, которыйне может начинать никакую лексему*/ }%%int found_id (void) {/* На первый символ идентификатора указывает переменная yytext.Длина идентификатора содержится в переменной yyleng.Процедура заносит лексему в таблицу анализатора*/}int found_num (void) {/* На первый символ числа указывает переменная yytext.Длина числа содержится в переменной yyleng.Процедура заносит лексему в таблицу анализатора*/}Третий раздел программы содержит различные вспомогательные процедуры,которые могут быть скомпилированы отдельно, но загружены должны быть вместе слексическим анализатором.Лексический анализатор, создаваемый программой Lex, работает ссинтаксическим анализатором по схеме однопроходного компилятора.
Главной118программой является синтаксический анализатор, который запрашивает лексемы улексического анализатора, начиная чтение оставшейся части исходного текстапосимвольно и продолжая его до тех пор, пока не будет найдена самая длиннаяпоследовательность, соответствующая одному из регулярных выражений pi (этопервое правило разрешения неоднозначностей при обработке регулярных выражений).Затем для найденного шаблона выполняется соответствующее действиеi. Чаще всегоэто действие возвращает управление синтаксическому анализатору (то естьзаканчивается оператором вида return Token). Но так бывает не всегда. В этихслучаях лексический анализатор продолжает поиск лексем в тексте, пока действие,соответствующее одной из них, не возвратит управление синтаксическому анализатору.Такой поиск лексем позволяет осуществить обработку последовательностей пробелов икомментариев.Лексический анализатор возвращает синтаксическому только код обнаруженнойлексемы.
В программе Lex предусмотрено, что дополнительные атрибуты лексемымогут содержаться в глобальной переменной yylval, текстовое представлениелексемы находится в переменной yytext, а длина лексемы в символах – в переменнойyyleng.Если какой-либо лексеме соответствуют сразу несколько шаблонов, товыбирается тот из них, который размещается в перечне шаблонов первым, поэтомучастные шаблоны следует ставить в этом перечне раньше общих (это второе правилоразрешения неоднозначностей при обработке регулярных выражений – порядокследования регулярных выражений имеет определяющее значение).
Например, шаблон{if}, который может быть записан для распознавания лексемы начала условногооператора, должен предшествовать шаблону {id}, которому соответствует всякийидентификатор, в том числе, идентификатор if.Строка “<=” будет соответствовать шаблону “<=”, несмотря на то, что шаблон“<” находится в перечне раньше. В данном случае длина соответствия шаблону “<”меньше, чем длина соответствия шаблону “<=”. Программа Lex позволяет проводить иеще более сложный анализ лексем. В частности, в ней имеются возможностииспользования прогностических операторов, позволяющих распознавать лексемы, взависимости от той последовательности символов, которые располагаются за ними.Свободно распространяемая версия программы Lex носит название Flex (fastlexical analyzer generator).
Эта программа генерирует лексические анализаторы, поскорости работы не уступающие анализаторам, запрограммированным вручную,поскольку в ней представление детерминированного конечного автомата транслируетсянепосредственно в программу (на основе операторов перебора – case), и не возникаетдополнительных затрат времени на интерпретацию таблицы переходов.6.2. Автоматизация построения синтаксических анализаторовПрактически все современные языки программирования, позволяющиесоздавать практически ценные программные комплексы, являются контекстнозависимыми.
Однако расширение возможностей грамматического описания языковвведением описаний действий, то есть замена обычных грамматик на грамматики сдействиями, позволяет снизить требования к используемым грамматикам, а значит, ксинтаксическим анализаторам и их генераторам.
Грамматики с действиями нашли себеприменение в программе автоматической генерации синтаксических анализаторов –Yacc (Yet another compiler-compiler – еще один компилятор компиляторов).119По сравнению с генератором лексических анализаторов, работающим срегулярными выражениями, работа генератора синтаксических анализаторовосложненавозможныминеоднозначностямивграмматиках.Генерациясинтаксического анализатора для произвольной контекстно-свободной грамматикиоказывается слишком сложным процессом. Не удается создать такой генератор дажедля LR(1)-грамматик. Только специальный вид LR(1)-грамматик, называемыйграмматиками LALR(1), то есть “Look Ahead” LR(1)-грамматиками, позволяетразработать метод разрешения конфликтов на основании правого контекста длиной 1.Класс LALR(1)-грамматик достаточно широк.
Любой контекстно-свободный языкможет быть задан такой грамматикой. Единственным их недостатком по сравнению сLR(1)-грамматиками является то, что LALR(1)-грамматики ограничиваютвозможности распознавателей по обнаружению ошибок во входных цепочкахсимволов, точнее заставляют для обнаружения ошибок делать больше шагов вывода.Этот недостаток не может умалить важного достоинства LALR(1)-грамматик –возможности автоматического построения практически осмысленных генераторовсинтаксических анализаторов, к которым принадлежит и Yacc.Программа Yacc работает примерно по тому же трехшаговому алгоритму, что ипрограмма Lex: сначала создается текст искомого анализатора на языке Си (Си++,Java, Pascal, … ), затем он компилир уется ну жным компилятором, после чего мо жетпередаваться на исполнение, во время которого будет анализировать синтаксисподаваемых ему на вход текстов:Исходнаяпрограмма Yacctranslate.yКомпиляторYaccy.tab.cКомпиляторСиВходной потоксимволовпрограммыПрограммаанализатораy.tab.cПрограммаанализатораВыходИсходная Yacc-программа имеет три части: объявления, правила трансляции иподпрограммы поддержки.
В исходном описании указанные разделы отделяются другот друга строками из двух символов ‘%%’. По своей структуре эти части напоминаютразделы, обрабатываемые генератором лексических анализаторов, однако в разделеобъявлений вместо определений регулярных выражений записываются определениялексем, например,%token DIGIT%token IDЛексемы, определенные в этом разделе, могут использоваться в правилахтрансляции. Правила трансляции представляют собой обычные грамматическиеправила грамматик с действиями, записываемые по специальным правилам:120<Левая часть> :|. .|;<Alt 1> {Семантическое действие 1}<Alt 2> {Семантическое действие 2}.<Alt n> {Семантическое действие n}Такой вид правил полностью соответствует нормальным формам Бэкуса-Наура сучетом специфики представления информации в текстах программ.
В правилах Yaccтерминальные символы представляются одиночными символами в одинарныхкавычках (‘c’). Нетерминальными символами считаются строки из букв и цифр, невзятые в кавычки и не объявленные ранее как лексемы. Альтернативы в правилахразделяются символами вертикальная черта ‘|’. После последней альтернативыкаждого правила ставится точка с запятой.
Стартовым символом считается левая частьпервого правила, но его можно определить с помощью директивы начала:%start exprСемантические правила записываются непосредственно на том языкепрограммирования, на котором будет формироваться синтаксический анализатор, но вних допускается использование специальных символов:••$$ представляет значение атрибута, связанного с нетерминалом в левойчасти,$i представляет значение, связанное с i-м грамматическим символом(терминалом или нетерминалом) справа.Семантическое действие, входящее в правило, обычно сводится к вычислению$$ по $i:expr:expr ‘+’ term{ $$ = $1 + $3; } | term ;По умолчанию выполняется простейшее семантическое действие:{ $$ = $1; }Подпрограммы поддержки пишутся на том языке программирования, накотором будет сформирован синтаксический анализатор. Среди этих подпрограммобязательно должна существовать функция с именем yylex(), которая выполняетлексический анализ текстов исходного языка.
Все остальные подпрограммы (например,процедуры обработки ошибочных ситуаций) добавляются только в случае их реальнойнеобходимости. Лексический анализатор yylex() возвращает пары лексема-значение.Если функция возвращает лексему типа DIGIT, эта лексема должна бытьпредварительнообъявленавпервомразделеспецификации.Значение,соответствующее обнаруженной лексеме, возвращается через предопределеннуюпеременную yylval.Генераторы синтаксических анализаторов должны иметь средства, позволяющиеим разрешать неоднозначности, часто имеющиеся в контекстно-свободныхграмматиках, в том числе в LALR(1)-грамматиках.
Например, для правила грамматикиE → E+E|E-E|E*E|E/E|(E)|-E|numberв программе для Yacc следует писать такие правила:121%token number%left ‘+’ ‘-’%left ‘*’ ‘/’%right UMINUS%%expr : expr ‘+’| expr ‘*’|‘-’|‘(’exprexprexprexpr{ $$ = $1 + $3; }{ $$ = $1 * $3; }%prec UMINUS { $$‘)’{ $$| expr ‘-’ expr { $$ = $1 - $3; }| expr ‘/’ expr { $$ = $1 / $3; }= - $2; }=$2; }| NUMBER;Из-за неоднозначности грамматики при генерации анализатора могут возникатьконфликты, о количестве которых генератор выдаст сообщение. Конфликтыразрешаются применением по умолчанию двух следующих правил:••Порядок правил имеет значение и, в случае конфликта, нужным правиломбудет считаться правило, стоящее в списке правил перед конфликтующим.Из конфликтующих правил выбирается то, которое задает максимальнодлинный контекст.
Это правило корректно разрешает конфликт,возникающий из-за кочующего else.Однако генератор Yacc позволяет пользователям самим влиять на способразрешения конфликтов, задавая приоритеты и ассоциативность терминальныхсимволов. В приведенном выше примере задано, что приоритет сложения равенприоритету вычитания, но меньше приоритета умножения и деления. Все этиоператорыобъявленылевоассоциативными.Можнотакжезадаватьправоассоциативность (%right) терминалов и их неассоциативность (%nonassoc),которая означает невозможность комбинирования операторов (например, операторовотношения ‘>’).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
