И.А. Волкова, И.Г. Головин, Л.Е. Карпов - Системы программирования (1114897), страница 33
Текст из файла (страница 33)
Натретьем шаге эта программа в своей работе осуществляет ввод и лексический анализтекстов исходного языка.Программа Lex основана на анализе и преобразовании регулярных выражений,с помощью которых записываются лексические правила. В программе Lex введенынесколько расширенные правила записи регулярных выражений, позволяющиеоптимизировать их. Для удобства записи регулярных выражений часто вводятся классысимволов. Запись [abc], где a, b и c – символы алфавита, означает регулярноевыражение a|b|c. Сокращенный класс символов типа [a-z] означает регулярноевыражение a|b|...|z. С использованием классов символов можно описатьидентификаторы как строки, заданные регулярным выражением [A-Za-z][A-Zaz0-9].
Символ ‘-’ используется для обозначения диапазона в классе символов,символ ‘.’ означает, что в классе символов на этом месте может стоять любой символ,кроме символа новой строки. Чтобы в класс символов поместить непосредственно самсимвол ‘.’ (или ‘-’), перед ними следует ставить символ обратной косой черты,например, класс символов [\.\-] состоит из двух символов ‘.’ и ‘-’.В записи регулярных выражений программы Lex имеются также следующиеспособы указания повторений некоторых последовательностей символов:P* - итерация (повторение нуль или более раз)P+ - усеченная итерация (повторение один или более раз)P? – необязательное вхождение (нуль или один раз)Двойные кавычки используются для цитирования, то есть непосредственногоуказания последовательности символов:“a.+*” обозначает строку из четырех символов (без самих кавычек)Приведем примеры записи регулярных выражений, правильных с точки зренияпрограммы Lex:if[a-z][a-z0-9]*[0-9]*([0-9]+“.”[0-9]*)|([0-9]*“.”[0-9]+)(“—-”[a-z]*“\n”)|(“ ”|“\n”|“\t”)+./*/*/*/*/*/*идентификатор ifидентификаторчисловещественное числовид комментарияпроизвольный символ*/*/*/*/*/*/Программа lex.l состоит из трех разделов: объявлений, правил трансляции ивспомогательных процедур.
В файле lex.l эти разделы следуют друг за другомименно в таком порядке, отделяясь друг от друга строками, состоящими из парныхсимволов процента ‘%%’.Раздел объявлений состоит из описаний переменных, именованных констант(идентификаторов, используемых для представления констант) и регулярныхопределений, которые используются в качестве компонентов регулярных выражений вправилах трансляции:116%{%}/* Определение именованных констант,обозначающих коды лексем, например,ID, NUMBER, DELIMITER/*delimspacesletterdigitidnumberРегулярные определения*/*/[ \t\n\b\v\r]{delim}+[A-Za-z][0-9]{letter}({letter}|{digit})*{digit}+%%Обычно описания переменных и констант записываются внутри скобок ‘%{’ и‘%}’. Все, что находится внутри таких скобок, непосредственно переписывается всоздаваемую программу лексического анализатора, не рассматривается как частьрегулярных определений или правил трансляции.
Так же обрабатываютсявспомогательные процедуры, входящие в третий раздел программы 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, работает ссинтаксическим анализатором по схеме однопроходного компилятора.
Главной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)грамматик достаточно широк и подходит для описания синтаксиса реальных языкоапрограммирования (даже таких нетривиальных, как Си++).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
