DOI:10.2298/CSIS101116008R

Solving Difficult LR Parsing Conflicts by Postponing Them

C. Rodriguez-Leon1 and L. Garcia-Forte1

  1. 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: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable 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)