Карпов - Основы построения трансляторов (2005) (943926), страница 24
Текст из файла (страница 24)
Из вершины А в вершину В в графе направим ребро, помеченное и, если в грамматике есть продукция А — +аВ. По продукции вида В-+а грамматики б в графе проведем ребро, помеченное, а из вершины В в заключительную вершину.Е По продукции А-+е построим ребро из вершины А в заключительную вершину К помеченное я. Переход по этому ребру выполняется в том случае, если встретится символ, который помечает конец входной строки. Это может быть, например, символ ео~или символ 3. На рис. 5.1 представлен граф грамматики б;1.
Рис. 5.1. Граф грамматики 651 и ее синтаксическая диаграмма В общем случае. построение распознающего автомата по автоматной грамма- тике приводит к недетерминированному автомату. Однако известно, что по любому недетерминированному распознающему автомату может быть легко построен эквивалентный детерминированный автомат. На рис. 5.1 представлена также синтаксическая диаграмма этой автоматной грамматики — другая графическая форма представления распознающего автомата. Поскольку в каждом разветвлении этой синтаксической диаграммы все альтернативы помечены различными терминалами, ее можно использовать как схему процедуры распознавания языка, порождаемого грамматикой б; ~.
Легко видеть, что граф автоматной грамматики есть просто граф конечного автомата, распознающего этот язык. Состояниями конечного автомата, соответствующего грамматике, является множество нетерминалов грамматики и дополнительное состояние Е, метка которого не совпадает ни с одним нетерминалом грамматики. Начальным состоянием автомата является состояние Я, заключительным состоянием — состояние .Е В автомате из состояния А в состояние В есть переход под воздействием входного символа а, если А-+а — продукция грамматики.
Из состояния А в состояние Р' есть переход под воздействием символа а, если А-+а — продукция грамматики. Все переходы, помеченные символом пустой строки е, ведут в т из состояния А, если А — +е — продукция грамматики. Нисходящие методы синтаксического анализа 5.2. Синтаксический и семантический анализ автоматных языков 5.2.1. Синтаксический анализ при трансляции автоматных языков Вывод цепочки во всех автоматных грамматиках имеет одну и ту же структуру: промежуточные цепочки вывода имеют вид аД, где а — терминальная строка, а Д вЂ” единственный нетерминал.
На каждом шаге вывода терминальная цепочка увеличивается на один символ. Рассмотрим снова грамматику б;1. б»1. 5 — +аЯ ~ ЬА А — эаВ~ е В-+ЬА ~ а Пример вывода в этой грамматике: Я =:~ ЬА =:~ Ь~~В =:~ ЫЬА ==> Ь~Ь~~В ==> Ь~~Ь~~ЬА:=~ Ь~Ь~~Ь Деревья вывода в автоматных грамматиках тоже специфичны ~рис. 5.3). Рис. 5.3. Дерево вывода цепочки аааЬаЬ в грамматике 8~1 Синтаксический анализ состоит в восстановлении дерева вывода входной цепочки.
Для произвольной цепочки эта операция выполняется сверху вниз (рис. 5.4, а). Корень дерева помечается начальным символом Я; пара: <Л, а>, где А — очередной нетерминал в влекущем узле дерева вывода, а а — очередной символ анализируемой терминальной цепочки, должна определить не- терминал в следующем узле дерева — т. е. определить, какое правило под- 158 становки для очередного нетерминала применялось на очередном шаге вывода данной входной цепочки (рис. 5.4, 6). Если по исходной автоматной грамматике построен соответствующий детерминированный конечный автомат, то нетерминал, помечающий каждый следующий узел на синтаксическом дереве, совпадает с меткой состояния, в которое переходит автомат на очередном шаге под воздействием очередного символа входной цепочки, начиная с начального состояния, помеченного 5.
Рис. 6.4. а) Общая проблема синтаксического анализа; б) общая структура дерева вывода для автоматных грамматик Например, для грамматики 65 ~ вывод Я ==: ЬА ==:> ЬаВ ==> ЬаЬА ==> ЬаЬаЬА ==~ ЬаЬаЬ восстанавливается так. В выводе Я ==> .?. ==> ЬаЬаЬ искомые нетерминалы в концах промежуточных цепочек вывода (и, следовательно, в узлах синтаксического дерева) определяются по графу переходов соответствующего конечного автомата (см. рис. 5.1) как пометки в вершинах„в которые префикс входной цепочки привел автомат из начальной вершины 5. Первый шаг вывода: Я =-~ Ь'?'. На этом шаге очередным нетерминалом является Я„очередным терминалом — первый терминал входной цепочки Ь.
Эта пара приводит к очередному нетерминалу А, поскольку из состояния 5 автомат под воздействием Ь переходит в состояние А (или, что то же, для нетерминала 5 выбираем единственно возможную подстановку 5 — +ЬА, дающую Ь в качестве терминального префикса очередной сентенциальной формы). Второй шаг Я ==> ЬА ==> Ьа'Т вывода цепочки ЬаЬаЬ из 5 восстанавливается аналогично по очередному нетерминалу (состоянию) А и очередному входному символу (терминалу) а. Здесь знак вопроса заменяется на о. Завершение восстановления вывода очевидно. Нисходящие методы синтаксического анализа 5.2.2. Семантические операции при трансляции автоматных языков Стратегия синтаксически-ориентированной трансляции, которая рассматривалась в главе 3, состоит в следующем: семанпгические дейспгвия связываются с каждой продукцией ералгмапгггки, и как только пргг восспгановлении дерева вывода входной цепочки определяепгся, по какой продукции грамматики поспгроен очередной фрагмент синпгаксическоео дерева, выполняюпгся соопгвепгспгвугогцие эпгой ггродукцгггг се.чанпшческие действг~я.
При выборе семантических действий обычно учитывается стратегия построения дерева вывода — нисходящая она либо восходящая. Продукциям автоматной грамматики соответствуют переходы распознающего конечного автомата, поэтому семантические операции, сопоставленные продукциям автоматной грамматики, можно представить действиями на переходах конечного автомата.
При трансляции автоматных языков явное построение дерева вывода необязательно; в процессе распознавания входной цепочки при активизации каждого перехода распознающего конечного автомата выполняется семантическая операция, которая связывается с этим переходом автомата. Это именно та стратегия семантических вычислений, которая рассматривалась в лаве 3. Снова рассмотрим грамматику 05 !.' 3. А-+аВ 4. А — +е 5. В-+ЬА 6. В-+а В соответствии с концепцией синтаксически-ориентированной трансляции свяжем с каждой продукцией грамматики семантическую операцию: б~ !. 1. Я-+аЯ; у1 2. Я-+БА; у2 3. А — +аВ; у3 4. А — +е;у4 5  — +Му5 6.  — +а;у6 Для представления трансляторов автоматных языков удобно использовать либо граф переходов конечного автомата, либо синтаксическую диаграмму, 160 являющуюся фактически модификацией такого графа.
Необходимые для трансляции семантические действия включаются в граф переходов или в синтаксическую диаграмму рис. 5.1, как это показано для грамматики б; ~ на рис. 5.5 (заключительное состояние обозначено двойным кружком): Рис. 5.5. Синтаксическая диаграмма для грамматики 8~1 5.3. Примеры построения трансляторов автоматных языков 5.3Л.
Обработка потока телеграмм В качестве примера использования идей трансляции автоматных языков рассмотрим классическую задачу обработки потока телеграмм. Необходимо построить программу, принимающую на вход поток телеграмм и выдающую результаты обработки. Поток состоит из последовательности телеграмм, разделенных специальным разделителем Ф, весь поток заканчивается символом ео~ Каждая телеграмма состоит из последовательности слов, разделенных пробелами, слово — это произвольная последовательность букв. Требуемый выход состоит из печати для каждой телеграммы ее номера, числа слов, числа "длинных" слов (за них берется повышенная плата) и стоимости телеграммы, исходя из заданной стоимости одного обычного и одного длинного слова.
Аналогичную суммарную информацию требуется выдать по всему потоку телеграмм. Искомую программу можно представить как преобразователь„принимающий на вход последовательность телеграмм, а на выходе выдающий соответствующие характеристики этих телеграмм (рис. 5.6). Очевидно, что искомая программа обработки текстовой информации, которая принимает на вход цепочку символов — строку текста — и выдает некоторые результаты, может быть построена многими возможными способами. Одним из наиболее эффективных способов является построение этой программы как транслятора, реализующего преобразование вход = — ~ выход на основе синтак- Глава 5 Для построения транслятора этого языка достаточно включить на переходах распознающего автомата семантические правила, выполняющиеся по ходу распознавания. Таким образом, само синтаксическое дерево не строится в процессе трансляции, на каждом шаге распознавания выполняются именно те Рис. 5.?.
Грамматика в виде распознающего конечного автомата Рис. 5.8. Блок-схема распознавателя Рис. 5.9. Узлы синтаксического дерева Нисходящие методы синтаксического анализа семантические действия, которые соответствуют данному узлу семантического дерева. Семантические правила для этого транслятора построить очень просто. Пусть Ю вЂ” номер очередной телеграммы, к — число коротких слов в очередной телеграмме, И вЂ” число длинных слов, а К и Х) — эти же числа во всех прочитанных телеграммах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
