А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 61
Текст из файла (страница 61)
Синтаксический анализ завершается сверткой Т в стартовый символ Е. а По определению свертка представляет собой шаг, обратный порождению (вспомните, что в порождении нетерминал в сентенциальной форме замещается телом одной из его продукций). Цель восходящего синтаксического анализа, таким образом, состоит в построении порождения в обратном порядке. Вот порождение, соответствующее синтаксическому анализу, показанному на рис.
4.25: Е =~ Т =~ Т * Е =~ Т* Ы =~ Е* Ы ~ И я И Данное порождение является правым. 4.5.2 Обрезка основ Восходящий синтаксический анализ в процессе сканирования входного потока слева направо строит правое порождение в обратном порядке. Неформально говоря, основа, или дескриптор (папд!е), строки — это подстрока, которая соответствует телу продукции и свертка которой представляет собой один шаг правого порождения в обратном порядке.
4.5. Восходящий синтаксический анализ Например, основы в процессе синтаксического анализа Ы1 * Ыв (нижние индексы добавлены к токенам Ы для ясности) в соответствии с грамматикой (4А) показаны на рис. 4.26. Хотя Т вЂ” тело продукции Š— Т, символ Т не является основой в сентенциальной форме Т* Ыз. Если заменить Т на Е, мы получим строку Е * Ыз, которая не может быть порождена из стартового символа Е.
Таким образом, крайняя слева подстрока, которая соответствует телу некоторой продукции, не обязательно является основой. Рнс. 4.26. Основы в процессе синтаксического анализа строки Ы1 * Ыз Формально, если Я ~ аАю ~ а,3ю, как на рис. 4.27, то продукция А — )3 в позиции после о является основой (ЬапсПе) о)3ю. В качестве альтернативы основой правосентенциальной формы 7 является продукция А — )3 и позиция у, в которой может быть найдена строка )3, такая, что замена ~3 в данной позиции на А дает предшествующую правосентенциальную форму в правом порождении у. Рнс. 4.27. Основа А — ~3 в дереве разбора а,3н Заметим, что строка ю справа от основы должна содержать только терминальные символы.
Для удобства мы будем говорить как об основе о теле продукции )3, а не обо всей продукции А — ~3 в целом. Следует также заметить, что грамматика может быть неоднозначной, с несколькими правыми порождениями а,3ю. Если грамматика однозначна, то каждая правосентенциальная форма грамматики имеет ровно одну основу. Обращенное правое порождение может быть получено посредством "обрезки основ". Мы начинаем процесс со строки терминаловю, которую хотим проанализировать. Если ю — предложение рассматриваемой грамматики„то пусть ю = у„, где 7„— и-я правосентенциальная форма некоторого еще неизвестного правого порождения Я = 7с ~ у1 ~ -~з ~ =~ .~„, ~ 7„= ю.
Для воссоздания этого Зй4 Глава 4. Синтаксический анализ порождения в обратном порядке мы находим основу 1З„в Т„и заменяем ее левой частью продукции А„—,З„для получения предыдущей правосентенциальной формы Т„ы Заметим, что пока мы не знаем, каким образом искать основы, но вскоре познакомимся с соответствующими методами. Затем мы повторяем описанный процесс, т.е. находим в у„з основу 13„1 и свеРтываем ее длЯ полУчениЯ пРавосентенциальной фоРмы З„з. Если после очередного шага правосентенциальная форма содержит только стартовый символ Я, мы прекращаем процесс и сообщаем об успешном завершении анализа. Обращенная последовательность продукций, использованных в свертках, представляет собой правое порождение входной строки. 4.5.3 Синтаксический анализ мнеренос/свертка" Синтаксический анализ "перенос!свертка" (именуемый далее сокращенно ПС- анализом) представляет собой разновидность восходящего анализа, в которой для хранения символов грамматики используется стек, а для хранения остающейся непроанализированной части входной строки — входной буфер.
Мы используем символ $ для маркирования дна стека и правого конца входной строки. При рассмотрении восходящего анализа удобно располагать вершину стека справа (а не слева, как это делалось при рассмотрении нисходящего синтаксического анализа). Изначально стек пуст, а во входном буфере находится строка нн ВХОД и4 СТЕК 8 В процессе сканирования входной строки слева направо синтаксический анализатор выполняет нуль или несколько переносов символов в стек, пока не будет готов выполнить свертку строки () символов грамматики на вершине стека. Затем он выполняет свертку,9 к заголовку соответствующей продукции.
Синтаксический анализатор повторяет этот цикл до тех пор, пока не будет обнаружена ошибка или пока стек не будет содержать только стартовый символ, а входной буфер будет при этом пуст: ВХОД СТЕК Достигнув указанной конфигурации, синтаксический анализатор останавливается и сообщает об успешном завершении анализа. На рис. 4.28 пошагово показаны действия ПС-анализатора, выполняемые при синтаксическом анализе строки Ыз * 1пз согласно грамматике выражений (4.1). Хотя основными операциями являются перенос и свертка, всего ПС-анализатор может выполнять четыре действия: 1) перенос, 2) свертка, 3) принятие и 4) ошибка.
305 4.5. Восходящий синтаксический анализ Рис. 4.28. Конфигурации ПС-анализатора при входной строке Ы~:в Из 1. Перенос (ай1гг). Перенос очередного входного символа на вершину стека. 2. Свертка (гелосе). Правая часть сворачивасмой строки должна располагаться на вершине стека. Определяется левый конец строки в стеке и принимается решение о том, каким нетерминалом будет заменена строка. 3. Приняглие (ассер1). Объявление об успешном завершении синтаксического анализа. 4. Ошибка (еггог). Обнаружение синтаксической ошибки и вызов подпрограм- мы восстановления после ошибки. Использование стека в ПС-анализаторе объясняется тем важным фактом, что основа всегда находится на вершине стека и никогда — внутри него.
Это можно показать путем рассмотрения возможных видов двух последовательных шагов в любом правом порождении. На рис. 4.29 показаны эти два возможных случая. В случае (1) А заменяется на ДВу, после чего крайний справа нетерминал В в теле 1)Ву заменяется иа т. В случае (2) А снова раскрывается первым, но на этот раз тело представляет собой строку у, состоягцую из одних терминалов. Следующий крайний справа нетерминал В будет находиться где-то слева от у. Другими словами, имеем следующее: 1) Я 4 аАх ~ а~3Вух =ь аЯух ~'тп ~'тч тт 2) Я ~ аВхАх ~ аВхуа =ь о.~хух тт 306 Глава 4. Синтаксический анализ а г х Случай (2) Рнс.
4.29. Варианты двух последовательных шагов правого порождения Рассмотрим случай (1) в обратном порядке, начиная с момента, когда ПС- анализатор достиг конфигурации Синтаксический анализатор сворачивает основу у в В и достигает конфигурации Теперь синтаксический анализатор может выполнить перенос строки у в стек при помощи нуля или нескольких шагов переноса и получить конфигурацию Згу(ЗВу з3 с основой )зВр на вершине стека, после чего выполнить ее свертку в А. Теперь рассмотрим случай (2). В конфигурации основа у находится на вершине стека. После свертки основы у в В синтаксиче- ский анализатор может перенести строку жу для получения очередной основы у на вершине стека, готового к свертке в А: В обоих случаях после выполнения свертки синтаксический анализатор должен один или несколько раз перенести символы для получения в стеке очередной основы.
Он никогда не должен углубляться в ее поисках в стек. 4.5.4 Конфликты в процессе ПС-анализа Имеются контекстно-свободные грамматики, для которых ПС-анализ неприменим. Любой ПС-анализатор для такой грамматики может достичь конфигурации, )) у Случай (() Стек $(у)у'у ВхОд уа8 ЗО7 4.5. Восходящий синтаксический анализ в которой синтаксический анализатор, обладая информацией о содержимом стека и очередных й входных символах, не может принять решение о том, следует ли выполнить перенос или свертку (конфликт "перенос!свертка") либо какое именно из нескольких приведений должно быть выполнено (конфликт "свертка1свертка"). Ниже мы рассмотрим несколько примеров синтаксических конструкций, которые приводят к таким грамматикам.
Технически эти грамматики не принадлежат классу 1.К(й)-грамматик, определенному в разделе 4.7; будем говорить о них как о не-(.К-грамматиках. )с в (.К()с) указывает количество символов, которые предпросматриваются во входном потоке. Обычно используемые в компиляции грамматики принадлежат классу 1.К(1), т.е. выполняется предпросмотр не более одного символа. Пример 4.24. Неоднозначная грамматика не может принадлежать классу ЬК.
Рас- смотрим, например, грамматику с "висящим е!ае" (4.9) из раздела 4.3: х1т1 — !Г ехрг !Пеп ягт1 1!' ехрг !пеп а1т1 е!ае ягт1 оИзег Если ПС-анализатор находится в конфигурации Стек ВхОд е!ае .. 3 1!' ехрг гаев агт1 то мы не можем сказать, является ли 1! ехрг гпеп х1т1 основой, безотносительно к тому, что находится ниже его в стеке. Здесь мы сталкиваемся с конфликтом "перенос/свертка". В зависимости от того, что следует за е!ае во входном потоке, верным решением может оказаться свертка 1г" ехрг !Ьеп .птг в згтг или перенос е!ае и поиск еще одного егт1 для завершения альтернативы 1г" ехрг Феп хпи! е!ае агт1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
