Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2014-05-09

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

All times shown according to UTC.

Time Nick Message
00:08 jalvo \quit
04:28 ronsavage joined #marpa
04:57 jdurand joined #marpa
04:58 jdurand Re http://irclog.perlgeek.de/marpa/2014-05-08#i_8697867 - well done - this technique is used as well in the C grammar to ignore C++style comments, c.f. https://github.com/jddurand/MarpaX-Languages-C-AST/blob/master/lib/MarpaX/Languages/C/AST/Grammar/ISO_ANSI_C_2011.pm#L1357
06:26 ronsavage joined #marpa
07:37 ronsavage joined #marpa
09:12 ronsavage joined #marpa
15:35 jeffreykegler joined #marpa
16:44 jdurand joined #marpa
17:47 jeffreykegler The following concerns a detail of Marpa implementation of limited immediate practical interest, but will does have a significant impact on the Libmarpa implementation: cycles
17:48 jeffreykegler A cycle is a case where a grammar's symbol derives exactly itself: A ::= A is a rule that causes a direct cycle.   Cycles can also be indirect:
17:48 jeffreykegler A ::= B  B ::= C  C ::= A
17:49 jeffreykegler The SLIF currently bans cycles -- they're a fatal error but Libmarpa allows them.
17:50 jeffreykegler Earley-based recognizers have never had a issue with cycles.
17:50 jeffreykegler In the parsing (bocage creation) and evaluation, Marpa eliminates them if they're not productive (don't match any input) and prunes them back so they don't repeat if they do match input.
17:52 jeffreykegler I plan to change this approach, so that cycles are eliminated at grammar rewrite time -- the effect will be the same, but it will be accomplished with a grammar rewrite, rather than by catching the cycle during the bocage and evaluation phases.
17:53 yxhuvud I suppose the suppose the good part of AH is that they simply put cycles in a single state and is then ignores them
17:53 jeffreykegler The motive is to reduce the amount of complicated code needed for creating the parse trees, and for evaluation.
17:53 yxhuvud (though yes, I know you have stopped using AH state machines)
17:53 jeffreykegler yxhuvud: No, the LR(0) states didn't affect the issue one way or the other.
17:54 yxhuvud hmm
17:54 yxhuvud right, I was confused.
17:55 yxhuvud each rule will only be added once anyhow.
17:55 jeffreykegler It's easy to think they might help, but they don't really.
17:55 yxhuvud (per starting position, but that is the same in this case)
17:56 jeffreykegler Predictions states do collect cycles, but that savings just wasn't worth it.
17:57 jeffreykegler yxhuvud: I ran numbers on the AH/LR(0) issue by the way, and posted them to the mailing list.
17:57 yxhuvud oh? I might have missed that
18:00 jeffreykegler I thought I posted them to the mailing list.  I find this, with a lot of discussion, but no numbers: https://groups.google.com/forum/#!msg/marpa-parser/Nmem6JCes-A/O7blJqwaDRMJ
18:01 jeffreykegler Correction -- it does have the number.  I got them for Perl, HTML and C parsers.
18:01 jeffreykegler That was before COBOL emerged as the hot new language. :-)
18:07 yxhuvud heh
18:12 yxhuvud how big things have you tried to parse?
18:13 jeffreykegler yxhuvud: You're asking re the LR(0) state numbers
18:13 jeffreykegler ?
18:14 yxhuvud no, size of input given reasonably complex grammars. (ie html oslt)
18:14 jeffreykegler It's a matter of counting LR(0) states, so input size is not relevant
18:15 yxhuvud how many ends up expanded? Yes, I suppose so.
18:15 yxhuvud or entered into a position set, rather.
18:16 jeffreykegler Or at least I did not treat is as relevant. :-)
18:17 jeffreykegler I suppose you could run more careful numbers looking at the actually frequency of usage of the various states, but from just looking at the LR(0) state set, the message seemed to me dramatically clear.
21:10 sivoais joined #marpa

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