Grammar partitioning and modular deterministic parsing

Complex languages are often modularized into sublanguages and the compiler is accordingly organized as a set of separate modules. Modularization (call ed federalization) is beneficial for beating complexity, for maintenance, a nd for reuse. Focusing on syntax analysis, we consider the decomposition of a grammar into deterministic subgrammars. We study three conditions for de terminism in grammar partitioning: first using homogeneous modules of the L R(1) or LL(1) kind; then using heterogeneous modules (LR(1) or LL(1)). Fede ralization slightly decreases the generality of LR(1) parsers, but not of L L(1) ones, and it allows to handle some grammars which are not LALR(1). Exp erimental results show that LR(1) federal automata have fewer (up to 60%) s tates than monolithic LR(1) automata. Criteria for modularization, practica l experiences and hints to semantic decomposition issues conclude the paper . (C) 1999 Elsevier Science Ltd. All rights reserved.