In “Parsing: The Solved Problem That Isn’t” (2011), Laurence Tratt survey’s the algorithms available and explains why he finds them inadequate. I’m not the first person to notice this contradiction. If computer science has extensively studied parsing algorithms and many parser generators have been written, how come they aren’t used? Indeed, parsing is often treated as if it is a “solved problem.” What gives?
Approaches like that are prevalent in both the programming language design community and production compilers. Instead, I’ve ended up implementing a recursive descent parser that switches to precedence climbing for expression parsing. Unfortunately, despite a lot of searching, I’ve never found one that works well for language design or for that matter production compilers. Ideally, I could look at the parser generators for the language I’m working in and pick the one that suited my use case. Various parser generators are available and support a soup of parsing algorithms including LL, LR, LALR, ALL(*), GLR, and others. Trying to design a new programming language, I’m faced with the question of how to implement a parser for it.
0 kommentar(er)
