Л.Е. Карпов - Системы программирования (1114903), страница 34
Текст из файла (страница 34)
Например, шаблон{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),которая означает невозможность комбинирования операторов (например, операторовотношения ‘>’). Уровни приоритетов лексем определяются порядком их перечисленияв разделе объявлений, поэтому приоритет унарного минуса из приведенного примераоказывается выше приоритета умножения и деления.В правило можно вставлять явное задание приоритета правила с помощьюконструкции %prec <терминал> (как в предпоследней альтернативе на приведенномвыше примере). Используемый терминал может быть искусственно введенным.
Такойтерминал никогда не возвращается лексическим анализатором и объявляетсяединственно для того, чтобы определить приоритет правила. Именно поэтому унарныйминус, определяемый предпоследней альтернативой в приведенном примере, получаетнаивысший приоритет, по сравнению с другими операторами.В отличие от генератора лексических анализаторов Lex, который способенпостроить распознаватель по любому правильному регулярному выражению, генераторYacc не всегда способен решить поставленную перед ним задачу. Это связано с тем,что заданная контекстно-свободная грамматика может оказаться не соответствующейограничениям LALR(1)-грамматик. В этом случае генератор выдает сообщение обошибке, то есть о наличии неразрешимого конфликта в LALR(1)-грамматике.Пользователю необходимо или преобразовать грамматику, или ввести дополнительныеправила, облегчающие построения анализатора.Современные генераторы синтаксических анализаторов Yacc (а также другиегенераторы, выполняющие аналогичные построения, например, Bison) представляютсобой мощные программные инструменты.
С их помощью построены реальныеанализаторы для различных компиляторов и прикладных систем.122ЛитератураОсновная литература•••••••••••••Материалы к курсу “Системы программирования” и практикуму на ЭВМ(http://sp.cmc.msu.ru/win/courses/prak2/index.html, http://cmcmsu.no-ip.info/2course/).И. А.
Волкова, Т. В. Руденко. “Формальные грамматики и языки. Элементы теориитрансляции”, М.: МГУ, 1 9 9 (Шифр9в библиотеке МГУ: 5 ГВ6 6 В-676;http://sp.cmc.msu.ru/courses/prak2/lang_grams.pdf).А. В. Гордеев, А. Ю. Молчанов. “Системное программное обеспечение”, СПб.:“Питер”, 2002.А. Ю. Молчанов. “Системное программное обеспечение. Учебник для вузов”, СПб.:Питер, 2003.Alfred V. Aho, Jeffrey D. Ullman.
“The Theory of Parsing, Translation and Compiling”.Prentice-Hall, Inc., Englewood Cliffs, N. J., 1973 (А. Ахо, Дж. Ульман. “Теориясинтаксического анализа, перевода и компиляции”, в 2-х т., М.: “Мир”, 1978).Andrew W. Appel, Maia Ginsburg. “Modern compiler implementation in C”, CambridgeUniversity Press, 1998.P. J. Brown (ed.). “Software Portability”, Cambridge University Press, 1977(“Мобильность программного обеспечения”, под ред.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
