Существует множество технологических средств построения анализаторов формальных языков, используемых при создании разного вида трансляторов языков программирования. Все они, в конечном счёте, основываются на КС-грамматиках с теми или иными ограничениями, частным случаем которых являются регулярные (автоматные) грамматики. Как правило, эти технологические средства обеспечивают лишь проверку соответствующих требований, предъявляемых к грамматике, и выдачу диагностических сообщений об их нарушениях, тогда как существует множество способов эквивалентных преобразований КС-грамматик, которые могут быть выполнены автоматически и дать грамматики, удовлетворяющие требованиям метода анализа. Цель этой статьи – описать способ исключения несамовставленных нетерминалов из КС-грамматик за счёт введения регулярных выражений в правые части правил грамматики. В предельном случае такая преобразованная грамматика включает единственное правило для начального нетерминала.

There is a variety of parser generators for formal languages being used during designing compilers for programming languages of different types. All of them are based on the use of context-free grammars with various restrictions, regular grammars being a special case. As a rule, they only check the requirements imposed on grammar, and issue diagnostic messages in case of their violation. The purpose of this article is to describe the way of eliminating all nonterminals from the non-self-embedding grammar that gives the equivalent regular expression as result.