Сетевая грамматика

Сетевая грамматика [20], предложенная Вудсом, представляет собой множество направленных подграфов (сетей переходов) с конечным числом состояний и помеченными дугами (рис.2.6).

Рис. 2.6. Представление грамматики в виде сети переходов

Среди состояний выделяются:

– начальное (например, );

– множество промежуточных (например, ;

– множество конечных состояний (например, .

Метки на дугах могут быть:

– лексическими категориями (например. V – глагол, MV – модальный глагол, N – существительное, Par – частица, А – прилагательное, Рred – предлог);

– наименованиями состояний (например, PP – предложная группа существительных, VP – группа глагола, NP – группа существительного).

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

– наименование состояния на конце дуги запоминается в стеке;

– управление передается к состоянию, которым помечена дуга.

Операции запоминания в стеке и передачи управления называются погружением.

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

Чтобы сеть могла выполнять трансформационные преобразования (изменять фрагменты синтаксической структуры), к каждой дуге добавляется:

– произвольное условие (переход в состояние, указываемое дугой, разрешается только при выполнении этих условий);

– произвольное действие (действия выполняются, если осуществляется переход в состояние, на которое указывает дуга).

Полученная в результате такого добавления сеть называется расширенной сетью переходов (РАСП).

РАСП строит структурное описание предложения при переходе из одного состояния сети в другое. Части этого описания хранятся в регистрах (имеют стековую структуру) и их содержимое автоматически проталкивается (погружается), когда рекурсивное применение вызывает переход к более нижнему уровню. С дугами связаны действия, которые изменяют содержимое этих регистров, и условия. Описание сетевой грамматики задается с помощью нормальной формы Бэкуса (БНФ).

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

Описание набора нестандартных функций также опускается, так как их конкретизация зависит от реализации.

Типы дуг:

1. КАТЕГОРИЯ – задает лексическую категорию, которой помечена дуга.

2. ПОГРУЖЕНИЕ – указывает, что данный тип дуги вызывает операцию погружения. Используется для обработки дуг, помеченных наименованием состояния.

3. УСЛОВИЕ – задает условие перехода в состояние.

4. ВЫТАЛКИВАНИЕ – указывает на необходимость выполнения операции выталкивания стека. Связывает с конечным состоянием условия (их выполнение необходимо для подъема на более высокий уровень) и действия. Эта дуга является непомеченной (пустой).

Действие присваивает регистру значения формы:

1. ПРТЕК – присваивание на текущем уровне.

2. ПРПОГР – присваивание на уровне погружения (более глубокий, чем текущий уровень).

2. ПРПОГР – присваивание на уровне выталкивания.

Типы переходов:

1. ПУ (передача управления) – с выбором в качестве текущего обрабатываемого символа очередного символа входной строки (предложения).

2. ПП (переход к подпрограмме) – без изменения текущего обрабатываемого символа.

Типы форм:

1. ЗНАЧЕНИЕ – значением этой функции является содержимое регистра.

2. – значением этой функции является текущее слово входного предложения.

3. СВОЙСТВО – значением этой функции является значение свойства

4. ДЕРЕВО – значением этой функции является построенное дерево или его фрагмент. Фрагмент, выступающий вторым аргументом, задается при помощи скобок, символов и знака «+», обозначающего параметр.

5. СПИСОК – значением этой функции является список (форма) из значений аргументов.

6. ОБЪЕДИНИТЬ – значением этой функции является объединение двух списков (форм) в один.

7. ИМЯ – значением этой функции являются аргументы формы.

Опишем дуги, связанные с состояниями S0-S6 (рис.3.5)

((S0 (ПОГРУЖЕНИЕ NP

ИСТИНА

(ПРТЕК S D)

(ПРТЕК ТИП (ИМЯ ПОВЕСТВ))

(ПУ S1))

(КАТЕГОРИЯ MV

ИСТИНА

(ПРТЕК MV D)

(ПРТЕК ТИП (ИМЯ ВОПР))

(ПУ S2)))

(S1 (ПОГРУЖЕНИЕ VP

ИСТИНА

(ПРТЕК MV Æ)

(ПРТЕК VP D)

(ПУ S5))

(КАТЕГОРИЯ MV

ИСТИНА

(ПРТЕК MV D)

(ПУ S4)))

(S2 (КАТЕГОРИЯ Par

ИСТИНА

(ПУ S3)))

(S3 (ПОГРУЖЕНИЕ NP

ИСТИНА

(ПРТЕК S D)

(ПУ S4)))

(S4 (КАТЕГОРИЯ V

ИСТИНА

(ПРТЕК V D)

(ПУ S5)))

(S5 (ВЫТАЛКИВАНИЕ (ДЕРЕВО (S +++(VP +)) ТИП S MV D)

ИСТИНА)

(ПОГРУЖЕНИЕ NP

ИСТИНА

(ПРТЕК VP (ДЕРЕВО (VP (V +) D) V))

(ПУ S6)))

(S6 (ВЫТАЛКИВАНИЕ (ДЕРЕВО (S ++++) ТИП S MV VP)

ИСТИНА)

(ПОГРУЖЕНИЕ PP

ИСТИНА

(ПРТЕК VP (ОБЪЕДИНЕНИЕ (ЗНАЧЕНИЕ VP

(СПИСОК D))))

(ПУ S6)))

Символы ПОВЕСТВ и ВОПР обозначают типы предложений (повествовательное и вопросительное).

Например, для предложения «Будет ли оператор управлять агрегатом?» будут выполнены следующие действия.

S0: D=будет, MV:=будет;

ТИП:=ВОПР;

переход к S2;

S2: переход к S3;

S3: D=оператор, S:=(NP оператор);

переход к S4;

S4: D=управлять, V:=управлять;

переход к S5;

S5: D=агрегатом, VP:=(VP (V управлять)(NP агрегатом));

переход к S6;

S6: (S ВОПР(NP оператор) будет (VP (V управлять)(NP агрегатом))).

Для S0 ПОГРУЖЕНИЕ не выполняется.

Для S5 ВЫТАЛКИВАНИЕ не выполняется.

Для S6 ПОГРУЖЕНИЕ не выполняется.

Для простоты вместо условия подставляется ИСТИНА.

Выражения типа

(ДЕРЕВО (S +++(V +)D) ТИП S MV V)

означает, что вместо первых трех + будет подставляться значение ТИП, S, MV, а вместо четвертого – значение V.

Глубинная структура предложения представлена на рис.2.7.

Рис. 2.7. Глубинная структура предложения

В ряде случаев выделяют два вида регистров:

– содержания (содержат структуры);

– флаговые (содержат только условия).

К достоинствам сетевой грамматики относится то, что она

– обладает наглядностью (в отличие от ТПГ);

– обеспечивает мощность грамматики без ограничений (в отличие от НС-грамматики);

– способна объединять общие части правил (в отличие от НС-грамматики), что дает компактное представление, эффективность анализа и устраняет излишнюю обработку при разборе предложения;

– может использоваться для синтаксического анализа (в отличие от НС-грамматики и ТПГ, которые используются только для генерации);

– способна изменять построение фрагмента дерева, т.е. обеспечивает эффективность анализа;

– адаптивна (множество операций может пополняться в случае необходимости).

Недостатком этой грамматики является отсутствие эффективных алгоритмов синтаксического разбора (например, затруднено применение алгоритма Эрли, используемого для КС-грамматик).