Регулярные языки и КС-грамматики

Abstract

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.