Faster reachability analysis for LR(1) parsers - Archive ouverte HAL Access content directly
Conference Papers Year : 2021

Faster reachability analysis for LR(1) parsers


We present a novel algorithm for reachability in an LR(1) automaton. For each transition in the automaton, the problem is to determine under what conditions this transition can be taken, that is, which (minimal) input fragment and which lookahead symbol allow taking this transition. Our algorithm outperforms Pottier's algorithm (2016) by up to three orders of magnitude on real-world grammars. Among other applications, this vastly improves the scalability of Jeffery's error reporting technique (2003), where a mapping of (reachable) error states to messages must be created and maintained.
Fichier principal
Vignette du fichier
bour-pottier-reachability.pdf (571.02 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03478172 , version 1 (13-12-2021)



Frédéric Bour, François Pottier. Faster reachability analysis for LR(1) parsers. SLE 2021 - ACM SIGPLAN International Conference on Software Language Engineering, Oct 2021, Chicago, United States. ⟨10.1145/3486608.3486903⟩. ⟨hal-03478172⟩
9 View
17 Download



Gmail Facebook Twitter LinkedIn More