# IRC log for #marpa, 2015-11-14

All times shown according to UTC.

Time Nick Message
02:48 ilbot3 joined #marpa
02:48 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
04:20 Cheery thanks
04:37 Cheery So I'm reading on.. I may be understanding the deterministic reduction path.. but I'm not sure
04:38 Cheery it starts when you get a reduction with symbol. denoting that symbol with A
04:38 Cheery next there must be a rule that becomes completed.
04:39 Cheery ... A *
04:39 Cheery then it goes to check what rules become completed because that rule became completed
04:40 Cheery if it finds an unique rule of form * A, then it's on the path.
04:41 Cheery and it can omit the earlier reduction.
04:56 Cheery the rule that goes from * A to A * must be the same rule?
04:56 Cheery though it probably be, if it must be the only one.
05:02 Cheery I'm still not sure what it means in the terms of the code that the paper describes
05:03 Cheery it's the memoize_transitions and earley_reduction/leo_reduction -operations
05:03 Cheery the later two seem near identical, except that leo transition happens with an explicitly given symbol.
05:07 Cheery if I figure this out, this thing would be perfectly sufficient for me.
05:35 Idiosyncrat Cheery: one trick to thinking it out
05:35 Idiosyncrat is to think in terms from reconstructing the deterministic reduction path from just its top and bottom ...
05:35 Idiosyncrat which is what you have to do for a real Marpa implementation anyway.
05:36 Idiosyncrat That is, what do it mean for a path to be completely known, just given its top and bottom.
05:36 Cheery true
05:36 Idiosyncrat Think it out with that in mind, and the definitions may start to make sense.
05:37 Idiosyncrat Have you looked at Leo's paper?
05:37 Cheery I just looked at it this morning. but it's still hard
05:37 Cheery anyways.
05:37 Idiosyncrat It *is* a hard paper
05:37 Cheery I got something that may seem like it'd work, but I can't be sure.
05:38 Idiosyncrat How about the Grune & Jacobs account of Leo's algorithm?  Do you have access to a copy of G&J?
05:38 Cheery haven't seen that one.
05:39 Idiosyncrat I think they're 1st edition is online, and you really want to read their whole chapter on Earley IMHO
05:40 Idiosyncrat The Earley chapter didn't change much between the 1st and 2nd editions IIRC
05:40 Cheery I'll check in
05:41 Idiosyncrat Of course, if you have a good book budget, or access to a library you really want to get the 2nd edition.
05:41 Cheery btw. Here's what I got so far: https://gist.github.com/cheery/8a6d2f199d0d3324a752
05:41 Cheery it's this book? http://dickgrune.com/Books/PTAPG_1st_Edition/
05:41 Idiosyncrat I did peek at that but no more
05:41 Idiosyncrat Yes, that's it
05:42 Cheery thing I'd like you to look at, is this: and the next 20 lines: https://gist.github.com/cheery/8a6d2f199d0d3324a752#file-recognizer-py-L27
05:42 Idiosyncrat My apologies, but in my reading I am forced to focus on this theory paper rewrite, so I probably won't be able to give any detailed reactiion.
05:42 Cheery when are you done with it?
05:43 Cheery because you know.. reading your theory paper might actually help. :)
05:43 Idiosyncrat By my origiinal schedule, I was done a month ago. :-)
05:43 Idiosyncrat But I hope in the next couple of weeks.
05:54 ilbot3 joined #marpa
05:54 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
05:54 Cheery lots of jeans in the world..
05:54 Cheery I try github
05:55 Idiosyncrat https://github.com/jddurand
05:55 Idiosyncrat https://github.com/jddurand/MarpaX-Languages-C-AST
05:56 Idiosyncrat https://github.com/jddurand/MarpaX-Languages-ECMAScript-AST
05:56 Idiosyncrat The last two I think, really significant projects.
05:57 Idiosyncrat Basically Marpa-powered C-to-AST
05:57 Idiosyncrat and Javascript-to-AST
05:58 iarna joined #marpa
05:59 Cheery I'm probably heading to marpa-powered C compiler eventually too.
06:01 Cheery but the primary thing where I'm using these algorithms is the language implementation I'm working on.
06:02 Idiosyncrat Btw, I
06:02 Idiosyncrat I
06:03 Idiosyncrat I've devoted a lot of effort in the past to interesting folks in new kinds of Marpa-powered apps.
06:03 Idiosyncrat For example, in the original article on LR-regular grammars which IIRC is around 1970
06:04 Idiosyncrat They talk about how if they ever get a good LR-regular parser going it'd be great for syntax macros
06:04 Idiosyncrat (I think they had in mind ALGOL's)
06:05 Idiosyncrat Well, the practical LR-regular parser is here now, but everybody had given up on syntax macros for so long ...
06:05 Idiosyncrat that nobody even makes the connection.
06:06 Idiosyncrat If I had the time I'd love to experiment with stuff like self-extending languages.
06:06 Idiosyncrat But my belief is that this math basis needs to be worked out, and realistically if I don't do it, it won't happen.
06:08 Cheery that's actually interesting
06:09 Idiosyncrat It's just wide open at this point ... nobody is looking at it ...
06:09 Idiosyncrat but in the 1970's this kind of stuff used to fascinate folks, but the tools just did not exist.
06:12 Idiosyncrat https://vimeo.com/71278954
06:12 Cheery I did not dug in further half year ago, because even a fairly bad implementation did well. I felt it was important to get a good use-case first.
06:13 Idiosyncrat That link is a talk by Bret Victor where he pretends to be a 1970s programmer and talks about all the exciting ideas they had then
06:25 ilbot3 joined #marpa
06:25 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Pastebin: http://scsys.co.uk:8002/marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today
08:45 Cheery now I know it's not correct.. but it exhibits correct behavior.
08:48 Cheery the leo transition approach only makes sense if the table is sligtly different. :/
08:50 Cheery there is only one..
08:50 Cheery and it must activate only if the leo transition happens.
08:51 Cheery actually I think I let this be for now.
08:52 Cheery I'm pretty sure my previous parser didn't solve for right recursion.
08:53 Cheery oh wait.. something sparked.
08:54 Cheery the situations leo catches result in sort of recursion
08:55 Cheery the recursion is contained within that column
08:58 Cheery this is a program trace
08:58 Cheery [s -> a * ]
08:59 Cheery a is found at 3:4, produces reduction with 's' symbol
08:59 Cheery rules that expected 's' at 3 will be shifted
09:00 Cheery you will find exactly one rule at 3 expecting 's'
09:00 Cheery [s -> a * s]
09:01 Cheery the shift produces rule, and that rule reduces.
09:01 Cheery because the shifted rule had position 2, it will look one column further.
09:02 Cheery turns out there's also exactly one rule that expected 's'
09:02 Cheery once shifted, it will too reduce.
09:02 Cheery again looking a column further.
09:03 Cheery during the recursion chain, no additional information is provided about the state
09:03 Cheery therefore it can be omitted
09:06 Cheery 'no additional information'.. hmm
09:08 Cheery so state progression need not be done, iff it doesn't result in new potentials not produced by earlier rules in the table.
09:08 Cheery and iff they can be inferred.
09:08 Cheery from the rest of the column contents.
09:09 Cheery are the rules catched by leo condition only ones?
09:09 Cheery so lets look at what does this mean in the state table.
09:11 Cheery states always progress rightwards.
09:11 Cheery so the state (2, 3) will become (goto[2][term], 3)
09:12 Cheery now I've got obvious leo reduction chain with state 4
09:13 Cheery if I let it be, it produces (goto[4][symbol], 3-0) -states.
09:13 Cheery or wait. it's also got property that it doesn't actually produce anything shiftable.
09:14 Cheery so if the state doesn't shift, and is the same state as the parent state, it can be inferred.
09:15 Cheery I'm trying this in practice in a moment.
09:27 Cheery THEOREM.
09:27 Cheery given set of states (S, N), where S is constant. only the lowest and highest numbered origin is required
09:27 Cheery the others can be omitted
09:28 Cheery because the system goes through traditional shifting, this won't reduce computation if applied, though.
09:29 Cheery the earlier proposition is probably more fruitful
09:30 Cheery I'm adding a condition: if state == pstate and len(self.goto[pstate]) == 0:
09:30 Cheery continue
09:32 Cheery no effect. weird.
09:33 Cheery oh I'm trying it in the wrong point.
09:33 Cheery success. >:)
09:34 Cheery who knows how effective this little hack is.
09:35 Cheery but the theorem is possibly wrong.
09:38 Cheery okay this is correct: the state progression need not be done if it doesn't result in new interpretations of the input.
09:40 Cheery or actually. even that doesn't matter.
09:41 Cheery here's actually two constraints here the optimization must handle:
09:41 Cheery - it must not change what the parser parses
09:41 Cheery - the missing states must be possible to inferred from the other states.
09:42 Cheery the problem in omitting state transitions that transition into same state and do not shift: they might result in interesting reductions.
09:47 Cheery actually I can probably produce situation where it produces wrong parse in application of my rule.. and I can figure out things from there.
10:06 Cheery I try the following: if the reduction of rule contains itself, the rule can be omitted.
10:07 Cheery iff it doesn't have goto -entries.
10:09 Cheery wow. that works.
10:15 Cheery since it does the search in earlier piles, omission also verifies the cut into recursion
10:16 Cheery I don't know if it eliminates all forms of right recursion, but it omits the right recursion occurring in LR(0).
10:20 sivoais_ joined #marpa
10:28 Idiosyncrat joined #marpa
10:29 Idiosyncrat Last week I was sort of disappointed in the low readership of Marpa question on stackoverflow -- just 6
10:29 Idiosyncrat http://niceperl.blogspot.com/2015/11/ccxi-stackoverflow-perl-report.html
10:29 sivoais joined #marpa
10:30 Idiosyncrat Turns out that it was the highest rated Perl question of the week
10:31 Cheery ):
10:31 Idiosyncrat Depending on how you read that it's either great for Marpa or lousy for Perl. :-)
10:33 Cheery say I have a state: (ah, origin), and goto[ah].length = 0, and the reduction results in (ah, origin - n), I can drop out the (ah, origin)
10:33 Cheery if that is true, I just wrote an earley parser that can handle right recursion.
10:34 Cheery some kind of right recursion..
10:36 Idiosyncrat n?
10:36 Idiosyncrat that is, origin - n?
10:36 Cheery a value that is lower than origin
10:37 Idiosyncrat Is this using LR(0) states?
10:37 Cheery yes. the split-dfa described in horsespool paper.
10:38 Idiosyncrat I gave up on those because the complexity made my brain hurt and there was no payoff
10:39 Cheery I haven't figured out how to rewrite the nulls out of the grammar. :)
10:40 Idiosyncrat Aycock&Horspool outline a system for rewriting the grammar -- did you see that in their paper?
10:40 Cheery the nihilist normal form?
10:40 Idiosyncrat I think that's it -- anyway, it's important
10:41 Cheery yeah, but it felt hard to do. Maybe I should figure it out anyway though.
10:41 Idiosyncrat It is hard, but dealing with nulls is harder -- this is A&H's big discovery IMHO
10:41 Cheery true.
10:42 Idiosyncrat Their paper seems to be all about those LR(0) states, but that turned out to be IMHO counter-productive.
10:42 Cheery the LR automaton does the precisely same thing.
10:43 Cheery wait..
10:43 Idiosyncrat The LR automation in the A&H paper assumes a rewritten grammar
10:43 Cheery I figured it out .
10:43 Cheery just realised that
10:43 Idiosyncrat Anyway, initially I implemented both the automation and the rewrite -- the latter because the former needs it
10:43 Cheery thought about the example presented in the paper, and it just dropped into places
10:44 Cheery I'll try the different recognizers in my usecase later today
10:44 Idiosyncrat But I later realized the automaton is counter-productive, and the really important part of the paper is that rewrite.
10:44 Cheery first without optimization because I'm more sure it works
10:44 Idiosyncrat All sorts of ways to deal with nulls in Earley's have been tried, and IMHO it's A&H who really found the solution.
10:45 Cheery then with optimization, and later I'll look at those normal forms like you propose.
10:45 Cheery I don't need really featureful parser. :)
10:46 Cheery yeah. I've just not understood how the NNF is easier than LR tables. but I may figure it out eventually.
10:46 Idiosyncrat The LR tables *require* the NNF
10:47 Cheery the funny thing this is not much longer than what a hand-written parser for my language would be in total.
10:47 Cheery even if I'm not relying to libmarpa.
10:48 Cheery even with the LR(0) tables in. :)
10:48 Cheery hm.
10:48 Cheery you're right
10:48 Cheery I've got the NNF if I have the information about nullables
10:49 Cheery because the NNF is rewriting of the grammar in respect to nullable rules.
10:49 Idiosyncrat I spent more time studying the A&H method than they did, I suspect.
10:50 Idiosyncrat IMHO the grammar rewrite is the valuable part of their method -- the LR(0) states are very hard to get working ...
10:50 Cheery yes they are.
10:50 Idiosyncrat and counter-productive once you do get them working.
10:50 Cheery they may be.
10:50 Idiosyncrat I did a full implementation and then ran numbers.
10:51 Idiosyncrat So I found out the hard way.
10:52 Cheery getting to go, but I'll tell later on how things went.