Синтез распознавателя для КСР-языка

В настоящее время языковые технологии активно включаются в различные сферы нашей жизни, что приводит к развитию современных транслирующих систем, ориентированных на разнообразный ассортимент вычислительных устройств, применяемых в производственных системах типа «организационно-технический комплекс» (далее «комплекс») [1, 2]. При этом наиболее остро проявилась проблема быстрой настройки синтаксического определения языка на ту форму, которая допускает автоматическую или ручную реализацию, а также проблема учета ограничений выбранного метода синтаксического анализа. Первая проблема обусловлена разнообразием спецификаций реализуемых языков, диапазон которых простирается от обычной формы Бэкуса-Наура (БНФ) и языка разметки HTML, до двухуровневых грамматик, чаще всего используемых при конкретизации применительно к специфике комплекса, которая должна быть отражена в языках описания целей , подцелей и логических связей между ними. Вторая проблема ведет либо к языковой неоднозначности, либо к недетерминированности распознающего автомата.

Опыт использования различных инструментальных систем в производственной сфере показывает, что при построении языка целей комплекса его удобно задавать в виде двухуровневой КС-грамматики (типа VW-грамматики), которая расширена рядом контекстных правил . Такой тип грамматики эквивалентно трансформируется в КС-грамматику в регулярной форме (КСР-грамматику) [4, 5], которая отличается от обычной КС-грамматики тем, что в ней помимо алфавитов нетерминалов и терминалов имеется дополнительный алфавит контекстных символов ( семантик ), а правые части правил представляют собой регулярные выражения над символами объединенного алфавита грамматики. Эти выражения трактуются как формулы с регулярными операциями над множествами цепочек, составленных из терминальных и контекстных символов. Таким образом, множество правил КСР-грамматики рассматривается как система, определяющая значения всех нетерминалов в качестве ее неизвестных. В такой грамматике классическое понятие вывода заменяется понятием вычислимости значения регулярного выражения.

Далее рассмотрим построение распознавателя (анализатора) для языка, определяемого КСР-грамматикой (КСР-языка).

1.    Синтез распознающего автомата

Напомним определения КСР-грамматики и синтаксической граф-схемы графового аналога КСР-грамматики.

Определение 1. КСР-грамматикой называется пятерка множеств G_R = ( N , T , Σ , P , S ) , где N - множество нетерминалов, Т – множество терминалов, Σ – множество семантик, P – множество КСР-правил, P = { A : R_A . | A ∈ N , R_A - регулярное выражение над алфавитом N ∪ T ∪ Σ } , S - начальный нетерминал грамматики.

С практической точки зрения, КСР-правила удобно представлять в виде конечных ориентированных графов с помеченными вершинами и дугами. Такие графы, представляющие КСР-грамматику, преобразуются в детерминированную конечно-автоматную схему, в которой каждая вершина соответствует состоянию автомата, а ее метка специфицирует порождаемый символ. В специальном программном средстве SynGT(Syntax Graph Transformations), разработанном в СПИИРАН, набор графов, представляющих правила КСР-грамматики, снабженных дополнительной информацией на дугах (семантики, предикаты), называется синтаксической граф-схемой (СГС) КСР-грамматики [4, 5]. Синтез граф-схемы рекуррентен и описан в [4]. В системе SynGT используется графический интерфейс, примеры которого можно найти в [4, 5].

С каждой KCP -грамматикой G связываем ее такую синтаксическую граф-схему Γ _G , что L Γ _G = L ( G ).

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

• -    являясь адекватным регулярному выражению, граф нагляднее отражает структуру KCP-грамматики и не вводит лишнюю рекурсивность(структурированность) в KCP -язык;

• -    из граф-схемы проще выбирать информацию о порождаемом языке;

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

• -    с дугами граф-схемы легко связать вызовы семантических процедур;

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

2.    Состояния распознавателя 2.1.    Регулярный случай

Далее определим понятие состояния, играющее основную роль в синтезе распознающих автоматов. Известное из литературы [3] понятие состояния автомата связывается с помеченными вершинами граф-схемы.

Cостоянию, в котором находится автомат, приписывается определенное количество информации о языке. Прежде чем определить состояние автомата, рассмотрим состояния в СГС. В данном случае под состоянием распознавателя будем понимать состояние в синтаксической граф-схеме Γ _G , т.е.

множество вершин Γ _G . Переход от одного состояния к другому, которое также является множеством (возможно пустым) вершин в синтаксической граф-схеме (СГС), управляется текущим символом, поступающим из входного текста.

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

Рассмотрим случай, когда КСР-грамматика G порождает регулярный язык, а множество P правил грамматики содержит только одно S -правило для начального нетерминала S , P = { S : A } , правая часть которого – регулярное выражение A в алфавите T . Синтаксическая граф-схема Γ _G состоит из одного графа для нетерминала S – Γ _G = { Г_S }, и не содержит нетерминальных вершин.

В этом случае состояние в Γ _G определяется состоянием для регулярного выражения A в графе Γ A .

Пусть Γ _A – граф для регулярного выражения A . Определим понятие состояния для регулярного выражения в графе Γ _A .

Определение 2. Состоянием в графе Γ _A называется:

• 1)    либо выходная вершина F_A ;

• 2)    либо терминальная вершина в Γ _A ;

• 3)    либо объединение состояний в Γ _A .

Для произвольной вершины β в графе Γ _A , ( β ≠ F _A ) определим состояние вершины β в графе Γ _A как множество вершин, смежных с вершиной β .

Определение 3. Состоянием вершины в графе Γ _A называется множество вершин S _β :

S _β ={ α | α - терминальная или выходная вершина в Γ _A , α ∈ succ ( β ) }.

То есть состояние произвольной неконечной вершины в графе для нетерминала A совпадает с множеством вершин, смежных с данной вершиной, S _β = succ ( β ) .

Если β – входная вершина графа Γ _A , β = E_A , то S _β называется начальным состоянием графа Γ _A .

Из определения 3 видно, что начальное состояние графа Γ _A является множеством вершин, достижимых из входной вершины E_A . Достижимость из E_A означает то, что символы, помечающие вершины в начальном состоянии, соответствуют начальной букве слова, порождаемого графом Γ _A .

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

2.2.    Переходное состояние

Определенное выше состояние в графе Γ _A по содержанию тождественно понятию состояния конечного автомата [3]. При синтезе автомата каждое его состояние отождествляется с состоянием в графе для регулярного выражения.

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

После того как одна из этих альтернатив выбрана (когда известна следующая буква слова), может составляться следующая альтернатива (следующее состояние). Это можно осуществить с помощью операции «переход по символу».

Пусть S – произвольное состояние в графе Γ _A , и ξ – буква из алфавита Τ .

Определение 4. Состояние S I ^ называется переходом по символу ^ (переходным состоянием для S ) в граф-схеме Г A , причем:

• 1)    если S = ⁰ или S = { F }, то S I ^ = 0 ;

• 2)    если S = { а }, а - терминальная вершина в Г A , то

0 , если m( а ) * §

SIx= ^                        ;

S _а , если m( а ) = §

• 3)    если S = J S , то S I x = J ( S i I ^ . i = 1                         i = 1

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

Если исходное состояние пусто или отсутствуют терминальные вершины, помеченные данным символом, то переходное состояние также пусто.

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

Операцию «переход по символу» можно естественным образом обобщить до операции «переход по слову».

Пусть S - произвольное состояние в графе Г A , и x = x '^ - слово в алфавите Т , x 'е Т * .

Определение 5. Переходом по слову x для состояния S называется состояние S I x = ( S I x ')/ ^ . Переходом по пустому слову £ называется состояние S I s = S .

Из вышесказанного следует утверждение.

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

L a = { x е T | F a е S e a I x }.

2.3.    Общий случай

Рассмотрим общий случай, когда КСР -грамматика G порождает КС -язык, а регулярные выражения КСР -правил из P содержат вхождения нетерминалов. Синтаксическая граф-схема Г у состоит из совокупности графов для нетерминалов Г _у = ( Г _S , Г _{А ]}, Г _А^ ,^, Г _А^ ) и содержит нетерминальные вершины.

Вхождения нетерминальных вершин в графах нарушают регулярность языка, порождаемого Г _е , и это находит свое отражение в определении состояния: оно может содержать не только одно множество вершин (как в регулярном случае), а два – состояние перехода и состояние возврата. Каждое из них может содержать другие состояния, и таким образом возникает иерархия все более сложных состояний. В таком сложном состоянии существует множество вершин, которое является «фактическим» состоянием, а все остальные – накопленные (магазинные) состояния.

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

Чем меньше нетерминальных вершин в Г у (или вхождений нетерминалов в KCP -правилах), тем меньше сложных состояний возникает при синтезе магазинного автомата. Поэтому представляется целесообразным максимально снизить число вхождений нетерминалов в грамматике, используя эквивалентные преобразования с применением операции обобщенной итерации (#) . Для этой цели необходимо применить процедуру регуляризации KCP -грамматики, формальное описание которой дано в [4].

Переход из одного состояния в другое в общем случае также управляется текущим символом и происходит с помощью операции «переход по символу». Но в отличие от регулярного случая в конце подслова (порожденного некоторой компонентой граф-схемы ГA) можно вернуться к накопленному состоянию – состоянию возврата и затем продолжить переход.

Следующим определением введем понятие состояния в СГС Г у , обобщающее ранее определенное в разделах 2.1, 2.2.

Определение 6. Состоянием в графе-схеме Γ _G называется:

• 1)    либо выходная вершина F_Ai графа для некоторого нетерминала A_i из алфавита N ;

• 2)    либо терминальная вершина в Г у ;

• 3)    либо пара множеств ( 5 1 , 5 ₂), где 5 1 и 5 ₂ - состояния в Г _у ;

• 4)    либо объединение состояний в Г у .

Для произвольной вершины в ( в не является выходной вершиной) в синтаксической граф-схеме Г _е определим состояние 5 р - состояние вершины в Г у .

Определение 7. Для произвольной вершины в в синтаксической граф-схеме Г у состояние вершины 5 р имеет вид:

а | а е succ( в ), а - терминальная или выходная вершина в Г_у

5 = 1

( 5 E ₍ , 5 _а ) | а е succ ( в ), а - нетерминальная вершина в Г_у

Если в - входная вершина графа F A для некоторого нетерминала A i из алфавита N , то состояние 5 в в Г _у будет называться начальным состоянием графа Г A ( 5 E ).

i           A _i

Начальное состояние графа Г _S для стартового символа KCP -грамматики называется начальным состоянием синтаксической граф-схемы Γ _G (обозначение S ₀ ).

Таким образом, чтобы построить состояние некоторой вершины в Γ _G , необходимо сначала построить состояние этой вершины в некотором Г_A . Поскольку в графе Г_A встречаются как терминальные, так и нетерминальные вершины, то они должны входить в строящееся состояние. Затем нетерминальные вершины заменяются на сложное состояние (пара) в соответствии с назначением нетерминальных вершин в Г _у . После подслова, порожденного графом для такого нетерминала, слово продолжается так, как если бы вместо нетерминальной вершины в Г _у находилась бы терминальная вершина, а вместо подслова поступил бы символ – метка этой нетерминальной вершины.

Таким образом, состояние в Г у - это иерархия вложенных пар множеств терминальных или выходных вершин. Самый нижний уровень этой иерархии представляет собой «фактическое» состояние, все остальные состояния в парах – магазинные.

Пример 1 . Рассмотрим грамматику G :

у = ({ 5 , C i ,C 2 }, { a , b }, P , 5 ). P = { 5 : a ,(Q; C 2 ), a,C : b , 5, C 2 : b }

Показана синтаксическая граф-схема Г _у для KCP -грамматики у (рис. 1.).

S ■           2           4              С2 7              С1 5        6