загрузка...
 
2. 7 Задачи анализа
Повернутись до змісту

2. 7 Задачи анализа

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

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

 G2=(T2, N2, P2, A), где

 T2  = {х, +, [, ]},

 N2 ={А,В},

 P2 = {А®х, А®[В], В®А, В®В+А}.

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

А? [В]? [А]? [[В]]? [[А]]? [[х]].

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

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

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

В ® А и В ® В+А.

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

При анализе сверху вниз основная проблема в определении необходимого правила V ® ai для построения следующего шага вывода цепочки w, когда в найденной части А ?* nVb известны левый нетерминальный символ V и n правил вывода V ® a1 , V ®a2, …V ® an с левой частью V. Решение этой проблемы, в частности, возможно с помощью алгоритма лексического <А(1) – анализа, который определяет необходимое правило V ® ai в зависимости от первого, еще не распознанного символа х в цепочке w.

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

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



загрузка...