用递归下降方法实现自底向上的语法分析

Bottom-up parsing implementation with recursive descendent method

针对LR(1)语法分析方法的分析能力较强,但其语法分析器的状态数太多,很难被应用的问题,提出了改进的LR(1)语法分析方法——RDLR(1)(RecursiveDescentLR(1))语法分析方法,同时给出了将LR(1)文法等价变换成RDLR(1)文法的一般方法。结果表明,该文法对语言的识别能力与LR(1)文法相同,比LALR(1)文法强;但其语法分析器的状态数却比LR(1)语法分析器的少,与LALR(1)语法分析器的状态数相当。

LR(1) parsing method is powerful, but it generates too many states. An improved LR(1) parsing method—RDLR(1)(Recursive Descent LR(1)) is introduced, and a regular method to transform an LR(1) grammar into a RDLR(1) grammar is given. The results show that RDLR(1) grammar is as powerful as LR(1) grammar and more powerful than LALR(1) grammar. But RDLR(1) parsing is less complex than LR(1) parsing and as complex as LALR(1) parsing.