Преобразовать регулярное выражение в CFG - PullRequest
Новая
       15

Преобразовать регулярное выражение в CFG

7 голосов
/ 14 апреля 2010

Как я могу преобразовать обычный язык в его эквивалентную грамматику без контекста? Нужно ли строить DFA, соответствующий этому регулярному выражению, или есть какое-то правило для такого преобразования?

Например, рассмотрим следующее регулярное выражение

* * 01 1005 + 10 (11) *

Как я могу описать грамматику, соответствующую приведенному выше RE?

Ответы [ 3 ]

11 голосов
/ 14 апреля 2010

  • Измените A + B на грамматику 

    G -> A
G -> B

  • Измените A * на 

    G -> (empty)
G -> A G

  • Изменить AB на 

    G -> AB

и рекурсивно переходить к A и B. Базовые случаи - это пустой язык (без продукций) и один символ.

В вашем случае 

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

Если язык описывается конечным автоматом:

  • использовать состояния в качестве нетерминальных символов
  • использовать язык в качестве набора терминальных символов
  • добавить переход p -> aq для любого перехода p -> q на букву a в оригинальном автомате
  • использовать начальное состояние в качестве начального символа в грамматике
6 голосов
/ 14 апреля 2010

Полагаю, вы имеете в виду преобразовать ее в формальную грамматику с правилами вида V-> w, где V - нетерминал, а w - строка терминалов / нетерминалов. Для начала вы можете просто сказать (смешивая синтаксис CFG и регулярное выражение): 

S -> 01+10(11)*

Где S - начальный символ. Теперь давайте разберем его немного (и добавим пробел для ясности): 

S -> 0 A 1 0 B
A -> 1+
B -> (11)*

Ключ должен преобразовать * es и + es в рекурсию. Сначала мы преобразуем звезду Клини в плюс, вставив промежуточное правило, которое принимает пустую строку: 

S -> 0 A 1 0 B
A -> 1+
B -> (empty)
B -> C
C -> (11)+

Наконец, мы преобразуем нотацию + в рекурсию: 

S -> 0 A 1 0 B
A -> 1
A -> A 1
B -> (empty)
B -> C
C -> 11
C -> C 11

Чтобы обработать x?, просто разбейте его на правило, создающее пустое, и правило, создающее x.

2 голосов
/ 16 мая 2012

На самом деле, разные грамматики CFG могут создавать один и тот же язык. Поэтому, учитывая регулярное выражение (регулярный язык), его отображение в CFG не является уникальным.

Определенно, вы можете создать CFG, который приведет к заданному регулярному выражению. Приведенные выше ответы показали некоторые способы достижения этого.

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

...