Грамматический анализ

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

Дерево разбора. Другие названия: дерево вывода, derivation tree (DT), parse tree (PT).
Результат грамматического анализа. Дерево разбора отличается от абстрактного синтаксического дерева наличием узлов для тех синтаксических правил, которые не влияют на семантику программы. Классическим примером таких узлов являются группирующие скобки, в то время как в AST группировка операндов явно задаётся структурой дерева.
В развиваемой нашей компанией открытой библиотеке VivaCore происходит построение именно дерева разбора Си/Си++ кода. Это позволяет получать некоторую дополнительную информацию, которая используется статическими анализаторами кода входящих в PVS-Studio.

Абстрактное синтаксическое дерево. Другие названия: дерево Канторовича, Abstract Syntax Tree (AST), АСД. Абстрактное синтаксическое дерево это конечное, помеченное, ориентированное дерево, в котором внутренние вершины сопоставлены с операторами языка программирования, а листья с соответствующими операндами. Таким образом, листья являются пустыми операторами и представляют только переменные и константы. АСД отличается от дерева разбора тем, что сохраняет только существенную информацию о программе, тогда как дерево разбора, напротив, - много избыточной информации. В этом смысле абстрактное синтаксическое дерево является конденсированной формой дерева разбора, удобной для представления структуры языковых конструкций с точки зрения семантики.