└─┬───┬─┘ │ └─┬───┬─┘ │ └─┬───┬─┘ │
│ └────┘ nil └────┘ │ └───>┘
┌─┴─────┐ ┌─┴─────┐
│ a │ │ ) │
└─┬───┬─┘ └─┬───┬─┘
│ nil nil nil
┌─┴─────┐
│ b │
└─┬───┬─┘
│ nil
┌─┴─────┐
│ c │
└─┬───┬─┘
nil nil
Рис. 14. Многосвязная структура конструкции "Выражение"
ш0
Приведем набросок процедуры анализатора [3]. Будем счи-
тать, что при вызове анализатора через процедуру Getsym уже
прочитан первый символ анализируемой строки:
procedure Parse(goal:hptr; var match : boolean);
{ match - результат анализа (дословно: равняться, подходить)}
var s : ref;
begin
s:=goal^.entry;
repeat
if s^.terminal then
if s^.tsym=sym then
begin
match:=true;
Getsym
end
else
match:=(s^.tsym=empty)
else
Parse (s^.nsym, match);
if match then
s:=s^.suc
- 53 -
else
s:=s^.alt
until s=nil
end
Можно сказать, что описанная выше многосвязная структура
по существу таблично задает исходный язык, поэтому анализатор
и называется таблично управляемым.
28. ВОСХОДЯЩИЕ МЕТОДЫ АНАЛИЗА
28.1. LR - грамматики
Синтаксический анализ предложения языка может выполняться
по принципу снизу вверх, а именно: предложение читается анали-
затором до тех пор, пока не появится возможность отождествить
часть прочитанной цепочки с правой частью какого-либо правила
вывода [11]. Тогда выполняется свертка этой цепочки с заменой
ее на нетерминал левой части. Далее анализ продолжается до тех
пор, пока входная цепочка не будет исчерпана. В стеке к этому
времени должен находиться начальный символ грамматики.
Рассмотрим идею восходящего анализа подробнее на следующем
примере. Некоторые тонкости будут обсуждаться дополнительно.
2Пример. 0 Пусть задана следующая КС-грамматика:
1) S -> real Idlist
2) Idlist -> Idlist, Id
3) Idlist -> Id
4) Id -> a │ b │ c │ d
Здесь большими буквами выделены нетерминальные символы, а
с малой буквы начинаются терминалы. Будем считать, что у нас
имеется сканер, который читает из входной цепочки терминальные
символы предложения. Пусть на вход подается следующее предло-
жение: "real a, b,c". Для работы анализатора потребуется стек,
где будет храниться будущая правая часть правила вывода. В
таблице 3 приведен пример анализа (в последнем столбце указы-
вается выполняемая операция: или сдвиг символа в стек, или
свертка подцепочки к нетерминалу).
.
- 54 -
ш1
2Таблица 3
2Пример восходящего разбора
┌─────┬────────┬────────┬──────────────────────┐
│номер│читаемый│операция│содержимое стека после│
│шага │символ │ │выполнения операции │
├─────┼────────┼────────┼──────────────────────┤
│ 1 │real │сдвиг │real │
│ 2 │a │сдвиг │real a │
│ 3 │ │свертка │real Id │
│ 4 │ │свертка │real Idlist │
│ 5 │, │сдвиг │real Idlist, │
│ 6 │b │сдвиг │real Idlist, b │
│ 7 │ │свертка │real Idlist, Id │
│ 8 │ │свертка │real Idlist │
│ 9 │, │сдвиг │real Idlist, │
│ 10 │c │сдвиг │real Idlist, c │
│ 11 │ │свертка │real Idlist, Id │
│ 12 │ │свертка │real Idlist │
│ 13 │ │свертка │S │
└─────┴────────┴────────┴──────────────────────┘
ш0
Наш разбор считается успешным, так как в стеке располага-
ется только начальный символ и входная цепочка исчерпана.
Итак, в процессе анализа мы применяли два типа действий:
сдвиг и свертка (приведение). При этом выбор действия нами ни-
как не комментировался. А, желательно, чтобы на каждом шаге
однозначно определялось нужное действие. Далее при выполнении
свертки может оказаться, что это действие возможно по несколь-
ким сразу правилам вывода. Последнее означало бы, что придется
организовывать перебор различных вариантов свертки при попада-
нии в тупик.
2Определение. 0 Грамматики, допускающие безвозвратный анализ
по принципу снизу вверх при "заглядывании" на k символов впе-
ред (слева направо), называются LR(k)-грамматиками.
В обозначении LR первая буква L обозначает, что разбирае-
мое предложение читается слева направо. Вторая буква R обозна-
чает, что строится правосторонний разбор. Позже будет показа-
но, что определение LR-грамматик, так же как и LL-грамматик
связано с определенными ограничениями. В случае LR-грамматик
это ограничение касается однозначности каждой клетки специаль-
ной таблицы разбора.
На практике чаще всего рассматривают LR(0)- и LR(1)-грам-
матики. На самом деле, справедливо следующее утверждение.
2Теорема. 0Если некоторый язык относится к классу
LR(k)-языков при некотором k (то есть существует порождающая
- 55 -
его LR(k)-грамматика), то он является LR(k)-языком с любым
значением k (k>=0), в том числе и при k=0 и k=1.
Упомянем еще один интересный теоретический результат.
Если некоторый язык может быть разобран детерминированно, то
он относится к классу LR-языков. Например, любой LL(1)-язык
является LR-языком. Действительно, принятие решения в LR-ана-
лизаторе откладывается до полного прочтения правой части пра-
вила вывода, в то время как для LL(1)-языка гарантирован выбор
правила вывода уже по одному символу. Следовательно, в LR-раз-
боре информации уж никак не меньше.
В заключение перечислим достоинства LR-грамматик.
1) По заданной грамматике можно определить, является ли
она LR-грамматикой (так же как и для LL-грамматик).
2) Для LR-анализатора гораздо реже приходится преобразо-
вывать исходную грамматику (по сравнению с LL-анализатором).
28.2. LR-таблицы разбора
На практике LR-анализатор обычно выполняет разбор, руко-
водствуясь специальной управляющей таблицей. В этой таблице
для каждого возможного состояния анализатора и каждого очеред-
ного входного символа (терминального или нетерминального!)
предусмотрено необходимое действие, задающее сдвиг и новое
состояние или свертку по некоторому правилу. В первом случае
будем записывать в клетке таблицы сочетание "Sn", где S - опе-
рация сдвига, а n - номер нового состояние анализатора. Во
втором случае будем указывать сочетание "Rn", где R - операция
свертки (приведения), а n - указание номера правила, по кото-
рому осуществляется свертка.
Анализатор будет использовать два стека. Первый - для
хранения формируемой правой части какого-либо правила вывода,
а второй - для хранения состояний. Текущим состоянием анализа-
тора является верхнее значение в стеке состояний. Условимся,
что начальное состояние равно 1.
При выполнении операции сдвига анализатор помещает в стек
символов очередной символ и переходит в новое состояние, кото-
рое записывается также в стек состояний.
.
- 56 -
При выполнении операции свертки определяется длина правой
части правила вывода (обозначим эту длину через l) и из каждо-
го стека удаляется по l элементов. Нетерминал левой части пра-
вила вывода, по которому осуществлялась свертка, становится
текущим входным символом. Обратите внимание: символ, который
вызвал свертку, не считается обработанным и возвращается об-
ратно во входную строку!
2Упражнение. 0Докажите, что нетерминальный символ, появив-
шийся после свертки, на следующем шаге будет помещен в стек.
2Пример. 0В таблице 4 приводится пример LR-таблицы для
грамматики из предыдущего примера. Символ "#" является марке-
ром конца входной цепочки. Незаполненные клетки таблицы соот-
ветствуют ошибочным ситуациям. В клетке 1/S указано слово
"halt", обозначающее конец работы анализатора.
2Пример. 0 Рассмотрим работу анализатора по таблице из пре-
дыдущего примера. Пусть на вход подается цепочка "real
a, b,c#". Первоначально стек символов пуст, в стеке состояний
записано начальное состояние 1. В таблице 5 приводится пример
трассировки алгоритма LR-разбора.
ш1
2Таблица 4
2Пример управляющей таблицы LR-анализатора
┌──────────┬─────┬──────┬─────┬──────┬───────┬───────┬─────┐
│\ Символ │ │ │ │ │ │ a b │ │
│ ──────── │ S │Idlist│ Id │ real │ , │ c d │ # │
│Состояние\│ │ │ │ │ │ │ │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 1 │halt │ │ │ S2 │ │ │ │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 2 │ │ S5 │ S4 │ │ │ S3 │ │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 3 │ │ │ │ │ R4 │ │ R4 │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 4 │ │ │ │ │ R3 │ │ R3 │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 5 │ │ │ │ │ S6 │ │ R1 │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 6 │ │ │ S7 │ │ │ S3 │ │
├──────────┼─────┼──────┼─────┼──────┼───────┼───────┼─────┤
│ 7 │ │ │ │ │ R2 │ │ R2 │
└──────────┴─────┴──────┴─────┴──────┴───────┴───────┴─────┘
ш0
В приложении 1 приведен пример программы, реализующей
анализ по LR-таблице.
.
- 57 -
ш1
2Таблица 5
2Пример трассировки алгоритма LR-разбора
┌───────┬──────┬────────┬────────────────────────────────────┐
│Очеред.│Текущ.│Выполня-│Содержимое после выполнения действия│
│символ │состо-│емое ├─────────────────┬──────────────────┤
│ │яние │действие│ стека символов │ стека состояний │
├───────┼──────┼────────┼─────────────────┼──────────────────┤
│ │ │ │стек пуст │ 1 │
│ real │ 1 │ S2 │real │ 1 2 │
│ a │ 2 │ S3 │real a │ 1 2 3 │
│ , │ 3 │ R4 │real │ 1 2 │
│ Id │ 2 │ S4 │real Id │ 1 2 4 │
│ , │ 4 │ R3 │real │ 1 2 │
│ Idlist│ 2 │ S5 │real Idlist │ 1 2 5 │
│ , │ 5 │ S6 │real Idlist, │ │
│ b │ 6 │ S3 │real Idlist, b │ │
│ , │ 3 │ R4 │real Idlist, │ │
│ Id │ 6 │ S7 │real Idlist, Id │ │
│ , │ 7 │ R2 │real │ 1 2 │
│ Idlist│ 2 │ S5 │real Idlist │ 1 2 5 │
│ , │ 5 │ S6 │real Idlist, │ │
│ c │ 6 │ S3 │real Idlist, c │ │
│ # │ 3 │ R4 │real Idlist, │ │
│ Id │ 6 │ S7 │real Idlist, Id │ │
│ # │ 7 │ R2 │real │ 1 2 │
│ Idlist│ 2 │ S5 │real Idlist │ 1 2 5 │
│ # │ 5 │ R1 │стек пуст │ 1 │
│ S │ halt │ │ │ │
└───────┴──────┴────────┴─────────────────┴──────────────────┘
ш0
28.3. Грамматики простого предшествования
К числу восходящих методов разбора относится анализ по
таблице предшествования для грамматики называемых грамматиками
предшествования [8]. Рассмотрим такие грамматики.
Прежде всего определим на множестве терминальных и нетер-
минальных символов отношения предшествования. Используемые ни-
же символы R и S берутся из такого множества.
2Определение 1. 0 Два символа находятся в отношении не-
посредственного следования, если они непосредственно следуют
друг за другом в правой части какого-либо правила вывода грам-
матики. Через R=.S будем обозначать отношение непосредственно-
го следования символа S за символом R. Здесь символы R и S мо-
гут быть как терминальными, так и нетерминальными в любой ком-
бинации.
2Определение 2. 0 Символ R находится в отношении не-
посредственного предшествования к символу S, если существует
- 58 -
нетерминальный символ G, такой что R=.G и из G выводима цепоч-
ка, начинающаяся с S (обозначение: R<.S). Здесь символы R и S
также могут быть как терминальными, так и нетерминальными.
2Определение 3а. 0 Терминальный символ R находится в отноше-
нии непосредственного послеследования к символу S (терминаль-
ному или нетерминальному), если существует нетерминальный сим-
вол G, такой что G=.R и из G выводима цепочка, заканчивающаяся
символом S (обозначение: S.>R).
2Определение 3б. 0 Терминальный символ R находится в отноше-
нии непосредственного послеследования к символу S (терминаль-
ному или нетерминальному), если существуют нетерминальные сим-
волы G и Q, такие что G=.Q и из G выводима цепочка, заканчива-
ющаяся символом S, а из Q выводима цепочка, начинающаяся с
символа R (обозначение такое же: S.>R).
2Пример. 0 Рассмотрим следующую грамматику:
1) S -> bMb 2) M -> (L 3) M -> a 4) L -> Ma)
Подумайте, какой язык порождается этой грамматикой? Ниже
в таблице 6 приводятся отношения предшествования для объеди-
ненного алфавита терминальных и нетерминальных символов.
ш1
2Таблица 6
2Пример таблицы предшествования
┌──────────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│\Второй символ│ │ │ │ │ │ │ │
│ ──────────── │ S │ M │ L │ a │ b │ ( │ ) │
│Первый символ\│ │ │ │ │ │ │ │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ S │ │ │ │ │ │ │ │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ M │ │ │ │ =. │ =. │ │ │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ L │ │ │ │ .> │ .> │ │ │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ a │ │ │ │ .> │ .> │ │ =. │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ b │ │ =. │ │ <. │ │ <. │ │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ ( │ │ <. │ =. │ <. │ │ <. │ │
├──────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│ ) │ │ │ │ .> │ .> │ │ │
└──────────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
ш0
2Определение 4. 0 Грамматика называется грамматикой простого
предшествования, если в ней нет правил вывода с одинаковыми
правыми частями и для каждой пары символов определено не более
одного отношения предшествования.
- 59 -
Грамматика из предыдущего примера является грамматикой
простого предшествования (см. таблицу 6).
28.4. Анализатор предшествования
Рассмотрим алгоритм анализа входной цепочки по некоторой
таблице предшествования. Дополним множество терминальных сим-
волов терминальным символом "#". Будем считать, что для любого
символа R верны отношения предшествования: R.># и #<.R.
Для анализа (как и всегда при восходящем разборе) нам
потребуется стек, где будет накапливаться будущая правая часть
правила вывода. При анализе очередного символа по таблице
предшествования определяется, в каком отношении находятся
верхний символ стека и очередной входной символ.
Если символы находятся в отношении непосредственного сле-
дования, то входной символ записывается в стек.
Если символы находятся в отношении непосредственного
предшествования, то в стек записывается и знак предшествова-
ния, и входной символ.
Если символы находятся в отношении непосредственного
послеследования, то производится свертка в стеке правой части
правила вывода (выделенной самым верхним отношением в стеке из
всех отношений непосредственного предшествования). Очередным
входным символом становится нетерминал левой части свернутого
правила. Если же свертка невозможна (то есть не существует
правой части правила вывода, совпадающей с выделенной цепоч-
кой), то значит обнаружена ошибка.
Если обнаружится, что для текущих символов отношение
предшествования неопределено, то значит обнаружена ошибка.
Анализатор заканчивает работу успешно, если входная це-
почка исчерпана, а в стеке находится начальный символ грамма-
тики.
2Пример. 0 Рассмотрим работу анализатора по предыдущей таб-
лице предшествования. Пусть на вход подается цепочка
"b(aa)b#". Первоначально в стек записывается маркер конца. Ни-
же в таблице 7 приводится пример работы анализатора.
.
- 60 -
ш1
2Таблица 7
2Пример работы анализатора предшествования
┌──────────────────┬────────────┬─────────────────────────┐
│ Оставшаяся часть │ Отношение │ Содержимое стека после │
│ входной цепочки │ предшеств. │ выполнения действия │
├──────────────────┼────────────┼─────────────────────────┤
│ │ │ # │
├──────────────────┼────────────┼─────────────────────────┤
│ b ( a a ) b # │ <. │ # <. b │
├──────────────────┼────────────┼─────────────────────────┤
│ ( a a ) b # │ <. │ # <. b <. ( │
├──────────────────┼────────────┼─────────────────────────┤
│ a a ) b # │ <. │ # <. b <. ( <. a │
├──────────────────┼────────────┼─────────────────────────┤
│ a ) b # │ .> │ # <. b <. ( │
├──────────────────┼────────────┼─────────────────────────┤
│ M a ) b # │ <. │ # <. b <. ( <. M │
├──────────────────┼────────────┼─────────────────────────┤
│ a ) b # │ =. │ # <. b <. ( <. M a │
├──────────────────┼────────────┼─────────────────────────┤
│ ) b # │ =. │ # <. b <. ( <. M a ) │
├──────────────────┼────────────┼─────────────────────────┤
│ b # │ .> │ # <. b <. ( │
├──────────────────┼────────────┼─────────────────────────┤
│ L b # │ =. │ # <. b <. ( L │
│ M b # │ =. │ # <. b M │
├──────────────────┼────────────┼─────────────────────────┤
│ b # │ =. │ # <. b M b │
├──────────────────┼────────────┼─────────────────────────┤
│ # │ .> │ # │
├──────────────────┼────────────┼─────────────────────────┤
│ S # │ <. │ # <. S │
├──────────────────┼────────────┼─────────────────────────┤
│ # │ .> │ Анализ завершен успешно │
└──────────────────┴────────────┴─────────────────────────┘
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
