А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 75
Текст из файла (страница 75)
Однако неоднозначные грамматики с применением некоторых специальных приемов приводят к более эффективным синтаксическим анализаторам. + Нисходящий и восходящий синтаксический анализ. Синтаксические анализаторы в общем случае различаются по тому, работают ли они в нисходящем направлении (начиная со стартового символа грамматики и строя дерево разбора сверху вниз) или в восходящем (начиная с терминальных символов, образующих листья дерева разбора, и строя дерево снизу вверх). Нисходящие синтаксические анализаторы включают синтаксические анализаторы, работающие методом рекурсивного спуска, и Ь).-анализаторы; наиболее распространенными среди восходящих синтаксических анализаторов являются 1.К-анализаторы.
+ Проектирование грамматик. Грамматики для нисходящего синтаксического анализа спроектировать зачастую сложнее, чем грамматики для восходящего разбора. В них необходимо устранить левую рекурсию — ситуацию, когда нетерминал порождает строку, которая начинается с того же нетерминала. Следует также выполнить левую факторизацию — сгруппировать продукции для одного и того же нетерминала с общим префиксом тела продукции. + Синтаксические анализаторы, работающие методом рекурсивного слуска.
Эти синтаксические анализаторы используют для каждого нетерминала свою процедуру. Эта процедура просматривает входной поток и принимает решение о том, какая продукция должна быть применена для ее нетерминала. Терминалы в теле продукции в нужный момент проверяются на соответствие входным данным, а обработка нетерминалов в теле продукции заключается в вызове соответствующих процедур. При этом методе возможен возврат в случае выбора неверной продукции. 377 4АО. Резюме к главе 4 + 1Л, (1)-анализаторы.
Грамматика, такая, что корректная продукция для данного нетерминала может быть выбрана путем просмотра только одного очередного входного символа, называется ЕЕ (1)-грамматикой. Такие грамматики позволяют строить таблицы предиктивного синтаксического анализа, которые для каждого нетерминала и входного символа дают корректный выбор продукции. Обработка ошибок может быль облегчена путем размещения подпрограмм для обработки ошибок в некоторых (нли во всех) записях таблицы, в которых нет корректных продукций. + Синтаксический анализ методом переноса/свертки.
Восходящие синтаксические анализаторы в общем случае работают путем выбора на основе очередного входного символа (символа предпросмотра) и содержимого стека выполняемого действия — переноса очередного входного символа в стек или свертки нескольких символов на вершине стека. Свертка заменяет тело продукции на вершине стека заголовком этой продукции. + Активные префиксы.
В синтаксическом анализе методом переноса/свертки содержимое стека всегда представляет собой активный префикс, т.е. префикс некоторой правосентенциальной формы, который завершается не правее конца основы этой правосентенциальной формы. Основа представляет собой подстроку, образующуюся на последнем шаге правого порождения сентенциальной формы. + Допустимые пункты. Пункт представляет собой продукцию с точкой в некотором месте в теле продукции. Пункт является допустимым для активного префикса, если продукция этого пункта используется для генерации основы, а активный префикс включает все символы слева от точки, но не справа. + !.й-анализаторы.
Каждый из нескольких видов 1.К-синтаксических анализаторов начинает работу с построения множеств допустимых пунктов (именуемых 1.К-состояниями) для всех возможных активных префиксов и отслеживает состояние для каждого префикса в стеке. Множество допустимых пунктов определяет принятие решения о выполняемом действии. Если существует допустимый пункт с точкой на правом конце тела продукции, выбирается свертка; если очередной символ находится непосредственно справа от точки в некотором допустимом пункте, то выполняется перенос этого символа в стек.
+ Б1.й-синтаксические анализаторы. В БЕК-анализаторе мы выполняем свертку, вызванную допустимым пунктом с точкой на правом конце, при условии, что очередной входной символ может следовать за заголовком применяемой для свертки продукции в некоторой сентенциальной форме. 378 Глава 4. Синтаксический анализ Грамматика принадлежит классу БЬК, а описанный метод применим, если отсутствуют конфликты действий, т.е. если не существует такого множества пунктов и входного символа, для которых имеются две продукции для свертки или имеется возможность как свертки, так и переноса.
+ Канонические 1В-анализаторы. Этот более сложный вид ЬК-анализаторов использует пункты, дополненные символами входного потока, которые могут следовать после свертки по соответствующей продукции. Свертка осуществляется только в том случае, если существует допустимый пункт с точкой на правом конце и текущий входной символ — один из разрешенных для данного пункта. Канонический ЬК-анализатор может избежать некоторых конфликтов действий БЬК.-анализатора, но зачастую имеет существенно большее количество состояний, чем Я К-анализатор для той же грамматики. + ЬАЬВ-синтаксические анализаторы. ЬАЬК-анализаторы обладают многими преимуществами БЬК и канонических ЬК-анализаторов, объединяя состояния, которые имеют одни и те же ядра (множества пунктов без связанных с ними множеств входных символов).
Таким образом, количество состояний оказывается тем же, что и у БЬК-анализатора, но в ЬАЬК-анализаторе может быть устранен ряд конфликтов Я.К-анализатора. На практике чаще всего используется именно этот метод синтаксического анализа. + Восходящий синтаксический анализ неоднозначнык грамматик.
Во многих важных ситуациях, таких как синтаксический анализ арифметических выражений, можно использовать неоднозначную грамматику с применением сторонней информации, такой как приоритеты операторов, для разрешения конфликтов между переносом и сверткой или между переносами по двум разным продукциям. Таким образом, 1.К-метод синтаксического анализа распространяется на многие неоднозначные грамматики. + Тасс. Генератор синтаксических анализаторов хасс принимает (возможно) неоднозначную грамматику и информацию для разрешения конфликтов и строит 1.А1.К-состояния. Затем он создает функцию, которая использует эти состояния для выполнения восходящего синтаксического анализа и вызывает при выполнении сверток связанные с ними функции.
4.11 Список литературы к главе 4 Формализм контекстно-свободных грамматик был введен Хомоки (Спошзку) [5) в процессе изучения естественных языков. Эта идея была использована в описании синтаксиса двух ранних языков: гопгап — Бэкусом (Вас)озз) 12] и А18о! 60— 4,1!. Список литературы к главе 4 379 Науром (Ь!аиг) [26]. Ученый Папини (Рап!ш) разработал эквивалентную синтаксическую запись для описания правил грамматики санскрита между 400 и 200 годами до н.э.
[19]. Явление неоднозначности впервые было рассмотрено Кантором (Сап!ог) [4] и Флойдом (Р!оуд) [13]. Нормальная форма Хомоки (см. упражнение 4.4.8) была разработана в [6]. Обзор теории контекстно-свободных грамматик можно найти в [17]. Синтаксический анализ методом рекурсивного спуска использовался в ранних компиляторах, таких как [16], и системах разработки компиляторов, таких как МЕТА [28] и ТМО [25].
ЬЬ-грамматики были предложены Льюисом (Ьеичз) и Стирнсом (8!еашв) [24]. Упражнение 4.4.5 взято из [3]. Идея приоритета операторов и использования функций приоритетов принадлежит Флойду (Р[оуд) [14]. Эта идея была обобщена для части языка, не содержащей операторы, Виртом (%птЬ) и Вебером (%еЬег) [29]. Сегодня эти методы сами по себе используются редко, но они являются ведущими среди усовершенствований Ьй-анализа.
ЬК-грамматики и синтаксические анализаторы были введены Кнутом (Кпи!Ь) [22], который описал построение канонических таблиц Ьй.-анализа. Ьй.-метод не рассматривался как практический, поскольку таблицы синтаксического анализа превышали имевшуюся в то время оперативную память типичного компьютера, до тех пор, пока Кореньяк (Когеп]а)г) [23] не разработал метод получения таблиц вполне разумного размера для синтаксического анализа типичного языка программирования.
Де Ремер (ПеКешег) разработал методы ЬАЬК [8] и БЬК [9], которые используются и сегодня. Построение таблиц ЬК-анализа для неоднозначных грамматик рассматривалось в [! и ! 2]. Хасс Джонсона ()оЬпзоп) очень быстро продемонстрировал практичность генерации ЬАЬК-синтаксических анализаторов для разработки компиляторов. Руководство по использованию Хасс можно найти в [20].
Версия с открытым кодом— Вйвоп — описана в [10]. Похожий генератор на основе ЬАЬК-анализа, называющийся С0Р [18], поддерживает действия, написанные на )ауа. Существующие в настоящее время генераторы нисходящих анализаторов включают Ап~1г [27]— поддерживающий действия на С++, )ача и С№ генератор анализаторов, работающих методом рекурсивного спуска, и ЬЬСеп [15] — генератор ЬЬ (1)-анализаторов. Библиография по обработке синтаксических ошибок собрана Дейном (Па!и) [7]. Алгоритм синтаксического анализа общего назначения с использованием динамического программирования был разработан независимо Коком (Ь Сос!ге) (не опубликовано), Янгером (Уоппйег) [30] и Касами (Казаш!) [2 !], откуда и получил свое название.
Имеется более сложный алгоритм общего назначения Эрли (Еаг!еу) [11], который табулирует ЬК-пункты для каждой подстроки данной входной 380 Глава 4. Синтаксический анализ 1. АЬо, А. И, Я. С. 1оЬпьоп, апд 1. О. Б!1шап, "Оегепп!и!або рагяп8 оГ агпЬ!8иова 8гапппагь", Сотт. АСМ 18:8 (Аи8., 1975), рр.
441-452. 2. Вас(сил, Х И!., "ТЬе лунгах апд лешап6св оГгЬе ргоровед !пгеглабопа! а18еЬга!с 1ап8иа8е оГгЬе Хит!сЬ-АСМ-бАММ СопХегепсе", Ргое. 1пг!. Сон!: 1п~оггпаг!оп Ргосехгтд, 1ЛЯЕЯСО, Рапв (1959), рр. 125-132. 3. Впгпап, А. апг) 1. О. 1Л!гпап, "Рагяп8 а!8опГЬпь ичГЬ Ьас(гГгас(с", 1п!огтабоп апг! Сои!го! 23:1 (1973), рр.
1 — 34. 4. Сап!от, О. С., "Оп Сбе ашЫ8шГу ргоЫеш оГ Вас(озя яуаГепь", Х АСМ 9:4 (1962), рр. 477-479. 5. СЬошйу, Х., "ТЬгее шоде!в Гог 1Ье бевсг!рбоп оГ!ап8иа8е", 1КЕ Тгапк оп 1п/огтапоп ТБеогу 1Т-2:3 (1956), рр. 113 — 124. СЬошвку, Х., "Оп сеггаш Гопиа( ргорегбев оГ 8гапипагв", 1п~оггпаг!оп апг! Сои!го! 2:2 (!959), рр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
