Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2014-11-12

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary

All times shown according to UTC.

Time Nick Message
00:04 flaviu joined #marpa
01:00 lie_detector joined #marpa
01:16 jeffreykegler joined #marpa
02:05 ronsavage joined #marpa
06:37 ronsavage joined #marpa
11:00 daxim which R2 test files exhibit parsing problems that are troublesome (infinite loops, exponential parsing time, plain impossible) in PEG parsers such as pegex or peg.js?
13:21 lie_detector joined #marpa
14:14 lwa joined #marpa
18:04 jeffreykegler daxim: re  http://irclog.perlgeek.de/​marpa/2014-11-12#i_9646971 -- almost all of them contain left recursions
18:04 jeffreykegler A very good question, though
18:11 jeffreykegler Re PEG's there is this, which does not answer daxim's question directly, but is very helpful: http://lambda-the-ultimate.​org/node/3039#comment-44356
18:21 jeffreykegler A problem, which also was the case with yacc, is that failure is very underreported -- here's an example for PEG ...
18:23 jeffreykegler If you look at the Wikipedia page, it tells you there is a large grammar for Lobjan, an effort at a constructed language to spoken by humans: http://en.wikipedia.org/wiki/Parsin​g_expression_grammar#External_links
18:24 jeffreykegler So, OK, follow the link: http://users.digitalkingdom.org/~​rlpowell/hobbies/lojban/grammar/
18:25 jeffreykegler and start reading.  What it says is they the author has *started* the grammar, has done "most" of it, and is confident about solving the remaining problems.
18:26 jeffreykegler (PEG is not actually a grammar, but a description of a parser -- it requires you to figure out how to parse the language, and requires you to use a seductive but treacherous formalism to do it.)
18:27 jeffreykegler Continuing reading, we note the author has run straight into what is perhaps PEG's nastiest feature -- you don't know what language you're parsing ...
18:29 jeffreykegler that is, even if PEG *is* doing the job there's no way of showing that -- you don't know what language you're parsing ...
18:30 jeffreykegler and therefore as he's doing the "rest" of his grammar, it's not clear he's making progress, or if he's actually regressing.
18:31 jeffreykegler Now read this tragedy further ... more struggles ... until we reach the end and ...
18:33 jeffreykegler He sees a possible solution, but it will require expanding the grammar by a factor of 20, which number he assures us is no joke.  I would certainly not be laughing if I sank a lot of effort into a parser and ran into this.
18:34 jeffreykegler But wait, it's still not the end ....
18:34 jeffreykegler "Update 20 Sep 2005: I am no longer so sure that it's possible, but I don't have any good reason; just a change in my gut feeling. I also think a 20 times size increase is probably conservative."
18:35 jeffreykegler It's like reading one of those journal expedition stories, you know, the kind where they all die one by one, and the last entry breaks off in middle with something like, "Solmething at the door, I hope it's not a bear ..."
18:36 Aria Oh geez.
18:36 Aria It so is
18:37 jeffreykegler But let's suppose this Lobjan parser *had* been finished.  Working with PEG is like working with nitroglycerin. (I've never actually done it, but I hear from the survivors.)
18:38 jeffreykegler Any change in a PEG grammar has large and unpredictable ramifications, so even if the Lobjan grammar had been finished, it would have been almost unchangeable ...
18:39 jeffreykegler and almost unmaintainable, which is A Big Deal, because ...
18:41 jeffreykegler if you recall from above, you don't know what language your parser parses, so you don't know really know if your parser really works for the grammar you intended.
18:42 jeffreykegler So follow up Wikipedia's report of a successful, large PEG implementation and this is what you actually find.
18:43 jeffreykegler A huge advantage of Marpa is that the language it parses is *exactly* the one you specified in your BNF.
18:44 Aria Still won't tell you it's ambiguous unless you find ambiguous input, but it'll at least do that. And you can resolve it.
18:45 jeffreykegler The question of whether a grammar is ambiguous is undecidable.
18:48 Aria Yep.
18:48 Aria You'll know it when you find it, but you can't always tell without input that proves it.
18:48 Aria (at least, with marpa you will)
18:48 jeffreykegler Also, to collect references for those interested in PEG'
18:49 jeffreykegler s limits, here is Laurence Tratt's paper: http://tratt.net/laurie/research/pubs/html/tratt__​direct_left_recursive_parsing_expression_grammars/
18:49 jeffreykegler Prof Tratt is the author of ANTLR, which takes the same kind of approach to left parsing that I took to Earley's parsing.
18:51 jeffreykegler OOPS!  no actually I confused him with Terence Parr.  Never mind. :-)
18:51 jeffreykegler Anyway the paper looks very careful and good.
20:24 lie_detector "It's like reading one of those journal expedition stories..."
20:24 lie_detector lol'd hard
21:39 flaviu joined #marpa

| Channels | #marpa index | Today | | Search | Google Search | Plain-Text | summary