ВУЗ:
Составители:
49
щиеся в стеке нетерминальные символы и при сравнении ищет ближайший к
верхушке стека терминальный символ. Однако после выполнения сравнения и
определения границ основы при поиске правила в грамматике нетерминальные
символы следует, безусловно, принимать во внимание.
Алгоритм состоит из следующих шагов:
Шаг 1. Поместить в верхушку стека символ ⊥
H
, считывающий элемент – в
начало входной цепочки символов.
Шаг 2. Сравнить с помощью отношения предшествования терминальный
символ, ближайший к вершине стека (левый символ отношения), с текущим
символом входной цепочки, обозреваемым считывающим элементом (правый
символ отношения). При этом из стека надо выбрать самый верхний терми-
нальный символ, игнорируя все возможные нетерминальные символы.
Шаг 3. Если имеет место отношение <• или =•, то произвести сдвиг (пере-
нос текущего символа из входной цепочки в стек и сдвиг считывающего эле-
мента на один шаг вправо) и вернуться к шагу 2. Иначе перейти к шагу 4.
Шаг 4. Если имеет место отношение •>, то произвести свертку. Для этого
надо найти на вершине стека все терминальные символы, связанные отношени-
ем =• («основу»), а также все соседствующие с ними нетерминальные символы
(при определении отношения нетерминальные символы игнорируются). Если
терминальных символов, связанных отношением =•, на верхушке стека нет, то в
качестве основы используется один, самый верхний в стеке терминальный сим-
вол стека. Все (и терминальные, и нетерминальные) символы, составляющие
основу, надо удалить из стека, а затем выбрать из грамматики правило, имею-
щее правую часть, совпадающую с основой, и поместить в стек левую часть
выбранного правила. Если правило, совпадающее с основой, найти не удалось,
то необходимо прервать выполнение алгоритма и сообщить об ошибке, иначе,
если разбор не закончен, то вернуться к шагу 2.
Шаг 5. Если не установлено ни одно отношение предшествования между
текущим символом входной цепочки и самым верхним терминальным симво-
лом в стеке, то надо прервать выполнение алгоритма и сообщить об ошибке.
Общий алгоритм работы синтаксического анализатора
Синтаксический анализатор работает, опираясь на построенную матрицу
предшествования. На его вход поступает обработанный сканером текст исход-
ной программы. Каждый идентификатор или константа представляются для не-
го некоторым терминальным символом. Тогда 1-й шаг общего алгоритма ана-
лиза – построение таблицы лексем. По таблице лексем и матрице предшество-
вания выполняется разбор цепочки. Результатом разбора является проверка це-
почки на синтаксическую правильность и для правильных цепочек – построе-
ние последовательности правил вывода (для неправильных цепочек выдается
сообщение об ошибке). Получение последовательности правил – 2-й шаг обще-
го алгоритма анализа.
На 3-м шаге по последовательности правил легко строится цепочка вывода
и дерево синтаксического разбора. Дерево строится сверху вниз путем последо-
вательного применения правил. При построении дерева следует учитывать, что
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
