Синтаксический анализ (стр. 2 )

Восходящий разбор с правосторонним выводом:

Грамматика:

шаг:

стек ®

ввод

1) S ® SaSb

cвертка 2

e

a

a

b

b

¾ правосторонний вывод ¾¾ ¾¾¾¾

2) S ® e

перенос (1)

S

a

a

b

b

свертка 2

S

a

e

a

b

b

перенос

S

a

S

a

b

b

свертка 2

S

a

S

a

e

b

b

перенос

S

a

S

a

S

b

b

свертка 1

S

a

S

a

S

b

b

перенос

S

a

S

b

свертка 1

S

a

S

b

допуск

S

основа ®

¾ актив. префикс ®

ост. ввод ввод

¾¾ ¾ сентенц. форма ¾¾¾®

(1) Данное состояние не является допускающим, так как ввод не пуст.

Узлы дерева разбора соответствуют прямоугольникам в стеке. Сыновья каждого сворачиваемого нетерминала находятся в стеке над ним и правее.

Нисходящий синтаксический разбор без возвратов

Метод рекурсивного спуска

Анализ методом рекурсивного спуска (resursive-descent parsing) – разновидность нисходящего синтаксического анализа, при котором для обработки входной цепочки выполняется ряд рекурсивных процедур. Каждому нетерминалу грамматики сопоставляется отдельная процедура, которая реализует разбор для всех продукций грамматики, имеющих этот нетерминал в левой части. Выбор между продукциями осуществляется по k очередным входным символам – k-предиктору. Требуемая однозначность выбора накладывает дополнительные ограничения на вид грамматики.

Построение рекурсивного анализатора для регулярной грамматики

Пусть задана детерминированная РГ. Для каждого нетерминала A выпишем серию всех продукций:

A ® a1B1 | a2B2 | … | akBk | b1 | b2 | … | bm

Детерминированность РГ означает, что внутри серии все терминалы ai и bj различны.

Теперь для каждого нетерминала построим по следующему шаблону процедуру разбора:

procedure ParseA; -- A ®a1B1|a2B2|...|akBk|b1|b2|...|bm

begin

select Scanner() of

{a1}: ParseB1;

{a2}: ParseB2;

...

{ak}: ParseBk;

{b1,b2,...,bm}: -- нет действий

else Error ("Ошибка разбора A");

end select;

end;

Альтернативы с одинаковыми Bi можно объединить, слив их направляющие множества {ai}. Корректность выбора обеспечивается непересечением направляющих множеств.

Функция Scanner сканирует очередную лексему во входном потоке и возвращает её токен. Процедура Error выдает ошибку и завершает исполнение программы. Эти действия должны программироваться отдельно.

Построение процедур разбора для РГ по указанной схеме может быть автоматизировано. Поэтому возможно создание универсального генератора синтаксических анализаторов для класса регулярных языков.

Работа рекурсивного РГ-анализатора

Вызов процедуры ParseS, соответствующей начальному нетерминалу грамматики, запускает нисходящий анализ методом рекурсивного спуска. Каждая процедура считывает очередной токен и либо выбирает подходящую продукцию и рекурсивно вызывает процедуру разбора для хвостового нетерминала, либо выдает ошибку, если подходящей продукции нет,

Динамическое дерево вызовов процедур ParseX в процессе разбора входной строки топологически совпадает с бинарным деревом разбора этой строки по РГ, разрастающемуся вглубь по правым ветвям.

Входная строка читается в процессе анализа строго слева направо, без заглядывания вперед и без возвратов. Таким образом, время работы анализатора линейно по длине входной цепочки.

Построение рекурсивного анализатора для КС-грамматики

КСГ имеет более общий вид продукций. Анализ методом рекурсивного спуска применим к ней с рядом ограничений.

Для каждого нетерминала A заданной КСГ выпишем серию всех продукций:

A ® a1 | a2 | … | an, где ai = Xi1 Xi2 … Ximi,

и построим процедуры, похожие на процедуры РГ-анализатора:

procedure ParseA; -- A ® a1|a2|...|an

begin

select LookAhead(k) of
Firstk(A®a1): Match(X11); Match(X12); ... ParseX1m1;

Firstk(A®a2): ParseX21; Match(X22); ... ParseX2m1;

...

Firstk(A®an): ParseXn1; ParseXn2; ... Match(Xnmn);

default: Error ("Ошибка разбора A");

end select;

end;

Каждая альтернатива выбора, как и прежде, отвечает за разбор по одной из продукций A ® ai . Её составляют вызовы процедур, последовательно распознающие символы Xij из правой части продукции. Если Xi – нетерминал, вызывается ParseXij; если Xij – терминал, вызывается cледующая процедура Match(Xij):

procedure Match (t: token);

begin

if t ¹ Scanner() then

Error ("Ожидается символ ", t);

end if;

end;

Для продукции A ® e с пустой основой последовательность действий пуста.

LookAhead – это функция, аналогичная Scanner, которая просматривает цепочку-предиктор, состоящую из k очередных входных лексем, но не сдвигает позицию ввода. Её можно реализовать с помощью буферизации cканера.

Чтобы выбор альтернатив работал корректно, направляющие множества (здесь они обозначены Firstk (A®ai) и состоят из цепочек длины не больше k), как и в РГ-анализаторе, не должны попарно пересекаться. Однако для КСГ общего вида это вызывает ряд трудностей:

–  для КСГ не запрещено, чтобы несколько ai начинались с одного и того же терминала или даже с одинаковой цепочки терминалов;

–  в КСГ первым символом цепочки ai может быть нетерминал.

Применение данного метода требует разрешения этих проблем каким-либо способом. Далее мы рассмотрим подкласс КСГ: LL(k)-грамматики, для продукций которых направляющие множества Firstk (A®ai) различаются и эффективно строятся.

Построение направляющих множеств и процедур разбора указанного вида для LL(k)-грамматик может быть автоматизировано. Поэтому для класса LL(k)-языков также возможно создание универсального генератора синтаксических анализаторов.

Особенность выбора по пустой цепочке

Некоторое (и, по условию непересечения, не более, чем одно) направляющее множество может содержать пустую цепочку e. Сравнение предиктора с пустой цепочкой считается успешным лишь в том случае, если он не совпадает ни с одной непустой цепочкой ни в одном направляющем множестве. По логике алгоритма в этом случае выбирается альтернатива отказа (default).

Если e не является допустимым значением предиктора, то отказ при сравнении с допустимыми непустыми цепочками равносилен неуспеху разбора: следует диагностировать ошибку и прервать разбор. Именно это предусмотрено в написанной выше схеме генерации.

Однако если e входит в некоторое направляющее множество, то отказ при сравнении не является ошибкой. В этом случае действия по разбору соответствующей продукции следует вписать в альтернативу отказа, а само множество из выбора исключить (его варианты при этом тоже попадут в отказные):

default: ParseXi1; ... ParseXimi; -- если e Î Firstk(A®ai)

Работа рекурсивного КСГ-анализатора

Запуск КСГ-анализатора производится вызовом процедуры ParseS, соответствующей начальному нетерминалу. Она (и также все остальные процедуры), сначала заглядывает вперед на k очередных лексем и на их основании выбирает продукцию или выдает ошибку, если подходящей продукции нет. Затем последовательно подтверждаются элементы правой части выбранной продукции, для чего вызываются рекурсивные процедуры ParseX для нетерминалов и процедура сравнения Match для терминалов.

Входная строка читается в процессе разбора слева направо, с заглядыванием вперед на k лексем. Буферизация сканера позволяет реализовать заглядывание без возвратов по входной строке. Таким образом, время работы анализатора линейно по длине входной цепочки.

Динамическое дерево вызовов процедур рекурсивного анализатора в процессе разбора топологически совпадает с бинарным деревом разбора по КСГ. Анализатор осуществляет левосторонний вывод входной цепочки: т. е., дерево вывода разрастается от корня вглубь путем развертки самого первого нетерминала в порядке левостороннего префиксного обхода дерева в глубину.

Сравнение схем КСГ - и РГ-анализаторов

Если применить схему построения КС-анализатора к РГ (как к частному случаю КСГ), то полученная программа будет немного отличаться от полученной по схеме построения РГ-анализатора. Для РГ направляющее множество продукции состоит из первого терминала в его правой части. В КСГ-схеме, первым действием всегда будет вызов Match от направляющего символа, нужный для фактического считывания k-предиктора. Это считывание можно убрать, заменив LookAhead на вызов сканера, что и сделано в РГ-схеме.

Дополнение рекурсивного КСГ-анализатора семантическими действиями

Построенную схему синтаксического анализа можно дополнить семантической нагрузкой: произвольными действиями, выполняемыми по ходу разбора. Порядок этих действий зависит от места размещения: так, действия, вписанные до самого первого вызова Match или ParseX в процедуре, будут выполняться в префиксном (прямом древесном) порядке, после самого последнего их вызова – в постфиксном (обратном древесном) порядке, а между ними – в одной из разновидностей инфиксного (внутреннего древесного) порядка.

В качестве примеров семантической нагрузки анализатора арифметического выражения рассмотрим четыре задачи и общие планы их решений.

1. Вычисление арифметического выражения

Преобразовать каждую процедуру разбора в функцию, возвращающую результатом значение подвыражения, соответствующего данному узлу дерева вывода. Лексемы-литералы и лексемы-идентификаторы порождают исходные значения (соответствующие листьям дерева вычислений). Операции в узлах дерева порождают промежуточные значения. Окончательное значение выдается результатом заглавной функции ParseS. Вычисления производятся в постфиксном порядке.

2. Построение явного представления структуры выражения

Описать структуру объекта данных для представления узла вычислений: литерального значения, идентификатора или операции, аргументы которой заданы ссылками на другие узлы. Преобразовать каждую процедуру разбора в функцию, возвращающую ссылку на динамический объект. Вписать в каждую процедуру действия по созданию объекта и заполнению его полей (создание узлов для объектов, порождаемых литералами, удобнее внести в процедуру Match). Заполнение полей объекта кодом операции и ссылками на аргументы в структуре узла выполнять по мере поступления лексем и данных от рекурсивных вызовов. Ссылка на построенное дерево вычислений выдается результатом заглавной функции ParseS. Создание объектов производится в префиксном порядке, заполнение – в инфиксном и постфиксном.

3. Контроль и преобразование типов в выражении

Для каждого объекта данных в выражении определить тип данных (1-, 2-, 4-байтовое знаковое или беззнаковое целое). Составить иерархию типов по включению. Ввести дополнительный атрибут в структуру объекта представления (задача 2): тип значения узла. Для терминальных объектов: тип идентификатора считается заданным в таблице имен, тип литерала определяется как минимальный тип, включающий заданное значение. Для операции тип результата определяется как минимальный тип, включающий типы аргументов. Если тип аргумента(-ов) не совпадает с типом результата, перед выполнением операции следует произвести преобразование аргумента, которое может быть рассмотрено как неявная унарная операция toType(x). Эти операции необходимо в явном виде встроить в дерево вычислений (для задачи 2) или включить в поток выходных команд (для задачи 4).