Extended context-free grammar (ECFG) is more powerful representation than that context-free grammar (CFG), which has finite automata, regular expressions, or syntax diagrams as a righthand side of productions. ECFGs describe the syntax of programming languages more concisely and more understandably than CFGs can do.
A mathod for building Extended LALR(ELALR) parsers for ECFGs was given by Nakata and Sassa [N&S86], but they assumed that the righthand sides of productions are deterministic finite automata (DFA). In this paper, an improved ELALR parser construction method for ECFGs, which allows the righthand sides of productions to be nondeterministic finite automata (NFA), is suggested. Our method is more preferable because NFA is more natural form for ECFGs than DFA. Also, an efficient algorithm to compute ELALR lookahead sets is proposed.
An ELALR parser generator based on the proposed new methods is implemented and exprimental results are presented.
