И.А. Волкова, И.Г. Головин, Л.Е. Карпов - Системы программирования (1119414), страница 33
Текст из файла (страница 33)
Главной117программой является синтаксический анализатор, который запрашивает лексемы улексического анализатора, начиная чтение оставшейся части исходного текстапосимвольно и продолжая его до тех пор, пока не будет найдена самая длиннаяпоследовательность, соответствующая одному из регулярных выражений pi (этопервое правило разрешения неоднозначностей при обработке регулярных выражений).Затем для найденного шаблона выполняется соответствующее действиеi.
Чаще всегоэто действие возвращает управление синтаксическому анализатору (то естьзаканчивается оператором вида return Token). Но так бывает не всегда. В этихслучаях лексический анализатор продолжает поиск лексем в тексте, пока действие,соответствующее одной из них, не возвратит управление синтаксическому анализатору.Такой поиск лексем позволяет осуществить обработку последовательностей пробелов икомментариев.Лексический анализатор возвращает синтаксическому только код обнаруженнойлексемы. В программе Lex предусмотрено, что дополнительные атрибуты лексемымогут содержаться в глобальной переменной yylval, текстовое представлениелексемы находится в переменной yytext, а длина лексемы в символах – в переменнойyyleng.Если какой-либо лексеме соответствуют сразу несколько шаблонов, товыбирается тот из них, который размещается в перечне шаблонов первым, поэтомучастные шаблоны следует ставить в этом перечне раньше общих (это второе правилоразрешения неоднозначностей при обработке регулярных выражений – порядокследования регулярных выражений имеет определяющее значение).
Например, шаблон{if}, который может быть записан для распознавания лексемы начала условногооператора, должен предшествовать шаблону {id}, которому соответствует всякийидентификатор, в том числе, идентификатор if.Строка “<=” будет соответствовать шаблону “<=”, несмотря на то, что шаблон“<” находится в перечне раньше. В данном случае длина соответствия шаблону “<”меньше, чем длина соответствия шаблону “<=”. Программа Lex позволяет проводить иеще более сложный анализ лексем. В частности, в ней имеются возможностииспользования прогностических операторов, позволяющих распознавать лексемы, взависимости от той последовательности символов, которые располагаются за ними.В программах на Фортране достаточно сложно распознавать такие операторыDO 1 I = 1.3DO 1 I = 1,3которые в этом языке эквивалентны следующим:DO1I=1.3DO1I=1,3В первом операторе (присваивания) до ввода десятичной точки невозможноопределить, являются ли буквы ‘D’ и ‘O’ частью идентификатора “DO1I”.
Во второйстроке (с заголовком цикла) буквы ‘D’ и ‘O’ составляют ключевое слово “DO”.Программа Lex позволяет записывать шаблоны в виде p1/p2, где p1 и p2 –регулярные выражения. Это означает, что шаблон соответствует строке p1 только в томслучае, если за ней следует строка, соответствующая p2. Регулярное выражение послепрогностического оператора ‘/’ указывает правый контекст соответствия, который118используется только для ограничения и не является частью шаблона. Например, дляраспознавания ключевого слова DO можно записать такой шаблон:DO/({letter}|{digit})*=({letter}|{digit})*,В соответствии с этой спецификацией лексический анализатор просматриваетвведённые символы после символов DO и отыскивает там последовательности букв ицифр, за которой следует знак “=” и ещё одна последовательность букв и цифр,заканчивающаяся символом “,”.
Если за буквами действительно следует такаяпоследовательность, то лексему составят только символы D и O, которые предшествуютв шаблоне прогностическому оператору ‘/’. При этом в переменную yylval будетзаписан указатель на букву D, а в переменную yyleng будет занесено значение 2(длина идентификатора DO).Прогностический оператор позволяет также распознавать ключевые слова втекстах на тех языках программирования, где эти ключевые слова не резервируются(Фортран, PL/1). Например, в Фортране и PL/1 строкаIF(I,J) = 3представляет собой правильный оператор присваивания элементу массива, но неусловный оператор.
Один из способов определения ключевого слова IF в программеLex состоит в указании его правого контекста с помощью прогностического оператора.В ситуации с указанными языками программирования, чтобы считать IF ключевымсловом, а не именем массива, следует сканировать исходный текст в поисках правой(закрывающей) скобки, за которой следует буква, а не знак равенства.
Шаблон для IF вФортране (где условие должно обязательно размещаться на одной строке текста) можетбыть записан так:IF / \( .* \) {letter}Точка со звездочкой означает многократное повторение любого символа, кромесимвола конца строки, а обратная косая черта перед скобками указывает, что скобки неявляются метасимволами группирования, а являются обычными символами. Для PL/1 исовременных версий языка Фортран шаблон должен быть несколько усложнён, чтобыдопустить поиск закрывающей скобки не только в той же строке, где записано словоIF, но и в последующих строках.Свободно распространяемая версия программы Lex носит название Flex (fastlexical analyzer generator). Эта программа генерирует лексические анализаторы, поскорости работы не уступающие анализаторам, запрограммированным вручную,поскольку в ней представление детерминированного конечного автомата транслируетсянепосредственно в программу (на основе операторов перебора – case), и не возникаетдополнительных затрат времени на интерпретацию таблицы переходов.6.2.
Автоматизация построения синтаксических анализаторовПрактически все современные языки программирования, позволяющиесоздавать практически ценные программные комплексы, являются контекстнозависимыми. Однако расширение возможностей грамматического описания языковвведением описаний действий, то есть замена обычных грамматик на грамматики сдействиями, позволяет снизить требования к используемым грамматикам, а значит, ксинтаксическим анализаторам и их генераторам. Грамматики с действиями нашли себе119применение в программе автоматической генерации синтаксических анализаторов –Yacc (Yet another compiler-compiler – еще один компилятор компиляторов).По сравнению с генератором лексических анализаторов, работающим срегулярными выражениями, работа генератора синтаксических анализаторовосложненавозможныминеоднозначностямивграмматиках.Генерациясинтаксического анализатора для произвольной контекстно-свободной грамматикиоказываетсяслишкомсложнымпроцессом.Однакосинтаксисязыковпрограммирования может быть описан грамматиками без неоднозначностей (т.к.
любаяправильная программа должна иметь единственную структуру), т.е. языкипрограммированияявляютсядетерминированными.Известно,чтолюбойдетерминированный язык может быть порожден так называемой LR(1)-грамматикой.Однако генераторы синтаксических анализаторов на основе произвольных LR(1)грамматик порождает анализаторы очень большого объема, что не позволяетиспользовать такие генераторы на практике.
Только специальный вид LR(1)грамматик, называемый грамматиками LALR(1), то есть “Look Ahead” LR(1)грамматиками, позволяет разработать метод разрешения конфликтов на основанииправого контекста длиной 1. Таблицы LALR(1)-анализатора весьма компактны, чтообеспечивает эффективность алгоритма анализа.
В то же время, класс LALR(1)грамматик достаточно широк и подходит для описания синтаксиса реальных языкоапрограммирования (даже таких нетривиальных, как Си++). Единственным ихнедостатком по сравнению с LR(1)-грамматиками является то, что LALR(1)грамматики ограничивают возможности распознавателей по обнаружению ошибок вовходных цепочках символов, точнее заставляют для обнаружения ошибок делатьбольше шагов вывода. Этот недостаток не может умалить важного достоинстваLALR(1)-грамматик – возможности автоматического построения практическиприменимых генераторов синтаксических анализаторов, к которым принадлежит иYacc.Программа Yacc работает примерно по тому же трехшаговому алгоритму, что ипрограмма Lex: сначала создается текст искомого анализатора на языке Си (Си++,Java, Pascal, …), затем он компилируется нужным компилятором, после чего можетпередаваться на исполнение, во время которого будет анализировать синтаксисподаваемых ему на вход текстов:Исходнаяпрограмма Yacctranslate.yКомпиляторYaccy.tab.cКомпиляторСиВходной потоксимволовпрограммыПрограммаанализатораy.tab.cПрограммаанализатораВыходИсходная Yacc-программа имеет три части: объявления, правила трансляции иподпрограммы поддержки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
