А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 73
Текст из файла (страница 73)
Каждое правило состоит из продукции грамматики и связанных семантических действий. Множество продукций, которые мы записывали как (Ьеад) (Ьоду) ~ (Ьоду)з ~ . ~ (Ьойу) 366 Глава 4. Синтаксический анализ ()Тпс1ис(е <ссуре.Ь> Ъ) %со)сеп Р161Т %% 11пе : ехрг '~п' ргйпгг("Ъс(~п", $1)г « 88 = 81 + 83г ) ехрг : ехрг '+' сегш ! сегш ( 88 = 81 * 83г ) сегга : гегш '*' Тассог Тассог Тассог г '(' ехрг ')' 0161Т ( 38 = 32г ) %% уу1ех() ( зпг сг о = г3егсЬаг()г Н (Твс(1г31ь(с)) уу1зга1 = с-'О'; гесцгп 01Гз1Т; ) геГцгп сз Рис. 4.58, Хасс-спецификация простейшего калькулятора в Хасс записываются следующим образом: (Ьеас() — (Ьос(у) ( (Семантическое действие), ) (Ьог)у) ( (Семантическое действие) ) (Ьос(у) „( (Семантическое действие) „) В продукциях Хасс строки букв и цифр без кавычек, не объявленные как токены, считаются нетерминалами.
Отдельный символ в одинарных кавычках, например ' с', представляет терминальный символ с, а равно целочисленный 367 4.9. Генераторы синтаксических анализаторов код токена, представленного этим символом (т.е. 1.ех должен вернуть синтаксическому анализатору код символа ' с' как целое число). Альтернативные тела продукций разделяются вертикальной чертой, а за каждой продукцией с ее альтернативами и семантическими действиями ставится точка с запятой.
Первый заголовок считается стартовым символом. Семантические действия Хасс представляют собой последовательности инструкций С. В них могут использоваться специальные символы: бб представляет значение атрибута, связанного с нетерминалом в заголовке продукции, а 31— значение, связанное с (-м грамматическим символом (терминалом или нетерминалом) тела продукции. Семантическое действие выполняется при свертке связанной с ним продукции, так что обычно семантическое действие вычисляет значение 33 на основании значений 31. В спецификации Хасс две Е-продукции Š— Е+Т) Т и связанные с ними семантические действия выглядят как ехрг : ехрг '+' сегвз ( бб = $1 + $3; ) ! гепп Заметим, что нетерминал гегвз в первой продукции представляет собой третий грамматический символ (вторым является оператор '+').
Семантическое действие, связанное с первой продукцией, суммирует значения ехрг и сегаз тела продукции и присваивает полученную сумму атрибуту нетерминала ехрг в заголовке. Мы опускаем семантическое действие для второй продукции, поскольку для продукции телом из одного символа действие по умолчанию состоит в копировании значения атрибута. В общем случае семантическим действием по умолчанию является ( 3$ = $1; Заметьте, что в спецификации Хасс добавлена новая стартовая продукция 11пе : ехрг ' хп' ( рг1псГ("ЪФп", В1); ) Эта продукция говорит о том, что входной поток калькулятора представляет собой выражение, за которым следует символ новой строки.
Семантическое действие, связанное с этой продукцией, состоит в выводе десятичного значения выражения, за которым следует символ новой строки. Часть С-подпрограмм поддержки Третья часть спецификации Хасс содержит С-подпрограммы поддержки. Среди них обязательно должна находиться функция лексического анализатора уу1ех( ).
Обычно для получения уу1ех( ) используется Ьех; см. раздел 4.9.3, 368 Глава 4. Синтаксический анализ Другие функции, ~акис как подпрограммы восстановления после ошибок, могут быть добавлены при необходимости. Лексический анализатор уу1ех ( ) производит токены, каждый из которых состоит из имени токена и связанного значения атрибута. Если функция возвращает имя токена, такое как ))161Т, это имя токена должно быть объявлено в первой части спецификации Хасс.
Значение атрибута, связанного с токеном, передается синтаксическому анализатору через предопределенную в Хасс переменную уу1зга1. Лексический анализатор на рис. 4.58 очень "сырой". Он считывает входной поток по одному символу с использованием функции десс)зал ( ) .
Если считанный символ — цифра, ее значение сохраняется в переменной уу1ма1, а лексический анализатор возвращает имя токена Р161Т. В противном случае в качестве имени токена возвращается сам считанный символ. 4.9.2 Использование Тасс с неоднозначной грамматикой Модифицируем спецификацию Хасс так, чтобы полученный в результате калькулятор стал немного полезнее. Во-первых, обеспечим возможность работы с несколькими выражениями, по одному в строке (разрешив также пустые строки между выражениями).
Для этого изменим первое правило следующим образом: 11пев : 11пев ехрг '~п' ( ргтпГГ("ЪдМ", $2)г ) 11пев '~п' /* елзргу */ В Хасс пустая альтернатива (третья в данном примере) означает е. Во-вторых, расширим класс обрабатываемых выражений, включив числа вместо одиночных цифр, а также все арифметические операторы — +, — (как бинарные, так и унарные), * и /. Простейший путь определения такого класса выражений — неоднозначная грамматика Š— Е+ Е ~ Š— Е ) Е * Е ) Е/Е ( — Е ~ (Е) ~ ппшЬег Полученная в результате спецификация Хасс приведена на рис. 4.59.
Поскольку данная грамматика неоднозначна, ).А(.К-алгоритм будет генерировать конфликты действий синтаксического анализа. При этом Хасс сообщит о количестве имеющихся конфликтов. Описание множеств пунктов и конфликтов можно получить при запуске Хасс с опцией командной строки -ч. При этом Хасс выводит дополнительный файл у.
оц~рцГ, содержащий ядра множеств пунктов, найденные при синтаксическом анализе, описание конфликтов и удобочитаемое представление таблицы (.К-анализа, показывающее, каким образом разрешены 369 4.9. Генераторы синтаксических анализаторов а( №1пс1пс(е <спуре.)г> №1пс1пс(е <зсс)1о.Ь> №с(еТ1пе ХХЯТХРЕ с)опЬ1е %) %со)сеп И()МЕЕВ /* Тип с(опЬ1е для стека Хасс */ хейг '+' $1егс '*' '/' ЪгфдЬГ ()М1Н()Я ргфпГТ("Ъд~п", Я2); 11пез : 11пез ехрг '~п' 1з.пез '~п' /* ергу */ уу1ех() ( Тпг с; ий11е ( ( с = дессЬаг() ) == ' ' ); Тй ( (с == '.') ) ) (1зс(фдфс(с) ) ) ( ппдесс(с, зсс(1п); асалам("в1й", йуу1ча1)г геспгп Н()МВЕВ; гегпгп с; Рнс.
4.59. Спецификация Хасс улучшенного калькулятора конфликты. Если Хасс выявляет конфликты, файл у.опгрпг с информацией о конфликтах создается без подсказки со стороны пользователя. Если Хасс не получает иных указаний в своей спецификации, все конфликты разрешаются им исходя из следующих двух правил. ехрг : ехрг '+' ехрг ехрг '*' ехрг '/' '(' ехрг ехрг И()ИВЕВ ехрг ехрг ехрг ехрг ) / боргес ( ЯЯ ЯЯ ( ЯЯ ( ЯЯ ЯЯ ()М1Н()Я = Я1 + Я3; Я1 — ЯЗ; ) — Я1 * ЯЗ; — Я1 / ЯЗ; Я2; ) ( ЯЯ = — Я2; 370 Глава 4. Синтаксический анализ К Конфликт "свертка/свертка" разрешается выбором продукции, находящейся первой в спецификациях Тасс.
2. Конфликт "перенос!свертка" разрешается в пользу переноса. Это правило корректно разрешает конфликт, возникающий из-за неоднозначности "висящего е)зе". Поскольку эти правила по умолчанию не всегда представляют именно то, что требуется создателю компилятора, Хасс обеспечивает общий механизм для разрешения конфликтов "перенос!свертка*'. В части объявлений терминалам можно назначить приоритеты и ассоциативность. Объявление %1етс '+' задает операторы + и — как левоассоциативные, имеющие один и тот же уровень приоритета. Объявить оператор как правоассоциативный можно следующим образом: Ъгйд)тс Кроме того, можно обеспечить неассоциативность оператора (т.е. два оператора не могут быть скомбинированы никоим образом) следующим обьявлением; Ъпопаввос '<' Токены получают уровни приоритетов в том порядке, в котором они встречаются в части обьявленнй, начиная с наинизшего.
Токены в одном объявлении имеют одинаковые приоритеты. Таким образом, объявление Ег' т)з~ ЛПМВЯ на рис. 4.2 дает токену 0М1МГ)Я наивысший приоритет по сравнению с пятью предшествующими терминалами. Уасс разрешает конфликты "перенос!свертка" назначением приоритета и ассоциативности каждой продукции, участвующей в конфликте (так же, как и каждому терминалу, вовлеченному в конфликтную ситуацию). Если необходимо осуществить выбор между переносом входного символа о и сверткой в соответствии с продукцией А — а, то Хасс выполняет свертку, если приоритет продукции выше приоритета а или если приоритеты одинаковы и ассоциативность продукции— левая. В противном случае выбирается перенос. Обычно приоритет продукции устанавливается таким же, как у ее крайнего справа терминала. В большинстве случаев это разумное решение.
Например, в продукции Š— Е+Е ~ Е*Е 371 4.9. Генераторы синтаксических анализаторов мы предпочитаем свертку по продукции Š— Е + Е, если очередной входной символ — +, поскольку + в теле продукции имеет тот же приоритет, что и входной символ, и при этом он левоассоциативен. В случае очередного входного символа * мы предпочитаем перенос, поскольку входной символ имеет более высокий приоритет, чем + в теле продукции. В тех ситуациях, когда крайний справа терминал не обеспечивает корректный приоритет продукции, его можно изменить путем добавления к продукции дескриптора боргес (терминал) Прн этом приоритет и ассоциативность продукции будут такими же, как у использованного в дескрипторе терминала, который, как правило, определен в разделе объявлений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
