Solving Difficult LR Parsing Conflicts by Postponing Them

Computer Science and Information Systems

C. Rodriguez-Leon¹ 

[1] Departamento de EIO y Computacion, Universidad de La Laguna

关键词: parsing;    lexical analysis;    syntactic analysis.;   

DOI  :  10.2298/CSIS101116008R

学科分类：社会科学、人文和艺术（综合）

来源: Computer Science and Information Systems

【 摘 要 】

Though yacc-like LR parser generators provide ways to solve shift-reduce conflicts using token precedences, no mechanisms are provided for the resolution of difficult shift-reduce or reduce-reduce conflicts. To solve this kind of conflicts the language designer has to modify the grammar. All the solutions for dealing with these difficult conflicts branch at each alternative, leading to the exploration of the whole search tree. These strategies differ in the way the tree is explored: GLR, Backtracking LR, Backtracking LR with priorities, etc. This paper explores an entirely different path: to extend the yacc conflict resolution sublanguage with new constructs allowing the programmers to explicit the way the conflict must be solved. These extensions supply ways to resolve any kind of conflicts, including those that can not be solved using static precedences. The method makes also feasible the parsing of grammars whose ambiguity must be solved in terms of the semantic context. Besides, it brings to LR-parsing a common LL-parsing feature: the advantage of providing full control over the specific trees the user wants to build.

【 授权许可】

CC BY-NC-ND