Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-07-22

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

All times shown according to UTC.

Time Nick Message
00:00 jeffreykegler Interesting might be to try *not* implementing that optimization, and doing timings.
00:01 jeffreykegler Everyone assumes it's worth the effort, but I do not recall seeing any timings on modern hardware.
00:09 RichardMichaels hi
00:09 RichardMichaels im working on getting my Non-deterministic Finite Automation ready for release
00:36 jeffreykegler RichardMichaels: good luck
00:38 jeffreykegler I'm thinking of converting my Toshiba Satellite C55 laptop to Linux, which would leave me with no Windows machine.
00:39 jeffreykegler I've found with Windows 8.1 I spend a lot of time on updates and other care&feeding, and get little actual use out of it.
02:04 ronsavage jk: Re http://irclog.perlgeek.de/m​arpa/2015-07-22#i_10934733. Hahaha. News at 11 :-).
02:55 jeffreykegler joined #marpa
03:04 ronsavage joined #marpa
05:46 ceridwen joined #marpa
05:54 ronsavage joined #marpa
06:50 pczarn joined #marpa
09:54 pczarn I think it's best to build index entries while the current Earley set is still in cache
09:56 pczarn modern hardware probably makes index sets even more worth the effort
09:57 pczarn of course it all depends on the layout of index entries and Earley sets
09:58 pczarn I meant to say there may be more than one good way of implementing them
09:59 pczarn Your paper mentions they're sets of tables indexed by symbol
11:23 pczarn nevermind... Leo items have a lot of information which needs to be stored
13:40 pczarn will the internals of Kollos work with unit rules? because logic of binarized rules might be simpler without unit rules
14:45 RichardMichaels joined #marpa
15:38 lwa joined #marpa
16:16 koo7 joined #marpa
16:17 jeffreykegler joined #marpa
16:17 jeffreykegler pczarn: Kollos's binarization is not a strict Chomsky form so, yes, there are unit rules.
16:18 jeffreykegler The object is to allow rewrites, not to put the grammar into a theoretical form -- the binarization is a means to an end.
19:47 hobbs joined #marpa
20:17 RichardMichaels hi
20:25 pczarn hi
20:25 RichardMichaels are Non-deterministic finite automations good for writing compilers with?
20:27 pczarn what do you mean by writing compilers?
20:27 RichardMichaels for doing lexing and parsing
20:29 pczarn They're good for lexing but far too weak for parsing an average grammar
20:31 pczarn My intuition is they can only hold a limited amount of state
20:32 RichardMichaels hmmm
20:33 Aria Yeah, it really limits what you can express.
20:34 RichardMichaels Well I am going to put my code on github soon so anyone who is interested can look at what I am doing
20:34 RichardMichaels It may not be a strict NFA, i use stacks for nested rules
20:55 pczarn perhaps you're combining top-down parsing with NFA
21:02 pczarn Today I implemented Leo optimization
21:04 Aria Woo!
21:41 RichardMichaels Interestng
21:44 RichardMichaels My parser uses, clones, each clone contains a stack. Clones are run in parallel, they are expected to each process one character at a time and are called once for each character of input. The stack handles nested rules. An OR type, will create new clones off the parent clone for each rule in the OR-list, put those on the top of the stack in each clone.
21:46 RichardMichaels When a clone is run, the rule at the top of the clones stack is executed. If a rule fails, then the entire clone is deleted
21:47 Aria Sounds like that could go quadratic quickly.
21:47 RichardMichaels probably
21:48 RichardMichaels When clones are created, the parent clone they are branched from is inactivated.
21:48 RichardMichaels its actually deleted
21:48 RichardMichaels clones are also deleted if the have a failed rule
21:50 RichardMichaels the call stack is cloned, but, when the call stack reaches the level where a clone was created off its parent, it continues running seperately, it is not merged with the parent because the parent is gone
21:52 RichardMichaels AFAIK, unless the grammer is highly ambiguous, there shouldnt be many clones running at a single time
21:57 RichardMichaels There is no need to keep more than one character of input string in memory at a time
22:22 pczarn joined #marpa
22:56 ronsavage joined #marpa
23:20 jeffreykegler joined #marpa
23:22 jeffreykegler Some random interjections
23:23 jeffreykegler muvets: I've looked a bit at Toki Pano -- a very, very charming idea
23:23 jeffreykegler Re NFA's and parsing and quadratic -- there's actually a history of implementations here that repays study -- Russ Cox did some nice writeups
23:24 jeffreykegler Regex engines in practice go with one of two strategies -- DFA or NFA
23:24 jeffreykegler NFA does risk going quadratic, but in practice often proves the better choice.
23:25 jeffreykegler Ken Thompson's ground-breaking regex engine IIRC was NFA-based
23:26 jeffreykegler Creating one's own parsers from the ground up is a great way of experiencing the concepts, and I don't want to discourage that approach ...
23:27 jeffreykegler in particular the best approach in general is the one that enthuses you -- taking a "correct" approach that makes you lose interest is as wrong a move as you can make
23:28 jeffreykegler And in any case, if everyone avoided approaches that "experts" say is a dead end, among many other things, there would be no Marpa
23:28 jeffreykegler I sometimes joke that I know Marpa takes the best approach, but I tried all the other ones first. :-)
23:29 jeffreykegler s/but I/because I/

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