6 ms·

I think it's possible if you make your meta grammar programmable, i.e. instead of generating code to compile, go into higher-order programming and return struct

by zzzcpan 10y ago

I think it's possible if you make your meta grammar programmable, i.e. instead of generating code to compile, go into higher-order programming and return structures that contain functions to execute. This will let you insert programmable hooks into nodes on different stages and various specific behaviors, including proper errors, specific whitespaces, etc. Even switch parsers depending on context. What I mean is something like this in pseudo code: parser = Parser (" ... program ::= statements eof statements ::= statement* ") parser.AddHookBefore ("statement", function { ... }) ast = parser.match (input)

chubot 10y ago
How is that different than what something like Yacc or ANTLR already provide? Inserting arbitrary code is definitely necessary for real languages, but this breaks the model, any guarantees you might have gotten (about performance), and is often awkward. bash uses yacc, and there are a bunch of globals mutated in the semantic actions, which is not easy to reason about. They are REALLY breaking out of the model. That is why people prefer hand-written parsers, because you can develop your own model, specific to the language you are parsing. As I wrote in that blog post, my parser only requires two tokens of lookahead, so there are no fancy algorithms involved. The hard part isn't really deriving the parser from the grammar; it's everything else (parsing here docs, etc.) I would question whether this saves any effort or lines of code over the hand-written approach. I think you would just end up with something almost as long -- and if you count the parser generator itself, it will be longer.
- zzzcpan 10y ago
  I guess the only option to keep clean grammars is to extend the meta language itself enough to support language-specific features. And if you implement it yourself it's not actually that hard to do. Parsing is not really a big deal after all. If I remember correctly the idea behind OMeta is to invent new languages to fit better into your problem domain so you could save a ton of code, not to parse existing ones.
  - chubot 10y ago
    Yeah, I agree that they are more suited to designing new languages rather than parsing existing ones. Parsing toy languages is not a big deal -- but then I have to make the observation that metalanguages are solving precisely the problem that's not a big deal. But parsing real languages is a big deal. How many C, C++, Perl, Ruby, or shell parsers are there? How many text editors or lint tools contain poor implementations of such parsers? Those are languages people actually use. I think the lesson is that humans can understand more complex languages than "standard algorithms" can, and they PREFER those languages (as shown by voting with their feet). Metalanguages should be designed for the languages that people actually use rather than constraining them to an artificial model.
- 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 ago
    I 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

by zzzcpan 10y ago

chubot 10y ago

How is that different than what something like Yacc or ANTLR already provide? Inserting arbitrary code is definitely necessary for real languages, but this breaks the model, any guarantees you might have gotten (about performance), and is often awkward. bash uses yacc, and there are a bunch of globals mutated in the semantic actions, which is not easy to reason about. They are REALLY breaking out of the model. That is why people prefer hand-written parsers, because you can develop your own model, specific to the language you are parsing. As I wrote in that blog post, my parser only requires two tokens of lookahead, so there are no fancy algorithms involved. The hard part isn't really deriving the parser from the grammar; it's everything else (parsing here docs, etc.) I would question whether this saves any effort or lines of code over the hand-written approach. I think you would just end up with something almost as long -- and if you count the parser generator itself, it will be longer.

zzzcpan 10y ago
I guess the only option to keep clean grammars is to extend the meta language itself enough to support language-specific features. And if you implement it yourself it's not actually that hard to do. Parsing is not really a big deal after all. If I remember correctly the idea behind OMeta is to invent new languages to fit better into your problem domain so you could save a ton of code, not to parse existing ones.
- chubot 10y ago
  Yeah, I agree that they are more suited to designing new languages rather than parsing existing ones. Parsing toy languages is not a big deal -- but then I have to make the observation that metalanguages are solving precisely the problem that's not a big deal. But parsing real languages is a big deal. How many C, C++, Perl, Ruby, or shell parsers are there? How many text editors or lint tools contain poor implementations of such parsers? Those are languages people actually use. I think the lesson is that humans can understand more complex languages than "standard algorithms" can, and they PREFER those languages (as shown by voting with their feet). Metalanguages should be designed for the languages that people actually use rather than constraining them to an artificial model.
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 ago
  I 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