А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 54

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 54)

Синтаксический анализ ! ж) Грамматика для булевых выражений: Ьехрг — Ьехрг ог Ь!егт ~ Ьгегт Ь!егт — Ь|егт апй 6~асгог ! В~ас1ог Ь7асгог — пот Ь|асюг ! (Ьехрг) ~ тгне ! Га)яе Упражнение 4.2.3. Разработайте грамматику для следующих языков. а) Множество всех строк из 0 и 1, таких, что за каждым 0 следует, по меньшей мере, одна 1. ! б) Множество всех строк из 0 и 1, являющихся лалиндромами, т.е.

строками, которые одинаковы при чтении как слева направо, так и справа налево. ! в) Множество всех строк из 0 и 1 с одинаковым количеством 0 и 1. !! г) Множество всех строк из 0 и 1 с количеством О, не равным количеству 1. ! д) Множество всех строк из 0 и 1, в которых не встречается 011 в качестве подстроки. !! е) Множество всех строк из 0 и 1 вида ху, где х ф у и х и у имеютодинаковую длину. Упражнение 4.2.4. Существуют достаточно распространенные расширения описания грамматик. В их число входят являющиеся метасимволами (как — или ~) квадратные и фигурные скобки в телах продукций, имеющие следующие значения. 1) Квадратные скобки, в которые заключен грамматический символ или символы, означают необязательность данной конструкции. Таким образом, продукция А — Х 1У) Я имеет то же действие, что и две продукции А — Х У х иА- ХЯ.

й) Фигурные скобки вокруг грамматического символа или символов говорят о том, что эти символы могут повторяться любое число раз, включая нуль. Таким образом, продукция А — Х (У Я) эквивалентна бесконечной последовательности продукций А — Х, А - Х У х,, А — Х У х У Я и т.д. Покажите, что эти два расширения не повышают мощность грамматик, т.е. что любой язык, который может быть сгенерирован грамматикой с данными расширениями, может быть сгенерирован и грамматикой без расширений. 271 4.2.

Контекстно-свободные грамматики Упражнение 4.2.5. Воспользуйтесь фигурными скобками, описанными в упражнении 4.2.4, чтобы упростить приведенную ниже грамматику блоков и условных конструкций: яятг — !1 ехрг 1Ьеп иятя е)ве иятя )1и1т! ФЬеп иятг Ьей!и яятЖит епд и~тймя — ~ иит1; и!тйли! ~ ият! ! Упражнение 4.2.6. Расширьте идею, приведенную в упражнении 4.2.4, чтобы позволить использование в теле продукций произвольных регулярных выражений грамматических символов. Покажите, что такое расширение не позволяет грамматикам определить ни один новый язык. ! Упражнение 4.2.7. Грамматический символ Х (терминал или нетерминал) бесполезен (цяе)еяя), если не существует порождения вида Я =~ шХу ~ шхр, т.е.

Х никогда не появляется в порождении некоторого предложения. а) Разработайте алгоритм для удаления из грамматики всех продукций, содержащих бесполезные символы. б) Примените свой алгоритм к следующей грамматике:  — 0)А А — А  — ~ 1 Упражнение 4.2.8. Грамматика на рис. 4.7 генерирует объявления для отдельных числовых идентификаторов; зти объявления включают четыре различных независимых свойства чисел. а) Обобщите грамматику на рис. 4.7, чтобы она позволяла иметь и атрибутов А, для некоторого фиксированного н и для 1 = 1, 2,..., и, где А; может быть либо ан либо Ьь Ваша грамматика должна использовать только О (и) грамматических символов и иметь общую длину продукций, равную О (и). ! б) Грамматика на рис.

4.7 и ее обобщение в части а упражнения допускают противоречащие и/или избыточные объявления, такие как с1ес1аге 1оо геа1 Яхес! геа1 й1оаГ1пд Можно потребовать, чтобы синтаксис языка запрещал такие объявления, т.е. чтобы каждое объявление, генерируемое грамматикой, имело только Глава 4. Синтаксический анализ одно значение для каждого из и атрибутов. Если сделать это, то для любого фиксированного п будет существовать только конечное количество корректных объявлений. Язык корректных объявлений (как и любой конечный язык) имеет грамматику (а также регулярное выражение). Очевидная грамматика, в которой стартовый символ имеет продукцию для кахслого корректного объявления, содержит п! продукций общей длиной О (и х и!). Вы должны справиться лучше: общая длина продукций вашей грамматики должна составлять О (п2").

!! в) Покажите, что любая грамматика из части б упражнения должна иметь общую длину продукций не менее 2". г) Что говорит часть в упражнения об обеспечении требования неизбыточности и непротиворечивости атрибутов объявлений посредством синтаксиса языка программирования? — цес1аге Ы орйопЕ1зг — орйопЕЫГ орйоп ! е — тле ~ зса1е ~ ргестоп ~ Ьые геа1 ~ сошр1ех — йхеп ~ йоайпй — гйпй!е ~ доиЫе — Ыпагу ! песппа1 ягтГ ор11опЕпГ орг1оп тос1е зса1е ргесюз1оп базе Рис. 4.7. Грамматика для многоатрибутных обьявлений 4.3 Разработка грамматики Грамматикой можно описать большую часть (но не весь) синтаксиса языков программирования. Например, требование объявления идентификаторов до их использования не может быть описано контекстно-свободной грамматикой.

Значит, последовательности токенов, принимаемые синтаксическим анализатором, образуют надмножество языка программирования; последующие фазы компилятора должны анализировать выход синтаксического анализатора, чтобы обеспечить его соответствие правилам, которые не проверяются синтаксическим анализатором. Этот раздел начинается с рассмотрения разделения работы между лексическим и синтаксическим анализаторами.

Затем будут рассмотрены преобразования, которые могут быть применены для получения грамматики, в большей степени приспособленной для синтаксического анализа. Один метод предназначен 273 4тн Разработка грамматики для устранения неоднозначности грамматики, другие (устранение левой рекурсии и левая факторизация) — для переписывания грамматики в виде, пригодном для нисходящего синтаксического анализа.

Завершится этот раздел рассмотрением некоторых конструкций языков программирования, которые не могут быть описаны ни одной грамматикой. 4.3.1 Лексический и синтаксический анализ Как говорилось в разделе 4.2.7, все, что может быть описано при помощи регулярного выражения, может быть также описано и грамматикой.

Закономерен вопрос — почему же для определения лексического синтаксиса языка используются регулярные выражения? На то есть несколько причин. 1. Разделение синтаксической структуры языка на лексическую и не лексическую части представляег собой улобный способ разбиения начальной стадии компиляции на два модуля меньшего размера, что упрощает работу с ними. 2. Лексические правила языка часто очень просты, и для их описания не требуется такое мощное средство, как грамматика. 3. Регулярные выражения в общем случае предоставляют по сравнению с грамматикой более краткую и простую для понимания запись токенов. 4.

Автоматически создаваемые на основе регулярных выражений лексические анализаторы более эффективны, чем лексические анализаторы, построенные на основе грамматики. Четких правил, что именно следует отнести к лексическим правилам, а что— к синтаксическим, нет. Регулярные выражения в большей степени подходят для описания структуры таких конструкций, как идентификаторы, константы, ключевые слова н пробельные символы. Грамматики же более приспособлены для описания вложенных структур, таких как сбалансированные скобки, пары Ьея)пепй, соответствующие друг другу 11'-ГЬеп-е!яе, и т.п.

Эти вложенные струкгуры не могут быть описаны регулярными выражениями. 4.3.2 Устранение неоднозначности атг — И ехрг гЬеп зллг и его гЬеп зплг е!яе зллг оСЬег (4.9) Иногда для устранения неоднозначности грамматика может быть переписана. В качестве примера устраним неоднозначность из следующей грамматики с "висящим е1зе": 274 Глава 4.

Синтаксический анализ Здесь ое)зег означает любую другую инструкцию. Согласно этой грамматике со- ставная условная инструкция )!' Ег е)зеп Яг е!ае )!'Ез г)геп Яз е)ае Яз имеет дерево разбора, показанное на рис. 4.8з. Грамматика (4.9) неоднозначна, поскольку строка !!' Ег т)геп )!'Ез 1)геп Яг е!ае Яз (4.!0) имеет два дерева разбора, показанных на рис.

4.9. Е, Рис. 4.8. Дерево разбора для условной инструкции Е, Х, Рнс. 4.9. Два дерева разбора неоднозначного предложения Во всех языках программирования с условными инструкциями такого вида предпочтительно первое дерево разбора. Общее правило гласит: "сопоставить з Нижние индексы у Е и Я не означают разные нетерминалы; они предназначены только для того, чтобы отличать разные вхождения одного и того же нетерминала. 275 4.3.

Разработка грамматики — таге)геа лгтг орел згтг — К ехрг Феп таес)еег( зете еЬе таес)ееге лете ог)зег — и ехрг Феп лгтЕ и ехрт г!геп таесеееге зяте еЬе орел зете лгтг таге)гесЕ лЕтг орел лгтЕ Рис. 4.10. Однозначная грамматика для инструкций 1бг)зеп-е1ве 4.3.3 Устранение левой рекурсии Грамматика является леворекурсивной (1ей геспггйес, если в ней имеется нетерминал А, такой, что существует порождение А =~ Агг для некоторой строки гг. Методы нисходящего разбора не в состоянии работать с леворекурсивными грамматиками, поэтому требуется преобразование грамматики, которое устранило бы из нее левую рекурсию. В разделе 2.4.5 мы рассматривали непосредственную левую рекурсию (ппшег)1а1е !ей геспгвюп), при которой существует продукция вида А — Агг.

Сейчас же будет рассмотрен общий случай. В разделе 2.4.5 показано, как леворекурсивная пара продукций А — Агг ~ Ез может быть заменена нелеворекурсивными продукциями А — Е)А' А' — ггА' ( е Следует заметить, что С и производные ст него лзыки программирования включены в зтст класс. Несмотря нв то, что в семействе С-обрезных языков не используется ключевое слово гйеп, его роль играет звкрыввюшвя скобка условия, следуюшего зв!Г.

Характеристики

Список файлов книги