Journal's Facebook pageDOI:10.2298/CSIS101116008R
Solving Difficult LR Parsing Conflicts by Postponing Them
- Departamento de EIO y Computacion, Universidad de La Laguna
http://nereida.deioc.ull.es
casiano@ull.es, lgforte@ull.es
Abstract
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.
Key words
parsing, lexical analysis, syntactic analysis.
Digital Object Identifier (DOI)
https://doi.org/10.2298/CSIS101116008R
Publication information
Volume 8, Issue 2 (May 2011)
Advances in Formal Languages, Modeling and Applications
Year of Publication: 2011
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium
Full text
Available in PDF
Portable Document Format
How to cite
Rodriguez-Leon, C., Garcia-Forte, L.: Solving Difficult LR Parsing Conflicts by Postponing Them. Computer Science and Information Systems, Vol. 8, No. 2, 517-531. (2011), https://doi.org/10.2298/CSIS101116008R
