Standard (right) regular grammars have three kinds of rules:

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

This is OK for a theoretical point of view, but a big inconvenience to be usable in practice. A practical regular grammar should allow us to use commodity operators (|,*,+,?,.,(,)), character sets and group multiple rules in a single one. For example, the following regular grammar describes fractional numbers:

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

The question is, what restrictions must be applied to RHS non-terminals to keep this grammars regular (if it is possible at all)?


Q - Why regular grammars instead of regular expressions?

A - Regular expressions are OK for simple languages, but they are write-only for more complex ones. On the other hand, well written extended regular grammars are allot more readable and maintainable and allows us to extend them with captures and rule actions easily.


1 Answer 1


Right regular grammars are very similar to NFAs. In fact, if we modify them slightly by forbidding productions of the form $A \to a$ but allowing ones of the form $A \to \epsilon$, they are completely equivalent to NFAs. As such, it's natural to allow rules of the form $A \to r B$, where $r$ is an arbitrary regular expression.

If we want to stay within the realm of grammars, we can allow instead (or additionally) rules of the form $A \to S'B$, where $S'$ is the starting symbol of a (nonterminal-)disjoint regular grammar (more generally, the regular grammars involved must form a DAG).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.