31 Мар 2013

Синтаксический анализ

31 Мар 2013

Синтаксический анализ (синтаксический разбор) — это процесс сопоставления линейной последовательности лексем языка (слов, токенов) с его формальной грамматикой. Результатом обычно является дерево разбора или абстрактное синтаксическое дерево. Для синтаксического разбора языков программирования используются контекстно-свободные грамматики. Это обоснованно тем, что грамматики более общих типов по иерархии Хомского (контекстно-зависимые и, тем более, естественные) гораздо труднее поддаются определённому анализу, а более простые (регулярные грамматики) не позволяют описывать вложенные конструкции языка и поэтому недостаточно выразительны.

Методы синтаксического разбора можно разбить на два больших класса в соответствии с порядком построения дерева разбора: восходящие и нисходящие. Нисходящие методы (методы сверху вниз) начинают с правила грамматики, определяющего конечную цель анализа с корня дерева синтаксического разбора и пытаются его наращивать, чтобы последующие узлы дерева соответствовали синтаксису анализируемого предложения. Восходящие методы (методы снизу вверх) начинают с конечных узлов дерева синтаксического разбора и пытаются объединить их построением узлов всё более и более высокого уровня до тех пор, пока не будет достигнут корень дерева.

Список источников