А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 62
Текст из файла (страница 62)
Следует отметить, однако, что ПС-анализ может быть адаптирован к разбору некоторых неоднозначных грамматик, таких как приведенная выше. При разрешении указанного конфликта "перенос/свертка" при обнаружении е!ае в пользу переноса синтаксический анализатор будет работать так, как мы ог него и ожидаем, связывая е!ае с предыдущим !Ьеп, которому еще не найдено соответствующее е!ае, Синтаксические анализаторы для таких неоднозначных грамматик мы рассмотрим в разделе 4.8. и Еще одна распространенная причина конфликта — когда у нас есть основа, но содержимого стека и очередного входного символа недостаточно для определения продукции, которая должна использоваться в свертке. Следующий пример иллюстрирует эту ситуацию.
30В Глава 4. Синтаксический анализ Пример 4.25. Предположим, имеется лексический анализатор, который возвращает имя токена Ы для всех имен независимо от их типа. Предположим также, что наш язык вызывает процедуры по именам с параметрами, заключенными в скобки, и что тот же синтаксис используется и для работы с массивами. Поскольку трансляции индексов массива и параметров процедуры существенно отличаются друг от друга, мы должны использовать различные продукции для порождения списка фактических параметров и индексов.
Следовательно, наша грамматика может иметь (среди прочих) продукции наподобие приведенных на рис. 4.30. Ы ( рагате!ег 1и~ ) ()) х)т~ (2) ктт~ (3) рагате~ег !1х) (4) ра«ате)ег 11х) (5) ра«атас« (6) ехрг (7) ехрг ((() ехрг 11га (9) ехрг 11х) ехрг:= ехрг рагате!ег 1и), рагате)ег рагатезег Ы Ы ( ехр«11кт ) Ы ехрг 1Ы, ехрг ехрг Рис. 4.30. Продукции, включающие вызов процедуры и обращение к массиву Инструкция, начинающаяся с р ( з., 3 ), будет передана синтаксическому анализатору как поток токенов Ы (Ы, Ы). После переноса первых трех токенов в стек ПС-анализатор окажется в конфигурации Стек Ы(Ы ВХОД ,Ы ) Очевидно, что токен Ы на вершине стека должен быть свернут, но какой продукцией? Правильный выбор — продукцией (5), если р — процедура, и продукцией (7), если р — массив.
Содержимое стека не может подсказать, чем является р; для принятия решения мы должны использовать информацию из таблицы символов, которая была занесена в стек при объявлении р. Одно из решений состоит в замене токена Ы в продукции (1) на ргосЫ и использовании более интеллектуального лексического анализатора, который возвращает ргосЫ при распознавании лексемы, представляющей собой имя процедуры. Такой способ требует от лексического анализатора обращения к таблице символов перед тем, как вернуть токен. 309 4.6. Введение в Ей-анализ: простой Ьй Если мы внесем эти изменения, то при обработке р(з, 3 ) синтаксический анализатор может оказаться в конфигурации Стек ВхОд ,Ы ) ргосЫ ( Ы либо в конфигурации, приведенной ранее. В первом случае мы выбираем свертку с использованием продукции (5), в последнем — с использованием продукции (7). Обратите внимание, что выбор определяется третьим от вершины символом в стеке, который даже не участвует в свертке.
Для управления разбором ПС-анализ может использовать информацию "из глубин" стека. и 4.5.5 Упражнения к разделу 4.5 Упражнение 4.5.1. Укажите основу каждой из приведенных ниже правосентен- цнальных форм для грамматики Я вЂ” 0 о 1 ! 0 1 из упражнения 4.2.2, ьл а) 000111; б) ООо11. Упражнение 4.5.2. Повторите упражнение 4.5.! для грамматики Ь' — Я Я + + ~ Я Я * ! а из упражнения 4.2.1 и следующих правосентенцнальных форм: а) ЗЯБ+а*+; б) ЯЯ + а * а+ „ в) ааа* а++. Упражнение 4.5.3.
Проведите восходящий синтаксический анализ для следую- щих входных строк и грамматик: а) входная строка 000111, соответствующая грамматике из упражнения 4.5.1; б) входная строка аао * а + +, соответствующая грамматике из упражнения 4,5.2. 4.6 Введение в ЕК-анализ: простой ЕК Наиболее распространенный тип восходящих синтаксических анализаторов на сегодняшний день основан на концепции, называющейся ) й(Й)-анализом; 1, здесь означает сканирование входного потока слева направо, й — построение правою порождения в обратном порядке, а й — количество предпросматриваемых З1О Глава 4. Синтаксический анализ символов входного потока, необходимое для принятия решения. Практический интерес представляют случаи и = О и )с = 1, и здесь будут рассмотрены только ЬК-анализаторы с /с < 1.
Если (й) опущено, считается, что й равно 1. В этом разделе рассматриваются базовые концепции ЬК-анализа и простейший метод построения ПС-анализаторов, называющийся простым ЬК (гагар!е ЬК вЂ” БЬК). Определенное знакомство с базовыми концепциями весьма полезно даже в том случае, когда для построения ЬК-анализатора используется автоматический генератор анализаторов. Мы начнем с "пунктов" и "состояний анализатора", диагностические сообщения генератора 1.К-анализаторов обычно включают состояния синтаксического анализатора, которые могут использоваться для выяснения источника конфликтов синтаксического анализа. В разделе 4.7 рассматриваются два более сложных метода — канонический ЬК и ЬАЬК вЂ” которые используются в большинстве ЬК-анализаторов.
4.6.1 Обоснование иенользования 1.К-анализаторов ЬК-анализаторы управляются таблицами наподобие нерекурсивных ЬЬ-анализаторов из раздела 4.4.4. Грамматика, для которой можно построить таблицу синтаксического анализа с использованием одного из методов из этого и следующего разделов, называется ЕЯ-:рамматцкой. Интуитивно, чтобы грамматика была 1.К.-грамматикой, достаточно, чтобы синтаксический анализатор, работающий слева направо методом переноса/свертки, был способен распознавать основы правосентенциальных форм при их появлении на вершине стека. ЬК-анализ весьма привлекателен по множеству причин.
° 1.К-анализаторы могут быть созданы для распознавания практически всех конструкций языков программирования, для которых может быть написана контекстно-свободная грамматика. Контекстно-свободные грамматики, не являющиеся 1.К-грамматиками, существуют, однако для типичных конструкций языков программирования их вполне можно избежать. ° Метод ЬК-анализа — наиболее общий метод ПС-анализа без возврата, который, кроме того, не уступает в эффективности другим, более примитивным ПС-методам 1см. список литературы к главе 4).
° ЬК-анализатор может обнаруживать синтаксические ошибки сразу же, как только это становится возможным при сканировании входного потока. ° Класс грамматик, которые могут быть проанализированы с использованием 1.К-методов, представляет собой истинное надмножество класса грамматик, которые могут быть проанализированы с использованием предиктивных или 1 Ь-методов синтаксического анализа. В случае грамматик, принадлежащих классу ЬК(к), мы должны быть способны распознать правую 4.6.
Введение в ЬК-анализ: простой ЬК часть продукции в порожденной ею правосентенциальной форме с дополнительным предпросмотром и входных символов. Это требование существенно мягче требования для ЬЬ(й)-грамматик, в которых мы должны быть способны распознать продукцию по первым й символам порождения ее тела. Таким образом, не должен казаться удивительным тот факт, что ЬК-грамматики могут описать существенно больше языков, чем ЬЬ- грамматики. Основной недостаток ЬК-метода состоит в том, что построение Ьй.-анализатора для грамматики типичного языка программирования вручную требует очень большого объема работы. Для решения этой задачи нужен специализированный инструмент — генератор ЬК-анализаторов. К счастью, имеется множество таких генераторов, и мы рассмотрим один из наиболее широко используемых — уасс— в разделе 4.9.
Такой генератор получает контекстно-свободную грамматику и автоматически строит ее синтаксический анализатор. Если грамматика содержит неоднозначности или другие конструкции, трудные для синтаксического анализа сканированием входного потока слева направо, генератор локализует их и предоставляет детальную диагностическую информацию. 4.6.2 Пункты н ЬК(0)-автомат Каким образом ПС-анализатор выясняет, когда следует выполнять перенос, а когда — свертку? Например, когда стек на рис.
4.28 содержит ЬТ, а очередной входной символ — *, каким образом синтаксический анализатор узнает, что Т на вершине стека — не основа, так что корректное действие — перенос, а не свертка Т в Е? ЬК-анализатор принимает решение о выборе "перенос/свертка", поддерживая состояния, которые отслеживают, где именно в процессе синтаксического анализа мы находимся. Состояния представляют собой множества "пунктов'*. ЬК (О)- пункт (для краткости — просто пункт ) грамматики С вЂ” это продукция С с точ- 5 кой в некоторой позиции правой части.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
