Я пытаюсь найти обычную грамматику, которая генерирует язык, заданный регулярным выражением ((a+b∗c)d)∗
. Есть ли общий метод, который я могу использовать для преобразования регулярных выражений в обычные грамматики?
Как найти регулярную грамматику для заданного регулярного выражения?
Ответы (1)
Обычно гораздо проще преобразовать конечный автомат для регулярного языка в обычную грамматику, чем регулярное выражение в обычную грамматику. Я бы рекомендовал начать с создания автомата для регулярного выражения — либо вручную, либо с помощью алгоритма Томпсона для механического преобразования регулярного выражения в автомат — и затем выполнить преобразование оттуда.
person
templatetypedef
schedule
19.01.2016
Должен ли я следовать методу, чтобы было легче? Где я могу найти
- person user3419487; 19.01.2016
Начните с размышлений о том, как преобразовать DFA в обычную грамматику. Я думаю, вы обнаружите тесную связь между переходами и продукцией, а также между принимающими состояниями и -продукцией.
- person templatetypedef; 19.01.2016
да, понял. Спасибо :)
- person user3419487; 20.01.2016