3 ms·

I used Lex and Yacc (as the article mentions, the direct predecessors of the Flex and Bison it talks about) a bit a long time ago, but more recently when I've w

I used Lex and Yacc (as the article mentions, the direct predecessors of the Flex and Bison it talks about) a bit a long time ago, but more recently when I've written parsers I've just used recursive descent - but I was parsing a well-defined grammar. It did leave me with the knowledge of how to describe grammars in Yacc though, which I have found useful. Guy Steele said something about a use of Yacc for language design (rather than implementation) that stuck with me : Be sure that your language will parse. It seems stupid to sit down and start designing constructs and not worry how they will fit together. You can get a language that's difficult if not impossible to parse, not only for a computer, but for a person. I use YACC constantly as a check of all my language designs, but I very seldom use YACC in the implementation. I use it as a tester, to be sure that it's LR(1) ... because if a language is LR(1) it's more likely that a person can deal with it. From the Dynamic Languages Wizards series (in 2001), in the panel on language design (1:09:05) [1] I've not yet employed Yacc in this fashion, but it did give me a tool for thinking about object models. A while ago when I was puzzling over how some classes in an entity relationship diagram should be related, and I considered it from the point of view of how would I design a grammar for serializing an instance of the model into text. This essentially made my decision for me in a principled way, though I never reached the point of writing up a grammar for the whole model, just considered the implications for the local bit that was troubling me. [1] https://youtu.be/agw-wlHGi0E?si=n-ann0TYjvZ45ie5&t=4145 https://youtu.be/agw-wlHGi0E?si=n-ann0TYjvZ45ie5&t=4145 edit: added a few clarifying notes

kazinator 3y ago
If you want a language easy to deal with for humans, you want LL(1) or possibly LL(k) for some reasonable k. LR(1) isn't easy to deal with: LR(1) shift-reduce parsing allows an arbitrary number of tokens to be stuffed into the parser stack before making a single reduction. If you want easy to parse, make sure that a left-to-right scan can make a parsing decision by looking at a small number of tokens (often one). A permanent parsing decision: parse it this way or that way, no backtracking to try something else.

kazinator 3y ago

If you want a language easy to deal with for humans, you want LL(1) or possibly LL(k) for some reasonable k. LR(1) isn't easy to deal with: LR(1) shift-reduce parsing allows an arbitrary number of tokens to be stuffed into the parser stack before making a single reduction. If you want easy to parse, make sure that a left-to-right scan can make a parsing decision by looking at a small number of tokens (often one). A permanent parsing decision: parse it this way or that way, no backtracking to try something else.