Minimization of context-free grammars

Yu. D. Ryazanov ; S. V. Nazina

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 90-96.

Résumé

This paper solves the problem of transforming the initial context-free grammar (CF-grammar) without excess characters into equivalent CF-grammar with less complexity. To solve this problem, the following relation on the set of a CF-grammar non-terminals is introduced: $E = \{(X,Y): (X=Y) \vee (X\to \alpha\Leftrightarrow Y\to \beta \wedge\vert \alpha \vert = \vert \beta \vert \wedge \forall i\,(\alpha (i) = \beta (i)\vee (\alpha (i), \beta (i))\in E))\}$ where $X$, $Y$ are non-terminals, $\alpha$, $\beta$ are chains of terminal and non-terminals, possibly blank, $\alpha (i)$ is the $i$-th character in chain $\alpha$, $\beta (i)$ is the $i$-th character in chain $\beta$. It is proved that the relation $E$ has the equivalence property and splits the set of non-terminals into equivalence classes. An algorithm is proposed for splitting a set of non-terminals into equivalence classes based on the method of sequential decomposition of the set of non-terminals into subsets so that non-equivalent non-terminals fall into different subsets. New CF-grammar is built on a set of non-terminals $N$, which elements are representatives of equivalence classes. From the set of rules of the initial CF-grammar, the rules with the left parts belonging to the set $N$ are chosen. If there is a non-terminal in the left side of any selected rule that does not belong to the set $N$, then it is replaced by its equivalent non-terminal from the set $N$. After such transformations in the CF-grammar, sets of identical rules may appear. From each set of identical rules, we leave only one rule. The result is a CF-grammar containing less rules and non-terminals than the initial CF-grammar. The paper provides an example of the implementation of the described transformations.

Détail

Keywords: formal language, minimization.
Mots-clés : formal grammar, equivalence relation

Bibliographie

[1] Aho A. V., Ullman J. D., The Theory of Parsing, Translation and Compiling, v. 1, Prentice-Hall Inc., NJ, USA, 1972, 560 pp. | MR

[2] Aho A. V., Lam M. S., Sethi R., Ullman J. D., Compilers: Principles, Techniques, and Tools, Addison-Wesley, 2007, 1009 pp.

[3] Konyuxova O. V., Kravcova E. A., “The implementation of the simplifying context-free grammars algorithms in Haskell and in Prolog”, Information Systems and Technologies, 2017, no. 4, 77–86 (in Russian)

[4] Hopcroft J. E., “An $n\log n$ algorithm for minimizing states in a finite automaton”, Theory of Machines and Computations, Academic Press, N.Y., 1971, 189–196 | DOI | MR

[5] Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Pearson, 2013, 496 pp. | MR

[6] Martynenko B. K., “One more method for minimization of finite automata”, Computer Tools in Education, 2017, no. 1, 5–14 (in Russian)

[7] Polyakov V. M., Ryazanov Yu. D., “Reducing the number of states in pushdown recognizers by means of equivalence relation”, Intern. J. Pharmacy Technology, 8:4 (2016), 22578–22587

[8] Ryazanov Yu. D., “Reducing the Number of Pushdown Symbols in One-state Pushdown Recognizers”, Bulletin of BSTU named after V. G. Shukhov, 2017, no. 6, 152–157 (in Russian)

[9] Martynenko B. K., Syntax-directed data processing, St. Petersburg University, Saint-Petersburg, 2004, 316 pp. (in Russian)

[10] Fedorchenko L. N, “Minimization of Translational CFR-grammar and Conditions of Generated Parser CFR-language”, Bulletin of the Buryat State University. Mathematics, Informatics, 2013, no. 2, 39–49 (in Russian)

[11] Stasenko A. P., “Automaton model of visual description of syntax parsing”, Computational Technologies, 13:5 (2008), 70–87 (in Russian) | Zbl