Faster reachability analysis for LR(1) parsers

Frédéric Bour (1, 2) , François Pottier (1)

1 CAMBIUM - Langages de programmation : systèmes de types, concurrence, preuve de programme
2 Tarides [Paris]

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.

Mots clés: Compilers; Parsing; Error diagnosis; Reachability

Domaines: Langage de programmation [cs.PL]

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⟩