Belgorod, Belgorod, Russian Federation
VAC 05.17.00 Химическая технология
VAC 05.23.00 Строительство и архитектура
GRNTI 20.53 Технические средства обеспечения информационных процессов
In this article the problem of the recognition of context-free languages is considered. The deterministic syntax diagrams are used for constructing effective recognizers. The class of left-recursive syntax diagrams is being considered in this article. The components of syntax diagrams with direct and indirect left recursion are defines in this paper. It is shown that left-recursive diagram is not deterministic and can not be used to construction effective recognizers. The author suggest the algorithm for converting left-recursive syntax diagram into equivalent diagram without left recursion, which can be deterministic. This algorithm expanded the class of syntax diagrams, which can be used for constructing effective recognizers.
context-free language, recognizer, syntax diagram , left recursion , equivalent transforming
Введение. Одним из наглядных способов задания синтаксиса языка являются синтаксические диаграммы (СД). Они применяются как для документирования языков программирования [1, 2], так и в проектировании программ обработки языков [3 – 7]. Основой таких программ является распознаватель языка. Для построения распознавателя линейной сложности [8, 9] используются детерминированные СД [8 – 11]. В множестве СД можно выделить класс леворекурсивных СД, которые не являются детерминированными и не могут быть использованы для построения эффективных распознавателей. В статье предложен алгоритм преобразования леворекурсивной синтаксической диаграммы в эквивалентную ей диаграмму без левой рекурсии. Применение этого алгоритма расширяет класс СД, которые можно использовать для построения эффективных распознавателей языков.
Основные понятия. На рис. 1 приведен пример СД, которая представляет собой ориентированный несвязный граф. В ней заглавными буквами (S,A,B) обозначены нетерминалы, прописными (a,b,c) – терминалы.
Каждому нетерминалу соответствует связная компонента графа. Компонента именуется соответствующим нетерминалом, имеет только одну точку входа и одну точку выхода и конечное множество узлов, терминальных и нетерминальных вершин. Точки входа и выхода на диаграмме компоненты не изображаются. Терминальная вершина изображается кружочком, в который вписан терминальный символ, нетерминальная – прямоугольником, в который вписан нетерминальный символ. Узел изображается на диаграмме жирной точкой. В точку входа не входит ни одна дуга и выходит конечное множество дуг (входные дуги компоненты). Узлы, в которые входят входные дуги, называются начальными. Из точки выхода не выходит ни одна дуга и входит конечное множество дуг (выходные дуги компоненты). Узлы, из которых выходят выходные дуги, называются заключительными. Дуги, соединяющие узлы, называются ε-дугами.
СД называется псевдодетерминированной (ПСД) [12], если в ней только один начальный узел и для каждого узла СД верно, что любые две дуги, выходящие из узла, идут в вершины, содержащие различные символы. В ПСД нет ε-дуг. СД, изображенная на рис. 1, является ПСД. Любую СД можно преобразовать в эквивалентную ей псевдодетерминированную СД [12].
Пусть в компоненте A синтаксической диаграммы существует путь l от точки входа до точки выхода. Если начать движение по этому пути и, проходя через терминальную или нетерминальную вершину, переписывать символ из вершины в некоторую изначально пустую цепочку α, то по окончании движения, когда придем в точку выхода, будет сформирована цепочка α, соответствующая пути l. Если путь l от точки входа до точки выхода не проходит ни через одну терминальную или нетерминальную вершину, то цепочка α пустая.
Пусть LA — множество всех путей от точки входа до точки выхода в компоненте A. Определим функцию F : LA → αA, которая каждому пути lÎLA ставит в соответствие цепочку α по описанному выше правилу.
|
c
|
|
A |
|
B |
|
a
|
|
A |
|
b
|
|
A |
|
a
|
|
c
|
|
S |
|
b
|
|
S |
|
a
|
|
B |
|
b
|
|
B |
Рис. 1. Синтаксическая диаграмма
Выводимые из нетерминала S цепочки определим следующим образом:
1) цепочка S – выводимая;
2) если цепочка γAβ выводимая, где γ и β – цепочки, состоящие из терминалов и нетерминалов, возможно пустые, а A – нетерминал, и некоторая цепочка αÎαA, то цепочка γαβ выводимая. Цепочка γαβ получается из цепочки γAβ путем замены нетерминала A на цепочку αÎαA.
Цепочку языка можно получить, «двигаясь» по дугам СД от точки входа начальной компоненты к ее точке выхода. При этом если дуга идет в терминальную вершину, то вписанный в нее символ добавляем в цепочку, если дуга идет в нетерминальную вершину, то переходим в соответствующую компоненту и движемся по ней аналогичным образом до точки выхода, после чего возвращаемся в предыдущую компоненту и продолжаем движение. После прохождения выходной дуги начальной компоненты в цепочку добавляем концевой маркер.
Символ x, который может быть добавлен в цепочку после прохождения выходящей из узла дуги e, принадлежит множеству выбора дуги e (ВЫБОР(e)). Узел u называется детерминированным, если множества выбора любых двух дуг, выходящих из узла u, не пересекаются. СД является детерминированной, если в ней все узлы детерминированные. В работах [8, 11] описаны алгоритмы вычисления множеств выбора дуг, выходящих из узлов, и определения принадлежности СД классу детерминированных СД.
Самолеворекурсивные компоненты синтаксических диаграмм. Компоненту А ПСД, в которой из начального узла одна из дуг идет в нетерминальную вершину с нетерминалом А, назовем самолеворекурсивной. Нетерминальную вершину с нетерминалом А, в которую идет дуга из начального узла, назовем леворекурсивной. Если считать компоненту А начальной в СД и в процессе левого вывода использовать только эту компоненту, то в ней можно вывести цепочки терминалов и нетерминалов вида βα*, где β – цепочка терминалов и нетерминалов, соответствующая пути от начального узла до заключительного, не проходящая через леворекурсивную вершину, а α* – последовательность цепочек терминалов и нетерминалов, возможно пустая, соответствующих путям от узла, в который входит дуга из леворекурсивной вершины, до заключительного узла. Точно такие же цепочки будем получать, если из компоненты А исключим леворекурсивную вершину, а из заключительных узлов проведем ε-дуги в узел, в который шла дуга из леворекурсивной вершины. Таким образом рекурсия в самолеворекурсивной компоненте заменяется итерацией.
На рис. 2 изображена самолеворекурсивная компонента ПСД. Устраняя левую рекурсию в этой компоненте по описанному выше правилу, получим компоненту, представленную на рис. 3.
|
b
|
|
A |
|
А |
|
a
|
|
В |
Рис. 2. Самолеворекурсивная компонента
|
b
|
|
A |
|
a
|
|
В |
Рис. 3. Компонента без левой рекурсии
Компонента на рис. 3 не является псевдодетерминированной, так как содержит ε-дуги. Преобразуем ее в псевдодетерминированную (рис. 4), используя алгоритм, описанный в работе [12].
|
b
|
|
A |
|
a
|
|
В |
|
В |
Рис. 4. Псевдодетерминированная компонента без левой рекурсии
Леворекурсивные компоненты синтаксических диаграмм. Компоненту А назовем леворекурсивной, если существует выводимая из А цепочка Аα, т. е. из А выводится цепочка, начинающаяся с нетерминала А. Очевидно, что самолеворекурсивная компонента является леворекурсивной. Для определения, является ли несамолеворекурсивная компонента А леворекурсивной, введем множество МА нетерминалов, с которых начинается хотя бы одна цепочка, выводимая из А. Такое множество можно получить следующим образом:
1. МА := Æ.
2. Если из начального узла компоненты А дуга идет в нетерминальную вершину с нетерминалом Х, то Х добавить в множество МА.
3. Если Х Î МА и из начального узла компоненты Х дуга идет в нетерминальную вершину с нетерминалом Y, то Y добавить в множество МА.
4. Повторять п.3, пока множество МА растет.
Если А Î МА, то компонента А леворекурсивная.
СД, содержащую хотя бы одну леворекурсивную компоненту, назовем леворекурсивной.
Пусть из начального узла леворекурсивной компоненты А дуга идет в вершину с нетерминалом Х. Если множество МХ нетерминалов, с которых начинается хотя бы одна цепочка, выводимая из Х, содержит нетерминал А, то такую дугу назовем леворекурсивной. Дугу, выходящую из начального узла, не являющуюся леворекурсивной, назовем нелеворекурсивной.
Покажем, что множества выбора леворекурсивной дуги и нелеворекурсивной дуги пересекаются.
Очевидно, что множество выбора дуги, входящей в нетерминальную вершину с нетерминалом Х равно объединению множеств выбора дуг, выходящих из начального узла компоненты Х.
Рассмотрим обязательно существующую в леворекурсивной СД последовательность дуг e1, e2,…, ek, такую, что
e1 – леворекурсивная дуга, идущая из начального узла компоненты А, в вершину с нетерминалом Х1;
e2 – дуга, идущая из начального узла компоненты Х1, в вершину с нетерминалом Х2;
ek – дуга, идущая из начального узла компоненты Хk–1, в вершину с нетерминалом A.
Пусть e – нелеворекурсивная дуга компоненты А, тогда
ВЫБОР(e) Í ВЫБОР(ek) Í … Í ВЫБОР(e2) Í ВЫБОР(e1), т. е.
ВЫБОР(e) Ç ВЫБОР(e1) ¹ Æ.
Следовательно, начальный узел леворекурсивной компоненты не является детерминированным и леворекурсивная СД так же не является детерминированной.
Устранение левой рекурсии в синтаксических диаграммах. Выше показано, что леворекурсивная СД не является детерминированной, поэтому, для преобразования СД в детерминированную, нужно, как минимум, устранить левую рекурсию.
Алгоритм устранения левой рекурсии следующий.
1. К1 := Æ – множество обработанных компонент (нетерминалов);
К2 := N – множество необработанных компонент (в начале алгоритма все компоненты (нетерминалы) необработанны).
2. Пока К2 ¹ Æ, выполнять п. 3.
3. Обработать компоненту А, А Î К2 по следующему алгоритму:
3.1. Если в компоненте А существует дуга, идущая из начального узла в вершину с нетерминалом Х, Х Î К1 и А Î МХ, то заменить вершину с нетерминалом Х компонентой Х, иначе выполнить п. 3.3.
3.2. Полученную в п. 3.1 компоненту А преобразовать в псевдодетерминированную и выполнить п. 3.1.
3.3. Если компонента А самолеворекурсивная, то устранить в ней левую рекурсию.
3.4. К2 := К2 \ {А}, К1 := К1 È {А}, т. е. исключить компоненту А из множества необработанных компонент и включить ее в множество обработанных компонент.
4. Конец алгоритма.
Рассмотрим устранение левой рекурсии в СД, представленной на рис. 1.
В этой диаграмме все компоненты леворекурсивные, т. к. МS = {A, B, S} и S Î МS, МА = {B, S, A} и А Î МA, МB = {S, A, B} и B Î МB.
В исходном состоянии К1 = Æ, К2 = {S, A, B}.
Множество К2 не пусто, берем из него компоненту S. В компоненте S нет дуги, идущей из начального узла в вершину с нетерминалом, принадлежащим множеству К1, т. к. К1 — пусто. Компоненту S исключаем из множества К2 и включаем в множество К1: К1 = {S}, К2 = {A, B}.
Из множества К2 берем компоненту А. В ней нет дуги, идущей из начального узла в вершину с нетерминалом, принадлежащим множеству К1. Компоненту А исключаем из множества К2 и включаем в множество К1: К1 = {S, A}, К2 = {B}.
Из множества К2 берем компоненту В. В ней есть дуга, идущая из начального узла в вершину с нетерминалом S, принадлежащим множеству К1. Множество МS = {A, B, S}, оно содержит компоненту В. Заменяем в компоненте В вершину с нетерминалом S компонентой S (рис. 5). Полученную компоненту преобразуем в псевдодетерминированную (рис. 6).
|
b
|
|
a
|
|
B |
|
b
|
|
B |
|
b
|
|
A |
|
a
|
|
c
|
Рис. 5. Компонента В
|
a
|
|
B |
|
b
|
|
B |
|
b
|
|
A |
|
a
|
|
c
|
Рис. 6. Псевдодетерминированная компонента В
В этой компоненте (рис. 6) есть дуга, идущая из начального узла в вершину с нетерминалом А, принадлежащим множеству К1. Множество МА = {B, S, A }, оно содержит компоненту В. Заменяем в компоненте В (рис. 6) вершину с нетерминалом А компонентой А (рис. 7).
|
c
|
|
B |
|
a
|
|
A |
|
a
|
|
B |
|
b
|
|
B |
|
b
|
|
a
|
|
c
|
Рис. 7. Самолеворекурсивная компонента В
Компонента В (рис. 7) самолеворекурсивная. Устраняя левую рекурсию, получаем компоненту В (рис. 8).
|
c
|
|
a
|
|
A |
|
a
|
|
B |
|
b
|
|
B |
|
b
|
|
a
|
|
c
|
Рис. 8. Компонента В без левой рекурсии
В этой компоненте нет дуги, идущей из начального узла в вершину с нетерминалом, поэтому компоненту В считаем обработанной, исключаем ее из множества К2 и включаем в множество К1: К1 = {S, A, B}, К2 = Æ.
Множество К2 пусто, СД без левой рекурсии получена. В этой СД действительно нет ни самолеворекурсивных компонент, ни леворекурсивных, т. к. МS = {A, B} и S Ï МS, МА = {B} и А Ï МА, МВ = Æ.
Выводы. В статье дано определение самолеворекурсивной и леворекурсивной компоненты СД, предложен алгоритм, определяющий принадлежность СД классу леворекурсивных СД, показано, что леворекурсивные СД не являются детерминированными и не могут быть использованы для построения эффективных распознавателей. Предложен алгоритм преобразования леворекурсивной синтаксической диаграммы в эквивалентную ей диаграмму без левой рекурсии. Это преобразование является обязательным в процессе преобразования недетерминированной СД в детерминированную и построения эффективных распознавателей языков.
1. Jensen K., Wirth N. Pascal User Manual and Report, Springer-Verlag, New York, 1975. p. 167.
2. Jensen K., Wirth N. Pascal Standard Iso - Jackson Libri, 1996. r.290.
3. Legalov A.I. Osnovy razrabotki translyatorov. URL: http://www.softcraft.ru/translat (data obrascheniya 22.01.2016).
4. Legalov A.I., Shvec D.A., Legalov I.A. Formal'nye yazyki i translyatory. Krasnoyarsk: Sibirskiy federal'nyy universitet. 2007. 213 s.
5. Karpov Yu.G. Teoriya i tehnologiya programmirovaniya. Osnovy postroeniya translyatorov. SPb.: BHV-Peterburg, 2005. 272 s.
6. Sverdlov S.Z. Yazyki programmirovaniya i metody translyacii. SPb.: Piter, 2007. 638 s.
7. Martynenko B.K. Sintaksicheskie diagrammy N. Virta i graf-shemy v Syntax-tehnologii // Komp'yuternye instrumenty v obrazovanii. 2014. № 2. S. 3-19.
8. Ryazanov Yu.D., Seval'neva M.N. Analiz sintaksicheskih diagramm i sintez programm-raspoznavateley lineynoy slozhnosti // Nauchnye vedomosti BelGU. Ser. Istoriya. Politologiya. Ekonomika. Informatika. 2013, № 8 (151). Vyp. 26/1. S. 128-136.
9. Polyakov V.M., Ryazanov Yu.D. Algoritm postroeniya nerekursivnyh programm-raspoznavateley lineynoy slozhnosti po determinirovannym sintaksicheskim diagrammam // Vestnik BGTU im. V.G. Shuhova. 2013. № 6, S. 194-199.
10. Ryazanov Yu.D. Preobrazovanie nedeterminirovannyh sintaksicheskih diagramm v determinirovannye // Vestnik VGU, seriya: sistemnyy analiz i informacionnye tehnologii, 2015. № 1. S. 139-147.
11. Ryazanov Yu.D., Kramarenko P.V. Grafovyy sposob analiza sintaksicheskih diagramm // Nauchnyy elektronnyy arhiv. URL: http://econf.rae.ru/article/8214 (data obrascheniya: 20.01.2016)
12. Ryazanov Yu.D., Seval'neva M.N. Psevdodeterminirovannye sintaksicheskie diagrammy // Prikladnaya matematika, upravlenie i informatika: sbornik trudov Mezhdunar. molodezh. konf., Belgorod, 3-5 oktyabrya 2012 g. : v 2 t., Belgorod : ID «Belgorod». 2012, T2. S. 546-553.
