Даны цепочка символов (слов) и грамматика. Нужно узнать, принадлежит ли это слово формальному языку, определяемому этой грамматикой. Для решения этой задачи обычно используются алгоритмы анализа слева направо, которые просматривают в этом направлении символы цепочки.
Например, цепочка [[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) – анализ в таком виде не используется. Тогда приходят к расширенным грамматикам или к синтаксическим диаграммам (графикам).