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