Грамматический разбор цепочек

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

10.1. Разбор цепочки "сверху-вниз".

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

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

Пример 34. Написать матрицу связей и таблицу подстановок для правил грамматики, приведенных в примере 14 и выполнить грамматический разбор арифметического выражения b), приведенного в примере 23.

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

Арифметическое выражение следует преобразовать к виду:

J = a ² + b ² = a x a + b x b;

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

Первым символом цепочки является операнд " a ". Поэтому последовательность вершин, связывающая начальный символ - J и первый символ цепочки " a", по матрице связей будет (J,T,M,K," a"). Максимальное левое поддерево, соединяющее эти два символа, есть последовательное соединение левых поддеревьев ((J,J), (J,T), (T,T), (T,M), (M,K), (K," a")). Следовательно, это поддерево есть позвоночник двоичного дерева. Первый символ цепочки записан правильно.

Если первым в цепочке указать знак операции, а не операнда, то невозможно найти позвоночник, связывающий начальный символ J с этим знаком. Так может быть оказана помощь в написании порядка следования символов цепочки.

Таблица 3

номер правила	Ai, w i	bi\wi
11	J, J	S1 T
12	J, T	-
21	T, T	S2 M
22	T, M	-
31	M, K	-
32	M, S31	J S32
41	S1, "+"	-
42	S1, "-"	-
51	S2, "x"	-
52	S2, "/"	-
61	S31, "("	-
62	S32, ")"	-
71	K, " a "	-
72	K, " b "	-

Следующим символом цепочки является знак бинарной операции "x", для которого в матрице связей есть левое поддерево (S2,"x"), но нет каких-либо связей в матрице с начальным символом грамматики J. Зато в таблице подстановок есть правое подерево (S2,M),корень которого S2 связан с левым поддеревом позвоночника (T,T) правилом 2₁ (T::= TS32M). Следовательно, правило 2₁ определяет нижнее ребро скелета и последнюю компоненту индекса скелета. Первая вершина этого ребра есть S2. Она же является начальной вершиной для левого поддерева. Следовательно, символ цепочки "x" связан с позвоночником последовательностью вершин (T,S2,"x"), т.е. он записан в цепочке правильно.

Если вторым в цепочке указать операнд,то невозможно установить связь этого символа с найденным позвоночником. Следовательно, между операндами обязательно должен быть знак операции. Так может быть оказана помощь в исправлении порядка следования символов цепочки.

Очередным символом цепочки является второй операнд " a ", а очередной вершиной нижнего ребра - M. По матрице связей выполняется поиск маршрута среди левых деревьев от начальной вершины M до концевой, являющейся образом терминального символа цепочки "a". Найденное максимальное левое поддерево ((M,K),(K," a")) связывает нетерминальный символ M и терминальный символ цепочки " a " и обеспечивает связь с позвоночником последовательностью вершин (T,S2,M,K," a"). Следовательно, символ "a "записан в цепочке правильно.

Так как все концевые вершины, связанные с узлом нижнего ребра T, определены, то вершина T есть корень куста, а последовательность символов " a x a" есть "фраза".

Следующим символом цепочки является знак бинарной операции "+", для которого в матрице связей есть левое поддерево (S1,"+"), но нет каких-либо связей с позвоночником. В таблице подстановок есть правое подерево (S1,T), корень которого связан с левым поддеревом позвоночника (J,J) правилом 1₁ (J::= JS1T). Следовательно, правило 1₁ определяет cледующее ребро скелета и cледующую компоненту индекса скелета. Первая вершина этого ребра есть S1. Это - начальная вершина для левого дерева (S1,"+"). Теперь символ цепочки "+" связан с позвоночником последовательностью вершин (J,S1,"+"). Следовательно, символ "+" в цепочке записан правильно.

Очередным символом цепочки является знак операнда " b ", а очередной вершиной ребра является T. По матрице связей выполняется поиск от вершины T до терминального символа цепочки "b". Найденное максимальное левое поддерево ((T,T),(T,M),(M,K),(K," b")) связывает нетерминальный символ T и терминальный символ цепочки " b ". Теперь символ "b " связан с позвоночником последовательностью вершин (J,S1,T,M,K," b"). Следовательно, символ " b " в цепочке записан правильно.

Несмотря на то, что для всех вершин второго ребра найдены все максимальные левые поддеревья, узел J не является корнем куста, т.к. для последнего максимального левого поддерева существует узел T.

Следующим символом цепочки является знак бинарной операции "x", для которого в матрице связей есть левое поддерево (S2,"x"), но нет каких-либо связей с уже найденными ребрами. В таблице подстановок есть правое подерево (S2,M), корень которого связан с последном максимальным левым поддеревом правилом 2₁ (T::= TS2M). Следовательно, правило 2₁ определяет ребро и компоненту индекса скелета для поддерева двоичного дерева. Первая вершина этого ребра есть S2. Это - начальная вершина для левого дерева (S2,"x"). Теперь символ цепочки "x" связан с позвоночником последовательностью вершин (J,S1,T,S2,"x"). Следовательно, символ "x" в цепочке записан правильно.

И наконец, последним символом цепочки является операнд " b ", а очередной вершиной ребра - M. По матрице связей выполняется поиск маршрута от вершины M до терминального символа цепочки "b". Найденное максимальное левое поддерево ((M,K),(K," b")) связывает нетерминальный символ M и терминальный символ цепочки " b ". Так как все концевые вершины, связанные с узлом T, определены, то вершина T есть корень куста, а последовательность символов " b x b" есть фраза. Теперь символ "b "связан с позвоночником последовательностью вершин (J,S1,T,S2,M,K," b"). Следовательно, символ " b " в цепочке записан правильно.

Больше символов в цепочке нет. Следовательно, узел J является корнем куста, описывающего заданную цепочку J = a x a + b x b. Индекс скелета двоичного дерева есть (11,21), а индекс скелета поддерева (21).

Пример 35. Выполнить грамматический разбор арифметического выражения с), приведенного в примере 23.

Правила грамматики те же, что в примере 34. В цепочке символов перед операндом либо после знака бинарной операции будет вспомогательный символ "(".

Арифметическое выражение следует преобразовать к виду: J = (a + b)² = (a + b)x(a + b).

Список связей и таблица подстановок приведены в примере 34. Последовательность вершин, связывающая начальный символ - J с первым символом цепочки " (", будет (J,T,M,S31,"("). Максимальное левое поддерево, соединяющее эти два символа, есть последовательное соединение левых поддеревьев ((J,T),(T,T), (T,M), (M,S31), (S31,"(")). Следовательно, это поддерево есть позвоночник двоичного дерева. Первый символ цепочки " (" записан правильно.

Следующим символом цепочки является операнд " a ", для которого в матрице связей есть левое поддерево (K," a"), но нет каких-либо связей с позвоночником. В таблице подстановок есть правое подерево (J,S32), корень которого связан с последним левым поддеревом позвоночника (M,S31) правилом 3₂ (M::= S31JS32). Следовательно, правило 3₂ формирует ребро скелета двоичного дерева. Первой вершиной ребра является J, которая, в свою очередь, является начальной вершиной максимального левого поддерева. Максимальное левое поддерево ((J,J),(J,T),(T,M),(M,K),(K," a")) связывает символ "a" c основным скелетом двоичного дерева. Следовательно, символ " a " записан в цепочке правильно.

Следующим символом цепочки является знак бинарной операции "+", для которого в матрице связей есть левое поддерево (S1,"+"), но нет каких-либо связей с позвоночником. Зато в таблице подстановок есть правое поддерево (S1,T), связанное с левым поддеревом позвоночника (J,J) правилом 1₁ (J::= JS1T). Следовательно, максимальное левое поддерево ((J,J), (J,T), (T,M), (M,K), (K,"a")) есть позвоночник поддерева, а правило 11 определяет ребро и компоненту скелета поддерева. Первая вершина этого ребра есть S1. Это - начальная вершина для левого дерева (S1,"+"). Теперь символ цепочки "+" связан с позвоночником поддерева последовательностью вершин (J,S1,"+"). Следовательно, он связан и с позвоночником двоичного дерева. Символ "+" в цепочке записан правильно.

Очередным символом цепочки является операнд " b ", а очередной вершиной ребра является T. По матрице связей выполняется поиск от вершины T до терминального символа цепочки "b". Найденное максимальное левое поддерево ((T,M),(M,K),(K," b")) связывает нетерминальный символ T и терминальный символ цепочки " b ". Теперь символ "b " связан с позвоночником поддерева последовательностью вершин (J,S1,T,M,K," b") и с позвоночником двоичного дерева. Следовательно, символ " b " в цепочке записан правильно.

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

Очередным символом цепочки является знак бинарной операции "x", для которого в матрице связей есть левое поддерево (S2,"x"), но нет каких-либо связей с уже найденными ребрами. В таблице подстановок есть правое подерево (S2,M), которое может быть связано с позвоночником основного двоичного дерева правилом 21 (T::= TS2M). Следовательно, правило 21 определяет второе ребро скелета двоичного дерева. Первая вершина этого ребра есть S2. Это -начальная вершина для левого дерева (S2,"x"). Теперь символ цепочки "x" связан с позвоночником двоичного дерева последовательностью вершин (T,S2,"x"). Следовательно, символ "x" в цепочке записан правильно.

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

Очередным символом цепочки является операнд " a ", для которого в матрице связей есть левое поддерево (K," a"). В таблице подстановок есть правое подерево (J,S32), корень которого связан с левым поддеревом позвоночника (M,S31) правилом 32 (M::= S31JS32). Следовательно, правило 32 формирует ребро скелета второго поддерева. Первой вершиной этого ребра есть J, которая является начальной вершиной максимального левого поддерева ((J,J), (J,T), (T,M), (M,K), K," a")). Следовательно, символ " a " записан в цепочке правильно.

Следующим символом цепочки является знак бинарной операции "+", для которого в матрице связей есть левое поддерево (S1,"+"). В таблице подстановок есть правое поддерево (S1,T), связанное с левым поддеревом (J,J) правилом 11 (J::= JS1T). Следовательно, максимальное левое поддерево ((J,J), (J,T), (T,M), (M,K), (K,"a")) есть позвоночник третьего поддерева, а правило 11 определяет его ребро и компоненту скелета поддерева. Первая вершина этого ребра есть S1. Это - начальная вершина для левого дерева (S1,"+"). Теперь символ цепочки "+" связан с позвоночником поддерева последовательностью вершин ("+",S1,J). Следовательно, он связан с позвоночником двоичного дерева. Символ "+" в цепочке записан правильно.

Очередным символом цепочки является операнд " b ", а очередной вершиной ребра является T. По матрице связей выполняется поиск от вершины T до терминального символа цепочки "b". Найденное максимальное левое поддерево ((T,M),(M,K),(K," b")) связывает нетерминальный символ T и терминальный символ цепочки " b ". Теперь символ "b " связан с позвоночником поддерева последовательностью вершин (J,S1,T,M,K," b") и с позвоночником двоичного дерева. Следовательно, символ " b " в цепочке записан правильно.

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

(S32,")"). Следовательно, вершина ")" также связана с позвоночником двоичного дерева. Символ ")" в цепочке записан правильно.

Больше символов в цепочке нет. Следовательно, индекс скелета двоичного дерева есть (21,32), а индексы скелетов первого поддерева (11), второго поддерева (32), третьего поддерева (11).

10.2. Разбор цепочки "снизу-вверх".

Первым шагом в разборе цепочки является поиск маршрута среди левых поддеревьев по матрице связей от вершины, соответствующей первому слева символу цепочки, до первого узла двоичного дерева. Этот узел является кандидатом на корень куста, а правило грамматики определяет переход к таблице постановок для задания начальных вершин левых поддеревьев. Следующим шагом выполняется поиск маршрута среди левых поддеревьев от концевой вершины, cоответствующей следующему символу цепочки до первой начальной вершины. Порядок следования начальных вершин максимальных левых поддеревьев задан порядком их записи в таблице подстановок. Если для узла маршруты от концевых вершин до всех начальных вершин найдены правильно, то данный узел является корнем куста, а разобранная часть цепочки синтаксически правильной.

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

Пример 36. Выполнить грамматический разбор арифметического выражения b), приведенного в примере 23.

Правила грамматики те же, что в примере 34. Для удобства изложения у левых поддеревьев поменяем местами вершину-исток и вершину-сток.

Первым символом цепочки является " a ". Маршрут среди левых деревьев до первого узла - кандидата на первый куст -опирается на вершины ("a",K,M,T). Правило 2₁ (T::= TS2M) формирует правое поддерево для первого узла. По этому правилу определены в таблице подстановок начальные вершины левых поддеревьев S2 и M. Следующий символ цепочки "x" связан с вершиной S2 левым поддеревом ("x",S2). Очередной символ цепочки " a " связан со следующей вершиной M максимальным левым поддеревом (("a",K),(K,M)). Других вершин у правого поддерева нет. Поэтому вершина Т есть корень куста, а цепочка " a x a"- " фраза".

Маршрут от корня куста T до очередного узла левого поддерева по матрице связей есть ((T,T),(T,J)). Правило 1₁ (J::= JS1T) формирует очередное правое подерево, а вершина J становится кандидатом на формирование корня куста. По этому правилу определены в таблице подстановок начальные вершины левых поддеревьев S1 и T. Очередной символ цепочки "+" связан с вершиной S1 левым поддеревом ("+",S1). Следующий символ цепочки " b " соединяется с вершиной T цепочкой левых деревьев (("b",K), (K,M), (M,T), (T,T)), но на этом маршруте есть узел для правого поддерева по правилу 21 (T::= TS2M). Следовательно, вершина T становится вторым кандидатом на формирование корня другого куста. По правилу 2₁ в таблице подстановок определены начальные вершины левых поддеревьев S2 и M. Очередной символ цепочки "x" связан с вершиной S2 левым поддеревом ("x",S2). Следующий символ цепочки " b " связан с вершиной M максимальным левым поддеревом (("b",K),(K,M)). Других вершин, связанных с узлом T, нет. Поэтому вершина Т есть корень куста для цепочки b x b. Разобранная цепочка bxb является фразой.

В цепочке больше символов нет. Поэтому следует вернуться к вершине J, являющейся кандидатом на формирование куста. Так как все подчиненные узлы сформировали кусты, а каждый куст формирует "фразу", то вершина J также формирует куст, но для всей цепочки J=axa + bxb.

Так доказана правильность синтаксической конструкции всей цепочки.

Пример 37. Выполнить грамматический разбор арифметического выражения с), приведенного в примере 23.

Правила грамматики те же, что в примере 34.

Первым символом цепочки является " ( ". Вершина S31 левого поддерева ("(",S31) является узлом и первым кандидатом на формирование куста. Правилом 3₂ заданы в таблице подстановок начальные символы левых поддеревьев J и S32. Следующий символ цепочки " a " соединен с первой вершиной J маршрутом ("a",K,M,T,J). Так сформировано максимальное левое поддерево (("a",K),(K,M),(M,T),(T,J),(J,J)). На этом маршрут есть узел J. Он является кандидатом на формирование очередного куста. Правилом 1₁ в таблице подстановок заданы начальные символы левых поддеревьев S1 и T. Очередной символ цепочки "+" соединен с первой вершиной S1 левым деревом ("+",S1). Следующий символ цепочки " b " соединен с вершиной T максимальным левым поддеревом ((" b ",K),(K,M),(M,T)). Так как все вершины куста соединены c концевыми вершинами, отображающими фразу, то узел J есть корень первого куста.

Теперь следует вернуться к первому кандидату на формирование куста S31. Для вершины S32 есть левое поддерево (")",S32). Так как свободных вершин для узла S31 нет, то сформирован второй куст, который соответствует фразе "(a + b)" и корень которого S31.

Следующим узлом левого поддерева от корня куста S31 будет вершина T. Правило 2₁ в таблице подстановок определяет начальные вершины максимальных левых поддеревьев S2 и M. Вершина T становится кандидатом на формирование куста. Первой вершиной является S2, которая соединена с вершиной "x", отображающей очередной символ цепочки. Второй вершиной является M, которая соединена с концевой вершиной для очередного символа цепочки "(" максимальным левым поддеревом (("(",S31),(S31,M)). На этом маршруте вершина S31 является узлом, т.е. претендует на формирование куста. По правилу 32 в таблице подстановок определены начальные вершины левых поддеревьев J и S32. Следующий символ цепочки "a" связан с вершиной J максимальным левым поддеревом ((" a",K), (K,M), (M,T), (T,J), (J,J)). Для этого поддерева вершина J есть узел, т.е. она также претендует на формирование куста. По правилу 1₁ в таблице подстановок найдены начальные вершины левых поддеревьев S1 и T. Очередной символ цепочки "+" связан с вершиной S1 левым поддеревом ("+",S1). Следующий символ "b" соединяется с вершиной T максимальным левым поддеревом ((" b ",K),(K,M),(M,T)). Итак, все вершины, связанные с узлом J, определены правильно. Следовательно, узел J является корнем третьего куста для фразы " a + b ".

Вернувшись к предшествующему кандидату куста, найдем для очередного символа ")" левое поддерево (")",S32). Так сформирован четвертый куст с корнем S31 для фразы "(a + b).

Наконец, для корня куста T определены все кусты-потомки. Поэтому вершина T формирует куст для фразы "(a + b)x(a + b)".

Левое поддерево ((T,T),(T,J)) соединяет корень куста T с начальным символом грамматики J. Следовательно, фраза "(a + b)x(a + b)" полностью соответствует грамматике, имеющей начальным символом J.

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