Синтаксические диаграммы. Дана цепочка символов (слов) и грамматика

Задачи анализа

Лекция 2

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

Например, цепочка [[x]] принадлежит языку L(G₂), описанному грамматикой G₂.

G₂=(T₂, N₂, P₂, A), где

T₂ = {х, +, [, ]}

N₂ ={А,В}

P₂ = {А®х, А®[В], В®А, В®В+А}

Действительно, заданную цепочку можно получить, применив последовательно по одному из правил вывода, заданного в Р₂.

АÞ [В]Þ [А]Þ [[В]]Þ [[А]]Þ [[х]]

Следовательно, цепочка [[х]] принадлежит формальному языку L(G₂).

Различают две стратегии: стратегия анализа сверху вниз и снизу вверх. При анализе сверху вниз для построения вывода заданной цепочки начинают с ГЛАВНОГО нетерминального символа и выбирают правила из заданного множества так, чтобы прийти к заданной цепочке w.

В примере [[х]] в грамматике G₂ главный нетерминальный символ А. Среди заданного множества правил вывода для А есть два: А ® х и А ® [В]. Первое из них не дает возможности вывести [[х]]. Берем А ® [В], то есть А заменяем на [В]. Теперь нужно выбирать из двух правил вывода для В.

В ® А и В ® В+А.

Выбираем В ® А, заменяем в [В] В на А и получаем [А]. Вновь из двух правил вывода для А выбираем А ® [В]. Заменяем в [А] А на [В]. Получаем [[В]]. Вновь из двух правил для вывода В выбираем В ® А и заменяем в [[В]] В на А. Получим [[А]]. И, наконец, из двух правил вывода для А выбираем А ® х. Заменяем в [[А]] А на х и получаем требуемую цепочку [[х]]. Таким образом, доказано, что заданная цепочка действительно принадлежит языку, определяемому грамматикой G₂.

При анализе сверху вниз основная проблема в определении необходимого правила V ® a_i для построения следующего шага вывода цепочки w, когда в найденной части А Þ* nVb известны левый нетерминальный символ V и n правил вывода V ® a₁, V ®a₂, …V ® a_n с левой частью V. Решение этой проблемы, в частности, возможно с помощью алгоритма LА(1) – анализа, который определяет необходимое правило V ® a_i в зависимости от первого еще не распознанного символа х в цепочке w.

Осуществляется LA(1) – анализ путем создания для нетерминалов процедур анализа. Эти процедуры, как правило, оказываются взаимно рекурсивными и часто неэффективными.

Для многих грамматик LA(1) – анализ в таком виде не используется. Тогда приходят к расширенным грамматикам или к синтаксическим диаграммам (графикам).

Это ориентированный граф с двумя фиксированными вершинами: входной, из которой дуги только выходят, и выходной, в которую дуги только входят.

Дуги этого графа могут быть помечены терминальными и нетерминальными символами. В расширенной диаграмме с терминальным Т и нетерминальным N алфавитами каждому нетерминалу А и его правилу вывода А ® a, где a - регулярное выражение в алфавите T U N, отвечает одна синтаксическая диаграмма. При обозначении дуг, помеченных терминальными символами, условились эти символы писать строчными буквами и заключать в окружность.

Нетерминальные символы условились писать заглавными буквами и размещать в прямоугольнике.

Регулярное выражение будет обозначаться греческими буквами внутри ромба.

На рисунке показаны примеры изображения дуг, помеченных терминальным символом а, нетерминальным А и регулярным выражением a.

Рисунок 1

Алгоритм LА(1) – анализа может быть применен при условиях, что в синтаксических диаграммах нет непомеченных дуг от входной вершины к выходной и в каждом разветвлении ветки начинаются с неодинаковых последующих терминальных символов.

По синтаксической диаграмме строится функция анализа выводимых из нетерминала цепочек символов.

Прохождению дуги, помеченной терминальным символом а, отвечает распознавание этого символа (т.е. а) в предъявленном для анализа слове и сдвиг на следующий символ в этом слове (чтение очередного символа из слова).

Прохождению дуги, помеченной нетерминальным символом А, отвечает вызов функции распознавания цепочек, которые выводятся из А. Перед вызовом этой функции предварительно должен быть прочитан первый терминальный символ х, который выводят из А, т.е. АÞ* х…Функция успешно анализирует цепочку w, выводимую из нетерминала А, если в соответствии с синтаксической диаграммой, прочитав посимвольно всю цепочку w, удается попасть из входной вершины в выходную.

Дата добавления: 2015-06-27