И.А. Волкова, И.Г. Головин, Л.Е. Карпов - Системы программирования (1114897), страница 34
Текст из файла (страница 34)
Единственным ихнедостатком по сравнению с LR(1)-грамматиками является то, что LALR(1)грамматики ограничивают возможности распознавателей по обнаружению ошибок вовходных цепочках символов, точнее заставляют для обнаружения ошибок делатьбольше шагов вывода. Этот недостаток не может умалить важного достоинстваLALR(1)-грамматик – возможности автоматического построения практическиприменимых генераторов синтаксических анализаторов, к которым принадлежит иYacc.Программа Yacc работает примерно по тому же трехшаговому алгоритму, что ипрограмма Lex: сначала создается текст искомого анализатора на языке Си (Си++,Java, Pascal, …), затем он компилируется нужным компилятором, после чего можетпередаваться на исполнение, во время которого будет анализировать синтаксисподаваемых ему на вход текстов:Исходнаяпрограмма Yacctranslate.yКомпиляторYaccy.tab.cКомпиляторСиВходной потоксимволовпрограммыПрограммаанализатораy.tab.cПрограммаанализатораВыходИсходная Yacc-программа имеет три части: объявления, правила трансляции иподпрограммы поддержки.
В исходном описании указанные разделы отделяются другот друга строками из двух символов ‘%%’. По своей структуре эти части напоминают120разделы, обрабатываемые генератором лексических анализаторов, однако в разделеобъявлений вместо определений регулярных выражений записываются определениялексем, например,%token DIGIT%token IDЛексемы, определенные в этом разделе, могут использоваться в правилахтрансляции. Правила трансляции представляют собой обычные грамматическиеправила грамматик с действиями, записываемые по специальным правилам:<Левая часть> :|.
.|;<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() возвращает пары лексема-значение.121Если функция возвращает лексему типа DIGIT, эта лексема должна бытьпредварительнообъявленавпервомразделеспецификации.Значение,соответствующее обнаруженной лексеме, возвращается через предопределеннуюпеременную yylval.Генераторы синтаксических анализаторов должны иметь средства, позволяющиеим разрешать неоднозначности, часто имеющиеся в контекстно-свободныхграмматиках, в том числе в LALR(1)-грамматиках. Например, для правила грамматикиE → E+E|E-E|E*E|E/E|(E)|-E|numberв программе для Yacc следует писать такие правила:%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, который способенпостроить распознаватель по любому правильному регулярному выражению, генератор122Yacc не всегда способен решить поставленную перед ним задачу.
Это связано с тем,что заданная контекстно-свободная грамматика может оказаться не соответствующейограничениям LALR(1)-грамматик. В этом случае генератор выдает сообщение обошибке, то есть о наличии неразрешимого конфликта в LALR(1)-грамматике.Пользователю необходимо или преобразовать грамматику, или ввести дополнительныеправила, облегчающие построения анализатора.Современные генераторы синтаксических анализаторов Yacc (а также другиегенераторы, выполняющие аналогичные построения, например, Bison) представляютсобой мощные программные инструменты. С их помощью построены реальныеанализаторы для различных компиляторов и прикладных систем.123ЛитератураОсновная литература•••••••••••••Материалы к курсу “Системы программирования” и практикуму на ЭВМ(http://sp.cmc.msu.ru/win/courses/prak2/index.html, http://cmcmsu.no-ip.info/2course/).И.
А. Волкова, Т. В. Руденко. “Формальные грамматики и языки. Элементы теориитрансляции”, М.: МГУ, 1999 (Шифр в библиотеке МГУ: 5ВГ66 В-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(“Мобильность программного обеспечения”, под ред. П. Брауна, М., Мир, 1980).Joseph M. Fox.
“Software and its development”. Prentice-Hall, Inc., Englewood Cliffs,1982 (Дж. Фокс, “Программное обеспечение и его разработка”, М., Мир, 1985).P. Genuys (ed.). “Programming Languages”, Academic Press, 1968 (“Языкипрограммирования”, под ред. Ф. Женюи, М., “Мир”, 1972).David Gries. “Compiler construction for digital computers”, John Wiley and sons, Inc.,1971 (Д. Грис. “Конструирование компиляторов для цифровых вычислительныхмашин”, М., “Мир”, 1975).P.
M. Lewis, D. J. Rosenkranz, R. E. Stearns. “Compiler Design Theory”, AddisonWesley, Reading, MA, 1976 (Ф. Льюис, Д. Розенкранц, Р. Стирнз. “Теоретическиеосновы проектирования компиляторов”, М.: “Мир”, 1979).Robert Morgan. “Building an optimizing compiler”, Butterworth-Heinemann, 1998.Steven S. Muchnick. “Advanced compiler design and implementation”, MorganKaufmann Publishers, Inc., 1997.Дополнительная литература из библиотеки МГУ•••••А. М. Вендров. “CASE-технологии. Современные методы и средствапроектирования информационных систем”,http://www.citforum.ru/database/case/index.shtml.Л. Е. Карпов. "Архитектура распределенных систем программного обеспечения",М., МАКС Пресс, 2007.
Шифр в библиотеке МГУ: 5ВГ66, К-265.Н. Н. Мансуров, О. Л. Майлингова. “Методы формальной спецификации программ:языки MSC и SDL”, М.: Изд-во “Диалог-МГУ”, 1998 (Шифр в библиотеке МГУ:5ВГ66 М-238).И. О. Одинцов. “Профессиональное программирование. Системный подход”, СПб.:“БХВ-Петербург”, 2002 (Шифр в библиотеке МГУ: 5ВГ66 О-425).Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. “Compilers. Principles, techniques andtools”. Addison-Wesley Publishing Company, Inc., 1985 (Альфред Ахо, Рави Сети,124•••••Джеффри Ульман.
“Компиляторы. Принципы, технологии, инструменты”, М.: Изд.дом “Вильямс”, 2001. Шифр в библиотеке МГУ: 5ВГ66 А-955).Grady Booch. “Object-Oriented Analysis and Design with Applications”,Benjamin/Cummings, 1990, Addison-Wesley Publishing Company, Inc., 1994 (Г. Буч“Объектно-ориентированный анализ и проектирование с примерами приложений наС++”, 2-е издание, М., СПб.: “Бином” – “Невский диалект”, 1998.
Шифр вбиблиотеке МГУ: 5ВГ66 Б-947; http://redlib.narod.ru/cidocs/buch.zip).Anton Eliëns. “Principles of Object-Oriented Software Development”. Second edition,Addison-Wesley, 2000 (А. Элиенс. “Принципы объектно-ориентированнойразработки программ”, 2-е издание. М.: Издательский дом “Вильямс”, 2002. Шифр вбиблиотеке МГУ: 5ВГ66 Э-460).M.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
