Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Parsing: The Solved Problem That Isn't (2011)

tratt.net

Post reply on HN
Print view View original

51–60 of 71 posts

Re: Parsing: The Solved Problem That Isn't (2011)

#51

Post by breuleux »

justinpombrio wrote: post #47
c3d wrote: post #37

The XL programming language ( http://xlr.sf.net ) has a rather unique approach to parsing. There is a short article about it here: http://grenouille-bouillie.blogspot.fr/2010/06/xl-axioms-rec... . XL features 8 simple node types, 4 leafs (integer, real, text, name/symbol) and 4 inner nodes (infix, prefix, postfix and block). With that, you can use a rather standard looking syntax, yet have an inner parse tree structu…

Judging from the article, if you parsed "if 3", you'd get back out (prefix if 3) instead of an error, since `if` is just a regular prefix operator. So, presumably there's some sort of well-formedness checking that goes on after parsing? Does anyone know more? The website says very little.

Yeah that puzzles me a bit too. Multifix operators are not more complicated than prefix/postfix/infix (well, only marginally). For instance, you can give each operator a left priority and a right priority and merge them when they meet with the same priority. Then `if x then y else z` would become (if/then/else x y z) or something like that. I think that's saner and easier to handle than what he does.

Re: Parsing: The Solved Problem That Isn't (2011)

#52

Post by justinpombrio »

breuleux wrote: post #51
justinpombrio wrote: post #47

Earlier quoted context omitted.

Judging from the article, if you parsed "if 3", you'd get back out (prefix if 3) instead of an error, since `if` is just a regular prefix operator. So, presumably there's some sort of well-formedness checking that goes on after parsing? Does anyone know more? The website says very little.

Yeah that puzzles me a bit too. Multifix operators are not more complicated than prefix/postfix/infix (well, only marginally). For instance, you can give each operator a left priority and a right priority and merge them when they meet with the same priority. Then `if x then y else z` would become (if/then/else x y z) or something like that. I think that's saner and easier to handle than what he does.

Yeah, that's what I was expecting too. And then XL could claim to have only five node types: integer, real, text, name, and multifix :-)

Re: Parsing: The Solved Problem That Isn't (2011)

#53

Post by l_dopa »

jblow wrote: post #38

It is nice to see someone summarizing this kind of information. However, really this is a continuation of the academic attitude toward parsers making them MUCH harder than they have to be. If you want to study grammars in an abstract sense, then think of them this way, and that's fine. If you want to build a parser for a programming language, don't use any of this stuff. Just write code to parse the language in a str…

This approach might be why several ubiquitous languages have needlessly ambiguous grammars. Decades of writing tools to be bug-compatible with the original implementation is much harder than learning a tiny bit of theory.

Re: Parsing: The Solved Problem That Isn't (2011)

#54

Post by dkarapetyan »

timdumol wrote: post #27
dkarapetyan wrote: post #25

Earlier quoted context omitted.

The more generic term for a lot of the stuff he talks about in that post falls under projectional editors and programming language workbenches. JetBrains MPS is one of the tools among many that help with building such editors. Here's a good talk by Markus Völter on using tools like JetBrains MPS.

I think you forgot to put in the link :)

http://www.infoq.com/presentations/tools-language-workbench

Re: Parsing: The Solved Problem That Isn't (2011)

#55

Post by sovande »

sklogic wrote: post #50
sovande wrote: post #49

Earlier quoted context omitted.

I was and also when scanning/lexing. My limited PEG parsing experience is with peg/leg by http://piumarta.com/software/peg/ and http://pegjs.majda.cz which is a Javascript PEG parser. Both very cool projects.

Looks like they do not include the optimisations I mentioned. But for this sort of use cases that would have been an overkill anyway.

So do you have an example of a PEG parser that uses these so called memorisation optimisation techniques then?

Re: Parsing: The Solved Problem That Isn't (2011)

#56

Post by chriswarbo »

jblow wrote: post #38

It is nice to see someone summarizing this kind of information. However, really this is a continuation of the academic attitude toward parsers making them MUCH harder than they have to be. If you want to study grammars in an abstract sense, then think of them this way, and that's fine. If you want to build a parser for a programming language, don't use any of this stuff. Just write code to parse the language in a str…

> Just write code to parse the language in a straightforward way.

This approach is why many consider parsing to be a solved problem, so it's certainly a valid approach. However, it's not the only valid approach.

For example, "straightforward" parsers often give terrible error messages: when the intended branch (eg. if/then/else) fails, the parser will backtrack and try a more general alternative (eg. a function call). Not only does this give an incorrect error (eg. "no such function 'esle'"), but it might actually succeed! In which case, the parser will be in the wrong state to parse the following text, and gives a non-sensical message (eg. "unexpected '('" several lines later).

This is an important problem, since these messages can only be decyphered by those who know enough about the syntax to avoid hitting them very often! Inexperienced users will see error messages over and over again, and have no idea that they're being asked to fix non-existent errors in incorrect positions.

Re: Parsing: The Solved Problem That Isn't (2011)

#57

Post by jblow »

wodenokoto wrote: post #43
jblow wrote: post #38

It is nice to see someone summarizing this kind of information. However, really this is a continuation of the academic attitude toward parsers making them MUCH harder than they have to be. If you want to study grammars in an abstract sense, then think of them this way, and that's fine. If you want to build a parser for a programming language, don't use any of this stuff. Just write code to parse the language in a str…

That's horrible advice. Some problems are really complex and can't be solved just by working from A to B. Your parser will probably not end up being able to handle the problems outlined in the article unless you take that theory into account before starting to program.

You never know, you might be talking to someone with actual experience.

Re: Parsing: The Solved Problem That Isn't (2011)

#58

Post by sklogic »

sovande wrote: post #55
sklogic wrote: post #50

Earlier quoted context omitted.

Looks like they do not include the optimisations I mentioned. But for this sort of use cases that would have been an overkill anyway.

So do you have an example of a PEG parser that uses these so called memorisation optimisation techniques then?

https://github.com/combinatorylogic/mbase/blob/master/src/l/...

Re: Parsing: The Solved Problem That Isn't (2011)

#59

Post by parrt »

I should add Adaptive LL(* ), ALL(* ), of ANTLR 4 to the mix here. It handles any grammar you give it and generates a correct parser except for one small caveat: no indirect left-recursion. It's the culimation of 25 years of focused effort to take LL-based parsing to the limit of power while maintaining simplicity and efficiency. See tool shootout in OOPSLA '14 paper I just presented http://www.antlr.org/papers/allstar-techreport.pdf Until we change the requirements of a parser generator, I'm done. :)

Re: Parsing: The Solved Problem That Isn't (2011)

#60

Post by ronsavage »

falsedan wrote: post #9

Jeffrey Kegler's work on Marpa is pretty exciting, but hasn't got much traction (maybe due to the implementation languages: Perl and Knuth's Literate Programming). https://metacpan.org/pod/Marpa::R2#A-simple-calculator

Marpa's homepage: http://savage.net.au/Marpa.html
Post reply on HN