Может ли (расширенная) регулярная грамматика иметь несколько нетерминалов в своей правой части?

Стандартные (правильные) регулярные грамматики имеют три типа правил:

A <- ""
A <- "a"
A <- "a" B

Это нормально с теоретической точки зрения, но создает большие неудобства для практического использования. Практичная регулярная грамматика должна позволять нам использовать товарные операторы (|,*,+,?,.,(,)), наборы символов и группировать несколько правил в одно. Например, следующая регулярная грамматика описывает дробные числа:

start <- digit+ dot digit* | digit* dot digit+
digit <- [0-9]
dot   <- '.'

Вопрос в том, какие ограничения должны применяться к нетерминалам RHS, чтобы эти грамматики оставались регулярными (если это вообще возможно)?

ПРИМЕЧАНИЕ

В. Почему обычные грамматики вместо регулярных выражений?

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


regex regular-language
person user3368561    schedule 10.05.2016    source источник
comment
На самом деле это не про программирование. Вам больше повезет, спросив на CS.SE   -  person Laurel    schedule 10.05.2016

Ответы (1)


arrow_upward
0
arrow_downward

какие ограничения должны применяться к нетерминалам RHS, чтобы эти грамматики оставались регулярными

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

Для примеров, которые вы привели, это

  • A <- α | β ⇒ A <- α; A <- β
  • A <- [αβ…] ⇒ A <- α; A <- β; …
  • A <- . ⇒ A <- [Σ]
  • A <- B ? ⇒ A <- ε; A <- B
  • A <- B * ⇒ A <- X; X <- ε; X <- BX
  • A <- B + ⇒ A <- X; X <- B; X <- BX

Здесь у нас проблема, так как X <- BX не является обычным грамматическим правилом. Однако мы можем сделать копии B и всех его подтерминов, которые это позволяют:

  • B <- ε ⇒ BX <- X
  • B <- α ⇒ BX <- α X
  • B <- α C ⇒ BX <- α CX (то же самое для CX)

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

person Bergi    schedule 10.06.2016