Преобразование языковой спецификации в производственные правила (не уверен, что это CFG или CSG)

Мне нужно написать функцию, которая проверяет, допустимы ли входные строки для данной спецификации языка. Я думал, что это будет стандартная CFG -> Нормальная форма Хомского, затем синтаксический анализ CYK, но одно из правил языка предотвращает это.

Некоторые правила просты: если мы определим терминалы {a,b,c,d,e,f,P,Q,R,S}, то допустимые строки будут

1) Любой из терминалов в нижнем регистре изолированно
2) Если 'x' - допустимая строка, то Sx тоже.

Но третье правило

3) Если X и Y - допустимые входные строки, то PXY, QXY, RXY тоже.

где {P,Q,R} - остальные терминалы в верхнем регистре, а X и Y - нетерминалы.

Как будет выглядеть производственное правило для этого? Я думал, это будет что-то вроде

XY -> PXY (and QXY, RXY)

но с этим есть две проблемы. Во-первых, это не правило CFG - означает ли это, что вместо этого этот язык определяет CSG?

Во-вторых, это не работает, потому что

XY -> PXY -> PPXY

не во всех случаях будет правильным сообщением.


parsing context-free-grammar chomsky-hierarchy context-sensitive-grammar
person neptune    schedule 06.05.2012    source источник
comment
Начните задавать такие вопросы на CSTheory   -  person Pale Blue Dot    schedule 16.07.2012

Ответы (1)


arrow_upward
3
arrow_downward

Я думаю, что эта грамматика не зависит от контекста, если только я не неверно истолковываю то, что вы говорите.

Во-первых, пусть A будет нетерминалом, который расширяется до некоторой допустимой строки, созданной только с использованием первых двух правил, мы получаем

A -> a | b | c | d | e | f

Теперь ваше второе правило гласит, что если вы можете построить строку, вы можете построить S. Мы могли бы закодировать это как

A -> SA

Наконец, вы сказали, что если у вас есть две строки X и Y, вы можете объединить их вместе как

PXY
QXY
RXY

Один из способов подумать об этом - создать строку P, за которой следуют любые две допустимые строки (то же самое для Q или R). Таким образом, вы можете добавить правила

A -> PAA | QAA | RAA

Это дает окончательную грамматику

A -> a | b | c | d | e | f
A -> SA
A -> PAA | QAA | RAA

Надеюсь это поможет!

person templatetypedef    schedule 07.05.2012