Карпов - Основы построения трансляторов (2005) (943926), страница 32
Текст из файла (страница 32)
Простейший алгоритм "грубой силы", пытающийся решить эту задачу простым перебором, ищет очередную связку проверкой на совпадение правых частей всех продукций грамматики и подстрок сентенциальной формы. Этот алгоритм не использует никакой информации, кроме информации о простом вхождении символов в септенциальную форму, и оказывается очень неэффективным. В 70-е годы прошлого века были разработаны методы, позволяющие выполнить восходящий синтаксический анализ с более полным учетом информации, содержащейся во входной цепочке.
В этой главе мы рассмотрим два метода выделения самой левой связки в сентенциальной форме: метод отношений предшествования и метод, основанный на использовании всей информации, содержащейся во входной цепочке до искомой связки, и 1 символов, идущих после связки. Этот последний метод лежит в основе очень эффективной технологии синтаксического анализа, которая используется для анализа широкого класса недв)смысленных КС-грамматик. Этот класс называется классом 1.К~ф)-грамматик. Восходящие алгоритмы синтаксического анализа 209 целью — поиска в ней самой левой связки для свертки этой связки к соответствующему нетерминалу. В нашем примере в полученной на предыдущем шаге сентенциальной форме аАЬссй связкой является подцепочка АЬс, и, следовательно, восходящий синтаксический анализатор должен по сентенциальной форме аАЬссй и грамматике 6~ ~ получить новую сентенциальную форму аАНе, выполнив свертку А ."== АЬс.
В конце концов восходящий синтаксический анализатор по исходной цепочке аЬЬссй и грамматике б~, ~ построит следующую последовательность сентен- циальных форм: аЬЬсй ~ аАЬс~де ==: а.йе — аАВе ==> 5 получив в конце концов начальный символ Я грамматики. На рис. б.1, О пока- зана эта последовательность. В каждой сентенциальной форме выделена связка„которую должен найти алгоритм синтаксического анализа на каждом шаге. Конечно, эта последовательность есть не что иное, как восстановленный пра- вый канонический вывод исходной цепочки в грамматике б~|.
Действитель- но, этот вывод имеет вид: 5 ==> аАВе ==> иАс1е ==> аАЬсс1е ==> аЬЬсде Из рис. 6.1 можно видеть, что получаемая в результате восходящего синтаксического анализа последовательность сентенциальных форм вполне достаточна, чтобы по ней построить дерево вывода исходной цепочки. Однако при трансляции построение всего дерева обычно не нужно, если с каждой выполняемой сверткой алгоритм синтаксического анализа может выполнить и необходимые для трансляции семантические действия, связанные с правилом грамматики, в соответствии с которым выполняется данная свертка. 6.2.
Грамматики простого предшествования При поиске связки в сентенциальной форме достаточно найти ее границы и тот нетерминал, к которому сворачивается эта связка. Для грамматик, у которых правые части всех продукций различны, по виду связки можно одно- и он полностью совпадает с восстановленной последовательностью. Очевидно, что если сентенциальная форма просматривается слева в поиске самой левой связки при восходящем синтаксическом анализе, то и восстанавливаться в ней сначала будут самые левые нетерминалы, а это характеризует такой вывод, когда в сентенциальных формах подстановка правой части продукций осуществляется для самого правого нетерминала, что как раз соответствует правому каноническому выводу.
Всегда восходящий метод синтаксического анализа„который находит самую левую связку, восстанавливает именно правый канонический вывод входной цепочки. Восходящие алгоритмы синтаксического анализа 2. Я-+а Т 3. 5 — +~Я 4. Т вЂ” эЬ 5. Т вЂ” ьбТ и вывод в ней: У' ~ №,~№ ==> №И№ => №[аЛ№ ~ №ИЛ№ => №ИИ№ Рассмотрим сентенциальную форму №~аЬТ~№. Поскольку №~аЬТ~№ может быть свернута к предыдущей сентенциальной форме №~аТ~№ в этом конкретном выводе с восстановлением Т вместо оТ в соответствии с продукцией Т-+И; то в этом конкретном примере вывода можно увидеть, что должны существовать следующие отношения предшествования (кроме прочих): и< Ь, оАТи Т >~. Такие отношения, конечно, нельзя найти анализом всех возможных выводов: таких выводов бесконечно много.
Поставим вопрос: можно ли их определить непосредственно из грамматики? Бинарные отношения, которые нас интересуют, должны для произвольных двух символов грамматики Х и К которые могут встретиться рядом при синтаксическом анализе в произвольной сентенциальной форме, дать ответ на три вопроса (см. рис. 6.1): 1. Может ли после символа Х начаться какая-нибудь связка, первым символом которой является У(отношение '<")? 2. Могут ли символы Х и У встретиться рядом в одной связке (отноше- ние 'А')? 3. Может ли перед символом У кончиться какая-нибудь связка с последним символом Х(отношение ">')? Самое простое — ответить на вопрос 2. Два символа могут встретиться рядом в одной связке, если существует правая часть какой-либо продукции грамматики, в которой эти два символа стоят рядом.
Для грамматики б~ ~ это всего 6 пар: Я№, Я, (5„№), (а, Т), Я, Я), (5', ~), (о, Т)~, что очевидно из правых частей продукций ~У вЂ” +№Л№, К вЂ” +а, К вЂ” ьаТ, Я вЂ” +~Я, Т вЂ” +6, Т вЂ” +ЬТ~. Итак, №='5, Ы№, а — Т, ~АЯ, 5А~, оАТ. Таким образом, не перебирая все возможные выводы, мы получили прямо из продукций грамматики множество всех пар символов, которые во всех выводах могут стоять рядом и одновременно сворачиваться в одной связке! Ответ на вопрос 1 чуть более сложен. Отношение '<" выполняется для пары (Х, У), если с У начнется цепочка, которая должна быть свернута к некоторому нетерминалу М, который может после свертки оказаться рядом с Х, и по- Глава б том (обязательно!) когда-нибудь свернуться вместе с Х при дальнейшем анализе. Следовательно, этот новый нетерминал Мобязательно будет стоять рядом с Х в правой части какой-нибудь продукции грамматики.
Формально: Х< Утогда и только тогда, когда (ЗА-+иХЛфеЯ): М==>' Уу . Для нахождения отношения '<" в нашей грамматике 6~ ~ выпишем все соседние пары в продукциях, у которых второй элемент — нетерминал (к которому могут быть свернуты какие-нибудь подцепочки). Это всего 4 пары: Я4, 5), (а, Т), (~, 5), (о, Т)~. Поскольку Я ==> а, Я ==> аТ, и Я ==> Я, то отношение '<" будет между символами д и ~, стоящими перед Я в продукциях грамматики, и символами а и ~ (с которых могут начинаться цепочки, выводимые из Я): т. е.
6< а, Ф< [, ~< а, ~< ~. Кроме того, это же отношение будет между символами а и 0 (стоящими перед Т в продукциях грамматики) и символом о (с которого могут начинаться цепочки, выводимые из Т): а< О, Ь <.О. Опять, не перебирая все возможные выводы, мы получили прямо из продукций грамматики множество всех пар символов, которые во всех выводах могут стоять рядом, и первый из них может сворачиваться позже второго! Рассмотрим, наконец, отношение ">', Его тоже можно определить из продукций грамматики: отношение ">' выполняется для пары символов (Х, У), если символом Х кончается цепочка, которая должна быть свернута к некоторому нетерминалу М, который либо может стоять рядом с У'в каком-нибудь правиле грамматики, либо же М может стоять рядом с некоторым 7, из которого выводятся цепочки, начинающиеся с К При просмотре цепочек слева направо клеще не может быть свернуто к нетерминалу в составе какой-нибудь продукции и всегда является терминалом.
Более формально: Х >Утогда и только тогда, когда (ЗА — >аЛЖ~3яА): М=э'уХ, У вЂ” — >* УЗ, Гя Т. Символ ==~* говорит о том, что Ю может быть выведена из У за произвольное число шагов вывода, в том числе и О, т. е. как частный случай допускается и 2 = У в том случае, если У вЂ” терминал, а М=~ уХ, имеет тот смысл, что из М может за произвольное число шагов вывода, большее О, получиться некоторая цепочка, заканчивающаяся символом Х. Для нахождения таких пар в нашей грамматике б~ ~ выпишем все соседние пары в продукциях, у которых первый элемент — нетерминал.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
