3 ms·
This is my experience as well, both from previous projects and for my long-running self-flaggelation exercise in writing a Ruby compiler. My parser is a mix be
by vidarh 10y ago
This is my experience as well, both from previous projects and for my long-running self-flaggelation exercise in writing a Ruby compiler.
My parser is a mix between a straight-forward recursive descent parser relying on its own small library, and an operator precedence parser, because I like the elegance of operator precedence parsers... That is, I like the elegance of them in languages that are sufficiently regular.
Ruby quickly turned out to be a frustrating exercise in taking my nice, clean (at the outset) operator precedence parser and mangling it to handle all kinds of exceptions. You can see the reasons for every rule if you squint hard enough - they make it "nicer" to write Ruby most of the time (except when they don't...). But they make the parsing an absolutely awful mess [1].
I fantasise about finding nice abstractions for all of those exceptions one day, but I'm not holding my breath.
And this is with a "library" approach rather than a framework/generator.
I'm sure I can, and eventually will, extract out some descently reusable components from it, but those will have a layer of crap piled on top of them when they're used to parse Ruby, and that layer of crap will make up a substantial proportion of the line count...
[1] Here's an example of the kind of fun stuff you find when parsing Ruby:
- If foo is a method, then "foo [1]" is "foo([1])" (calling the method "foo" with an Array with the element "1")
- If foo is a local variable, then "foo [1]" is "foo.[](1)" (calling the method "[]" on the object in "foo" with "1" as the argument. (if foo is a local variable, it will always alias a method with the same name)
- chubot 10y agoI checked out your project, very interesting! My parser for bash is also recursive descent + operator precedence, along with 13 different lexer modes (maybe 14 or 15 when I'm done!). This seems to be the "standard" now for production quality parsers; AFAIK that's essentially Clang's strategy for parsing C++. Python is the exception in that it actually uses a custom parser generator (although the speed is not great, hence the need for .pyc files). I don't know Ruby very well, but I've heard that people do like its syntax, but it's quite hard to parse. I think that speaks to my point that humans are better at recognizing weird syntax than "standard algorithms" are. Humans like to use the part of their brain that makes subtle distinctions with languages. I'm also dreaming about finding some kind of abstraction to describe my shell -- a proper meta-language. Like you, I'm starting from the goal and working backwards toward the tool, not working forward within the limitations of an arbitrary tool. Your blog looks similar to my blog, although mine isn't quite step by step. I wrote about an interesting finding about operator precedence parsing: there are two different names floating around for the same algorithm. And also I think the way Crockford explained it in JavaScript had some "accidental" influence. http://www.oilshell.org/blog/2016/11/01.html http://www.oilshell.org/blog/2016/11/01.html http://www.oilshell.org/blog/2016/11/03.html http://www.oilshell.org/blog/2016/11/03.html
- aidenn0 10y agoAt what point does one abandon the lexer model? If you have 13 different lexer modes, why not just encode those as part of the recursive decent parser and act directly on characters? I'm not a parser/pl person, but my view of lexing is that it only really buys you something if your lexer is sufficiently separate from your parse; once you have to tokenize things differently depending on where you are in the parse tree, it is just an extra layer of abstraction that fails to clarify the code.
- chubot 10y agoWell, the practical answer that all languages I know of have separate lexical and grammatical structure. It's just easier to write if you separate them. Though it's baroque, even bash has clear lexical structure. In my code, the lexer is the foundation and doing a lot of useful work. It's a map from the 13 modes to a list of regexes, which is a lot of logic that is kept out of the parser. https://github.com/oilshell/oil/blob/master/osh/lex.py https://github.com/oilshell/oil/blob/master/osh/lex.py The parser just calls lexer.Read(lex_mode), which hides the complexity of all these regexes. (The lexer might look weird, but I wrote it in a style to port to C, and in particular using re2c. This is an awesome tool which I've mentioned in my blog a couple times, but not written about yet. It combines regular expressions and turns them into a bunch of gotos in C. http://www.oilshell.org/cross-ref.html?tag=re2c#re2c http://www.oilshell.org/cross-ref.html?tag=re2c#re2c ) ----------- For a more theoretical answer: I've had this discussion before, and I would claim that lexing and parsing should be separate because they differ in both computational power and running time. Lexing is fast but not that powerful -- you are structuring the input stream with (at most) regular expressions. It can be done in linear time, without backtracking. On the other hand, parsing is slow but more powerful, e.g. CFGs or PEGs can recognize more than regular expressions, but they require backtracking/memoization/lookahead/etc. In other words, why not do the easy work with the fast algorithm, and then do the harder work with the more complicated, expensive algorithm -- on a shorter input? I came to the conclusion several years ago that PEGs only combined lexing and parsing for reasons of academic presentation and proof. I don't think it actually helps you in practice. Hope that answered the question! I think my shell lexer is somewhat interesting so I plan to blog about it. Honestly re2c was almost the thing that inspired me to write the shell -- it would have been intractable otherwise.