Синтаксический разбор – Построение дерева разбора

1. Задача синтаксического анализатора
2. Распознающие грамматики
3. Дерево разбора
4. Стратегии разбора
5. Разбор рекурсивным спуском
6. Ограниченные грамматики
7. Магазинные автоматы

Задача синтаксического анализатора

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

Распознающие грамматики

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

Дерево разбора

Дерево разбора в грамматике G=(V, W, E, P) – это помеченное упорядоченное дерево, каждая внутренняя вершина которого помечена символом из множества W, а каждый лист символом из множества V. Если внутренняя вершина помечена символом A, а ее прямые потомки – символами X1,…,Xn, то A → X1X2…Xn – правило этой грамматики. Причем левосторонний обход листьев этого дерева дает исходную сентенциальную форму. В таком случае говорят, что дерево соответствует сентенциальной форме или наоборот.