# IRC log for #marpa, 2014-12-22

All times shown according to UTC.

Time Nick Message
00:00 ronsavage I'll reply via G+, since I'll be making a number of points.
02:22 ronsavage joined #marpa
02:36 flaviu joined #marpa
02:57 koo6 joined #marpa
02:57 koo5 joined #marpa
03:19 koo6 while you're at the PR, the other day i asked in another channel if they have heard of marpa, and one response was " I'm also not a fan of silently allowing ambiguous grammars."
03:20 Aria ...
03:20 koo6 ...
03:30 flaviu Is there a way to verify that it isn't ambigious?
03:31 flaviu I know you can verify a particular parse isn't ambiguous, but generating lots of examples isn't much fun, even if it's a good idea for testing.
03:47 Aria I believe it's been proven that you can't actually know.
03:47 Aria (though lots of common cases can be spotted.)
03:47 Aria But I'm not sure.
03:48 flaviu This stackexchange post seems to suggest that you can somehow convert your grammar into an equation and have a CAS solve it. http://math.stackexchange.com/questions/22463/is-this-bnf-grammar-ambiguous/22467#22467
03:49 flaviu He cites "Chomsky and Schützenberger, 1963", but I can't track down that article.
03:57 Aria Looks like that goes for left derivation only.
04:27 jeffreykegler joined #marpa
04:28 jeffreykegler koo6: it's undecidable whether a *grammar* is ambiguous
04:28 jeffreykegler but it is trivially decidable if a particular parse (grammar + input) is ambiguous.
04:30 jeffreykegler Marpa::R2's \$grammar->parse() method, in fact, by default throws a fatal error is the parse is ambiguous.
04:32 koo5 and...what options do we have to try to find that a grammar isnt ambiguous?
04:33 jeffreykegler If you're creating grammars and recognizers directly (the usual thing), then you can use the \$recce->ambiguous() method
04:34 jeffreykegler I'm not sure the person complaining has a real problem or is just throwing out an excuse for not looking at something new.
04:34 jeffreykegler If you won't use ambiguous languages, then you have to stop speaking English.
04:36 jeffreykegler That is, of the issues Marpa users have creating grammars, winding up with ambiguity (as differentiated with winding up with not the grammar they wanted) never seems to be an issue.
04:36 jeffreykegler Another way to put it, is you still have to figure out how to express the grammar that describes your language ...
04:37 jeffreykegler and once you've done that, if your language is not ambiguous, then your grammar is not,
04:37 jeffreykegler and if your language *is* ambiguous, then it's what you wanted.
04:38 jeffreykegler I hope the above does not sound like I'm being facetious, or sarcastic, because that is not my intent.
04:41 koo5 nah, youre just going off on a tangent as usual, since the kind of person who asked that question would only be interested in, for example, knowing that some unambiguous subset can be defined
04:41 koo5 or similar mathy answers
04:43 jeffreykegler Let's take this example -- a person who designs a language and wants an unambiguous subset.
04:43 jeffreykegler Does using LALR or regular expressions really offer a better alternative?
04:44 jeffreykegler I mean, yes, sure it will reject his unambiguous grammar, but there won't be a any explanation why ...
04:44 jeffreykegler * unambiguous -> ambiguous
04:45 jeffreykegler ... and LALR and regexes will also reject a whole lot of unambiguous grammars.
04:46 jeffreykegler I think for his case, Marpa is as least as good a tool as any.
04:48 jeffreykegler PEG will be unambiguous, but will achieve that by arbitrarily rejecting choices -- it's kind of like a driver who is never lost, but can't guarantee where he ends up. :-)
04:51 jeffreykegler Anyway, Marpa-based ambiguity detection tools are quite possible -- in fact, testing samples inputs and using the ambiguous() method is in fact a very good tool for exploring and reducing ambiguity ...
04:51 jeffreykegler and you sure can't duplicate that technique with PEG or LALR or regexes.
05:02 ronsavage joined #marpa
05:04 jeffreykegler Now, the real question may not be "ambiguity" in the parsing theory sense, but not knowing what language your parser parses -- I think the 2nd has to be the greater concern.
05:04 jeffreykegler With Marpa, you've got a precise BNF description of your language, and Marpa parses *exactly* that.
05:06 jeffreykegler With PEG and LALR (yacc/bison) using precedence (which you have to use to get anything done), you don't really know what language your parser is parsing.
05:06 jeffreykegler Although you do know it's unambiguous, because otherwise your parser wouldn't parse it. :-)
05:07 koo6 good points for sure
05:08 jeffreykegler This not-knowing-what-language you're parsing is *not* a theoretical issue --
05:08 jeffreykegler http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2011/10/perl-and-parsing-12-beating-up-on-the-use-statement.html
05:08 jeffreykegler That link describes an unintended syntax allowed by Perl's LALR-based parser.
05:10 jeffreykegler With recursive descent you have the same problem -- a recursive descent parser for a language of any size is too hairy to really know what language it is parsing.
05:11 jeffreykegler With simple regexes, you *do* know what language you're parsing -- it's one of their attractions, but with complex ones, again, all you know is that the examples you test parse.
05:12 jeffreykegler With this problem, most of the focus is on rejection of syntax that was intended to be valid, but in fact the opposite problem is worse ...
05:13 Aria Indeed. It's what makes your language unintendedly complex, that you'll have to support forever.
05:14 jeffreykegler over a language life cycle, accepting invalid syntax as valid can paint you into a corner -- if you fix the problem, so that invalid syntax is rejected, then programs which worked previously will stop working.
05:17 jeffreykegler This issue of "knowing what you're parsing" I've thought of as important -- if you think about it having to put up with parsers whose language you can't define is pretty intolerable ...
05:18 jeffreykegler I mean, there's lots of code out there who's behavior we can't define, but for anything but parsing, we call that "bad code".
05:19 jeffreykegler With parsing we call it "state-of-the-art professional tools"
05:20 koo5 :)
05:20 jeffreykegler Btw, are koo5 and koo6 two different people?
05:21 koo5 nah
05:23 jeffreykegler Ok, not a big deal, but I was thinking some IRC software might auto-assign 'koo*' names, so there were actually two of you.
05:23 koo5 i was banned for it from ##workingset the other day:)
05:24 jeffreykegler Really?  Lots of folks are on this group under two different names at once.
05:24 jeffreykegler Sometimes I am.
05:25 jeffreykegler lucs: this is not a issue, is it?
05:25 lucs Not that I know of.
05:26 jeffreykegler koo5: lucs is actually the admin for this group, and I let him decide.
05:26 jeffreykegler Though I hope he doesn't kick me off. :-)
05:26 lucs :)
05:26 lucs "admin" is a pretty big word. I just happened to be around when the channel was created, and I'm glad to give a hand.
05:27 koo5 i dont even know, somebody bothers me about it every once in a while, i suppose the op there didnt find my response to him clear enough, people keep too many outdated rules for me to care
05:28 jeffreykegler Yes, lucs became the admin kind of by accident, but it is an accident which has worked out very well ...
05:28 jeffreykegler and one which I am happy to continue.
05:28 lucs Sure thing, my pleasure.
05:28 * koo5 notes Do not provoke lucs
05:28 lucs :)
05:29 jeffreykegler The #workingset thing may be that the group is so busy they need to be more strict.
05:30 koo5 yeah
05:32 jeffreykegler I've thought of blogging about the "know what language you're parsing" topic, but what I say on the topic doesn't seem to register, and when that kind of thing happens, I just switch to topics where I *am* getting my point across.
05:33 jeffreykegler For example, I tried a couple of posts about how you can actually *use* ambiguity in language design ...
05:33 jeffreykegler and if anything they may have backfired.
05:35 jeffreykegler It's late California time, and time for me to wind down for the evening.
05:35 koo5 well, one such post actually made me discover marpa. Before that, i thought my editor will have to do much more work. It opened a whole new world to me
05:35 jeffreykegler Which post was that?
05:36 jeffreykegler I try to track which ones actually communicate, and which ones are just me talking to myself.
05:36 koo5 might have been this http://blogs.perl.org/users/jeffrey_kegler/2014/08/language-design-exploiting-ambiguity.html
05:36 koo5 but i cant be sure now
05:37 jeffreykegler Ironic, because that's one of the ones that I thought just fell into a black hole.
05:38 jeffreykegler Anyway, good night!
05:38 koo5 not so much about the content but seeing that somebody out there is thinking about parsing from a human perspective and is able to communicate his knowledge on that level
05:38 koo5 g'night
05:44 ronsavage OK. I've posted to G+.
09:39 lwa joined #marpa
12:11 flaviu ronsavage: Can you post a link here? I'm unable to find your post.
12:43 koo5 joined #marpa
12:43 koo6 joined #marpa
16:37 koo6 joined #marpa
16:37 koo5 joined #marpa
18:01 jeffreykegler joined #marpa
20:26 ronsavage My G+ post on the web site design: https://groups.google.com/forum/#!topic/marpa-parser/5mWvzcxxIH8
21:04 flaviu ah, google groups are separate from google plus. That's why I didn't find it.