Синтаксическое дерево

В теории формальных языков для разбора синтаксической конструкции цепочки используют синтаксические деревья. Синтаксическое дерево - это дерево с одной выделенной вершиной, называемой корнем. Такое дерево позволяет описать одну, но синтаксически правильную последовательность символов в цепочке. Синтаксическое дерево называют также деревом разбора. Такое дерево есть ориентированный граф, в котором каждая вершина, кроме корня, связана не более чем с одной предшествующей. Множество вершин графа есть образ терминальных - V_T и нетерминальных - V_N символов, а множество дуг - образ правил формальной грамматики Р. Корень дерева - это образ начального символа J формальной грамматики.

Вершина-исток, инцидентная дуге, есть образ левой части продукции. Для КС-грамматики - это образ одного символа множества V_N. Вершина-сток, инцидентная дуге, есть образ правой части продукции. Для КС-грамматики - это образ одного символа из множества V = V_TÈV_N. Если вершина-сток есть образ нетерминального символа V_N, то к ней присоединяется новое дерево, корнем которого является данная вершина. Так формируются узлы на дереве. Если вершина-сток есть образ терминального символа V_T, то она формирует концевую вершину на дереве. Концевые вершины дерева часто называют листьями, а все множество листьев - кроной.

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

Множество концевых вершин-стоков вместе с вершиной-истоком формируют куст. Вершину-исток куста называют корнем куста. Имя этого корня есть имя синтаксической переменной, описывающей часть цепочки. Иногда эту часть цепочки называют "фразой".

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

Последней вершиной-истоком синтаксического дерева является вершина начального символа J, которая охватывает всю синтаксическую конструкцию цепочки. Последовательность ветвей дерева, связывающая начальную вершину J и вершину-сток для самого левого терминального символа цепочки формальной грамматики называют левым поддеревом.

Так как вершина-исток есть образ одного символа левой части продукции, то синтаксические деревья нашли применение в синтаксическом анализе текстов программ и в разработке алгоритмов их трансляции на язык вычислительной машины.

Пример 19. Построить синтаксические деревья для формирования правильных цепочек в грамматике G7 (см. пример 9).

В данной грамматике только два правила:

P = { p1: J::= ab; p2: J::= aJb }.

На рис. 5a) представлено синтаксическое дерево для правила J::= ab. Вершина J является корнем дерева и предком для вершин a и b. Концевые вершины a и b формируют крону дерева. Кроме того, вершины a и b являются братьями (старшим братом является вершина a) и потомками вершины J. На рис.5б) представлено дерево для правила J::= aJb. Вершина J является корнем дерева и предком для вершин a, J и b. Вершины a, J и b являются братьями (старшим братом также является вершина a) и потомками вершины J. Среди концевых вершин есть нетерминальный символ J. Поэтому множество вершин { a; J; b } не формирует крону. Вершина, соответствующая нетерминальному символу J, представляет узел на дереве, к которому может быть присоединено другое дерево с одноименным корнем. На рис.5в),5г) и т.д. показано "развитие" синтаксического дерева для данной грамматики.

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

Пример 20. Пусть дано предложение на естественном языке "хороший алгоритм имеет умеренную сложность".

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

Правила естественного языка и условные обозначения синтаксических переменных и лексем, указанные в круглых скобках, необходимы следующие:

<предложение - (J)>::= <группа-подлежащего - (A)> <группа-сказуемого -(B)>;

<группа-подлежащего - (A)>::= <прилаг.1 - (С)> <сущест.1 -(D)>;

<группа-сказуемого - (B)>::= <глагол - (E)> <дополнение - (F)>;

<дополнение - (F)>::= <прилаг.2 - G)> <сущест.2 - (H)>;

<сущест.1 - (D)>::="алгоритм"-(a1);

<сущест.2 - (H)>::= "cложность" - (a2);

<глагол -(E)>::= "имеет"- (b);

<прилаг.1 -(C)>::= "хороший - (c1);

<прилаг.2 -(G)>::= "умеренную"- (c2).

Синтаксические переменные <сущест.1> и сущест. 2> принадлежат классу <сущест>, <прилаг.1> и <прилаг.2> - классу <прилаг>. Однако индексация каждого члена одного класса оказывается удобной для устранения неоднозначности в семантике цепочки, отображающей все предложение.

На рис.6 представлено дерево разбора этого предложения.

<группа-подлежащего - (A)> и <группа-сказуемого - (B)> являются братьями и потомками для <предложение - (J)>, <прилаг.1 - (C)> и <cущест.1 - (D)> - братьями и потомками для <группа-подлежащего - (A)>, <глагол - (E)> и <дополнение - (F)> - братьями и потомками для <группа-сказуемого - (B)>, <прилаг.2 - (G)> и <сущест.2 - (H)> - братьями и потомками для <дополнения - (F)>. Последовательность ветвей, связывающая вершины <предложение - (J)>, <группа-подлежащего - (A)>, <прилаг.1> и "хороший", формируют левое поддерево синтаксического дерева.

Пример 21. Построить синтаксическое дерево для фрагмента программы на языке программирования Паскаль, имеющем начальным символом синтаксическую переменную <программа>.

Правила грамматики языка программирования Паскаль приведены в 2 (пример 3), а условные обозначения синтаксических переменных - в 4.

Начальной вершиной этого дерева является синтаксическая переменная <программа>, концевыми вершинами - лексемы текста программы и необходимые синтаксические переменные, взятые из множество правил языка Паскаль. Синтаксическое дерево для начального символа <программа> представлено на рис. 7a), а для начального символа J - на рис. 7b).

Полученное в результате разбора дерево не имеет кроны, т.к. концевая вершина <выражение> сохраняет образ нетерминального символа. Требуется написать еще несколько правил, определяющих c помощью терминальных символов это понятие. Последовательность ветвей, связывающих вершины <программа>, <заголовок-программы>, "PROGRAM", формирует левое поддерево синтаксического дерева.

Пример 22. Построить синтаксическое дерево для фрагмента программы на языке программирования Паскаль,имеющем начальным символом синтаксическую переменную <выражение>.

Небходимые правила грамматики языка программирования Паскаль приведены в 2 (пример 3), а условные обозначения синтаксических переменных - в 4.

Начальной вершиной этого дерева является синтаксическая переменная <выражение>, концевыми вершинами - лексемы текста программы. Синтаксическое дерево для начального символа <выражение> представлено на рис. 8a), а для начального символа С2 - на рис. 8b).

Полученное дерево имеет крону, т.к. все концевые вершины есть образы терминальных символов. Последовательность ветвей, связывающая вершины <выражение>, <терм>, <множ-ль>, <перем-я>, <идент-перем>, "i", формирует левое поддерево синтаксического дерева.

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

Пример 23. Пусть дана грамматика G9 (пример 14). Построить синтаксические деревья для арифметических выражений, заданных начальным символом грамматики J:

a) J= a + b²; см.рис. 9; b) J= a ² + b²; см.рис.10;

c) J= (a + b) ²; см.рис.11; d) J= a x b + a /(a - b); см.рис.12;

Левыми поддеревьями являются последовательности ветвей, соединяющие вершины синтаксических деревьев:

a) J-J-T-M-K- a; b) J-J-T-T-M-K- a;

c) J-T-M-S3-(; d) J-J-T-T-M-K -a.

Обзор синтаксических деревьев для четырех арифметических выражений позволяет допустить выводимость многих арифметических выражений, подчиняющихся правилам грамматики G9.
7. Алгоритмы обхода вершин дерева разбора.

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

Разработаны два алгоритма обхода синтаксического дерева: "сверху-вниз" и "снизу-вверх".

7.1 Алгоритм обхода "сверху-вниз".

шаг 1. выбрать корень дерева, соответствующий начальному символу J;

шаг 2. выбрать последовательно слева-направо каждую вершину-сток для самой левой вершины-истока;

шаг 3. если вершин-стоков больше нет, то конец, иначе перейти к шагу 2.

Пример 24. Написать правильную цепочку и найти систему составляющих для синтаксического дерева, представленного на рис.6.

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

JACc1Da1BEbFGc2Ha2.

В этой цепочке можно выделить составляющие подцепочки на уровне слов: Cc1 - имя и значение первого прилагательного, Da1 - имя и значение первого существительного, Eb - имя и значение сказуемого, Gc2 - имя и значение второго прилагательного, Ha2 - имя и значение второго существительного, на уровне членов предложения: AСc1Da1 - имя и значение группы подлежащего, FGc2Ha2 - имя и значение дополнения, BEbFGc2Ha2 - имя и значение сказуемого. Головой каждой подцепочки является синтаксическая переменная, что определяет условия для использования левосторонней грамматики

Система составляющих имеет вид

на уровне членов предложения:

CJ = { (A,2); (B,7); (F,10) };

на уровне слов:

СJ = { (C,3); (D,5); (E,8); (G,11); (H,13) }.

Каждая составляющая начинается в узле дерева и охватывает все множество вершин-стоков, связанных с этой вершиной-истоком. Составляющие (С,3) и (D,5) вложены в составляющую (A,2), составляющие (G,11) и (H,13) вложены в составляющую (F,10), cоставляющие (E,8) и (F,10) вложены в составляющую (B,7).

Пример 25. Написать правильную последовательность символов и найти систему составляющих для синтаксического дерева, представленного на рис.7.

Совершая обход дерева "сверху-вниз", получим цепочку терминальных и нетерминальных символов, раскрывающую синтаксическую конструкцию синтаксической переменной <программа> языка программирования Паскаль:

JA1a1A2a2c1B1B2a3B3B4C1А3ib1C2a4c2.

Основными составляющими в написании программы являются:

<заголовок-программы> - A1a1A2a2c1;

";" - c1;

<блок > - B1B2a3B3B4C1b1C2a4;

"." - c2.

Система составляющих для этой цепочки может быть записана так:

CJ = { (A1,2); (c1,6); (B1,10); (c2,19) }.

В каждую из составляющих вложены другие составляющие, имеющие меньшую длину. Так, например,

СA1 = { (A2,3) }.

Cоставляющая, голова которой есть терминальный символ, определяет служебное слово или специальный символ, имеющий фиксированный смысл.

Пример 26. Написать правильную последовательность символов и найти систему составляющих для синтаксического дерева, представленного на рис. 8.

Совершая обход дерева "сверху-вниз", получим следующую цепочку:

С2С3С4С1A3iD2xC4C1A3iD1+C3C4C1A3iD2xC4C1A3i.

Если принять основными составляющими цепочки нетерминальные символы С1 и С3, то систему составляющих можно записать так:

СС2 = { (C1,4);(C1,10);(C1,17);(C1,23);(C3,2);(C3,15) }.

Составляющая С1 есть голова подцепочки С1A3i.

7.2 Алгоритм обхода "снизу-вверх".

шаг 1. выбрать последовательно слева-направо вершины-стоки, соответствующие символам цепочки и найти вершину-исток на дереве;

шаг 2. если вершина-исток представляет начальный символ, то конец, иначе перейти к шагу 1.

Пример 27. Написать правильную цепочку и найти систему составляющих для синтаксического дерева, представленного на рис.6.

По правилам алгоритма "снизу-вверх" имеем правильную цепочку терминальных и нетерминальных символов:

c1Ca1DAbEc2Ga2HFBJ.

В цепочке также выделяются составляющие, но на первом месте каждой составляющей указывается ее значение, а на втором - имя: c1C; a1D; bE; c2G; a2H; c1Ca1DA; c2Ga2HF; bEc2Ga2HFB.

Хвостом каждой цепочки является синтаксическая переменная, что определяет условия использования правосторонней грамматики.

Система составляющих имеет вид:

на уровне членов предложения:

CJ = { (A,5);(F,12);(B,13)};

на уровне слов:

CJ = {(C,2);(D,4);(E,7);(G,9);(H,11)}.

Составляющие (C,2) и (D,4) вложены в составляющую (A,5), составляющие (G,9) и (H,11) вложены в (F,12), cоставляющие (E,7) и (F,12) вложены в (B,13).

Пример 28. Написать правильную последовательность символов и найти систему составляющих для синтаксического дерева, представленного на рис.7.

Совершая обход дерева "снизу-вверх", получим следующую цепочку:

a1a2A2A1c1iA3C1b1C2B4a3B3a4B2B1c2J.

Основными составляющими в написании программы являются

<заголовок программы> - a1a2A2c1A1;

";' - c1;

<блок > - iA3C1b1C2B4a3B3a4B2B1;

"." - c2.

Система составляющих для этой цепочки может быть записана так:

CJ = { (A1,4); (c1,5); (B1,16); (c2,17) }.

В каждую из составляющих вложены другие составляющие, имеющие меньшую длину. Так, например, составляющие A2 и A3 вложены в A1, составляющие C1 и С2 - в B4, составляющая B4 - в B3,составляющая B3 - в B2, а составляющая B2 - в B1.

Пример 29. Написать правильную последовательность символов и найти систему составляющих для синтаксического дерева, представленного на рис. 8.

Используя правила алгоритма "снизу-вверх", правильная цепочка символов имеет вид:

iA3C1C4xD2iA3C1C4C3+D1iA3C1C4xD2iA3C1C4C3C2.

Если принять основными составляющими цепочки нетерминальные символы С1 иС3, то систему составляющих можно записать так:

СС2 = { (C1,3);(C1,9);(C1,16);(C1,22);(C3,11);(C3,24) }.

Составляющая С1 есть хвост подцепочки iA3C1.

Дата добавления: 2015-06-27