Курс Основы построения трансляторов


Методы и алгоритмы синтаксического анализа


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

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

при восходящем синтаксическом разборе в предложении (или в промежуточной цепочке) ищется правая часть правила, которое необходимо “свернуть” к нетерминалу левой части. Решение принимается на основе анализа соседних терминальных символов в анализируемой цепочке.

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




Начало  Назад  Вперед