Белгород, Белгородская область, Россия
ВАК 05.17.00 Химическая технология
ВАК 05.23.00 Строительство и архитектура
ГРНТИ 20.53 Технические средства обеспечения информационных процессов
В статье рассматривается задача распознавания контекстно-свободных языков. Для построения эффективных распознавателей используются детерминированные синтаксические диаграммы. В работе рассматривается класс леворекурсивных синтаксических диаграмм. Даны определения самолеворекурсивной и леворекурсивной компоненты синтаксической диаграммы. Показано, что леворекурсивная диаграмма не является детерминированной и не может быть использована для построения эффективных распознавателей. Предложен алгоритм преобразования леворекурсивной синтаксической диаграммы в эквивалентную ей диаграмму без левой рекурсии, которая может быть детерминированной. Применение этого алгоритма расширяет класс синтаксических диаграмм, которые можно использовать для построения эффективных распознавателей формальных языков.
контекстно-свободный язык, распознаватель, синтаксическая диаграмма, левая рекурсия, эквивалентные преобразования
Введение. Одним из наглядных способов задания синтаксиса языка являются синтаксические диаграммы (СД). Они применяются как для документирования языков программирования [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. р.290.
3. Легалов А.И. Основы разработки трансляторов. URL: http://www.softcraft.ru/translat (дата обращения 22.01.2016).
4. Легалов А.И., Швец Д.А., Легалов И.А. Формальные языки и трансляторы. Красноярск: Сибирский федеральный университет. 2007. 213 с.
5. Карпов Ю.Г. Теория и технология программирования. Основы построения трансляторов. СПб.: БХВ-Петербург, 2005. 272 с.
6. Свердлов С.З. Языки программирования и методы трансляции. СПб.: Питер, 2007. 638 с.
7. Мартыненко Б.К. Синтаксические диаграммы Н. Вирта и граф-схемы в Syntax-технологии // Компьютерные инструменты в образовании. 2014. № 2. С. 3–19.
8. Рязанов Ю.Д., Севальнева М.Н. Анализ синтаксических диаграмм и синтез программ-распознавателей линейной сложности // Научные ведомости БелГУ. Сер. История. Политология. Экономика. Информатика. 2013, № 8 (151). Вып. 26/1. С. 128–136.
9. Поляков В.М., Рязанов Ю.Д. Алгоритм построения нерекурсивных программ-распознавателей линейной сложности по детерминированным синтаксическим диаграммам // Вестник БГТУ им. В.Г. Шухова. 2013. № 6, С. 194–199.
10. Рязанов Ю.Д. Преобразование недетерминированных синтаксических диаграмм в детерминированные // Вестник ВГУ, серия: системный анализ и информационные технологии, 2015. № 1. С. 139–147.
11. Рязанов Ю.Д., Крамаренко П.В. Графовый способ анализа синтаксических диаграмм // Научный электронный архив. URL: http://econf.rae.ru/article/8214 (дата обращения: 20.01.2016)
12. Рязанов Ю.Д., Севальнева М.Н. Псевдодетерминированные синтаксические диаграммы // Прикладная математика, управление и информатика: сборник трудов Междунар. молодеж. конф., Белгород, 3–5 октября 2012 г. : в 2 т., Белгород : ИД «Белгород». 2012, Т2. С. 546–553.
