A direct branching algorithm for checking equivalence of strict deterministic vs. LL(k) grammars |
| |
Authors: | Etsuji Tomita |
| |
Affiliation: | Department of Communication Engineering, The University of Electro-Communications, Chofu, Tokyo, 182 Japan |
| |
Abstract: | We present here an equivalence checking algorithm which operates directly on a pair of strict deterministic vs. LL(k) grammars. It is also straightforwardly applicable to a pair of LL(k) grammars, though an LL(k) grammar is not necessarily strict deterministic. The basic idea is from Korenjak and Hopcroft's branching algorithm for simple deterministic grammars, but ours is so distinguished that it is throughout free from mixing the nonterminals of the respective grammars in question and then very simple. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|