Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2017-12-19

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

All times shown according to UTC.

Time Nick Message
00:37 ronsavage joined #marpa
01:33 idiosyncrat Demat!
01:45 ronsavage joined #marpa
03:02 ilbot3 joined #marpa
03:02 Topic for #marpa is now Start here: http://savage.net.au/Marpa.html - Code paste/run: https://f.perlbot.pl/#marpa - Jeffrey's Marpa site: http://jeffreykegler.github.io/Marpa-web-site/ - IRC log: http://irclog.perlgeek.de/marpa/today - Youtube channel: https://www.youtube.com/channel/UCYKVfGBtfTqbs1JdYq-dc5g
03:03 idiosyncrat In the gist just pasted above, I include two script.  One is for the example longest-high, as amon originally had it.  The other is for the example shortest-high, to show that the method is flexible.
03:03 idiosyncrat I have not started the doc yet.  I wanted to work out the examples for it first.
03:06 idiosyncrat Very briefly (and perhaps not comprehensibly until I do the full doc) the ranking method is this.
03:07 idiosyncrat Choice points are instances of (symbol, g1_start, g1_end).  Within a choice point you have all the possible parses with that symbol, that G1 start, and that G1 end.
03:07 idiosyncrat Symbol is the token symbol for a token, the LHS for a rule.
03:09 idiosyncrat The rank of a rule is *not* that of the rule, but THE RANK OF THE RULE OF ITS MOST RECENTLY SCANNED CHILD.
03:09 idiosyncrat If you're conversant with Earley terminology, the rank of a rule instance is the rank of the rule of its predot instance.
03:11 idiosyncrat This may seem counterintuitive, but it allows ranking of rules which are different length, and ranking as scanning of a rule proceeds (that is, before it is completed).
03:12 idiosyncrat If I took the naive approach and used the rank of the actual rule of the choice itself, neither of those would be possible, and R2 ranking would be far less powerful.
03:12 idiosyncrat All of which I hope to explain more fully soon.
03:14 idiosyncrat https://gist.github.com/jeffreykegler/099d09480b50977701bcf8268576785c
03:14 idiosyncrat This method of ranking was chosen as a compromise.  R2's ASF's allow full generality in ranking.
03:15 idiosyncrat But in full generality, rule ranking can be arbitrarily expensive.
03:16 idiosyncrat I choose R2's built-in ranking to be the most powerful possible (or at least that was possible for me to think of) that had essentially zero cost.
03:16 idiosyncrat Zero cost meant no callbacks, and no recursion.
03:18 idiosyncrat So taking the rank of the predot instance was that compromise.  It's a constant and can be accessed in very fast constant time.
03:19 idiosyncrat I'd be surprised is the difference in speed between a ranked and unranked grammar is measurable when the grammar is unambiguous -- that is, when ranking is trivial.
03:20 idiosyncrat When it's non-trivial, and possibilities are eliminated by ranking, I'd expect the ranked grammar to be faster, if anything, because it does not have to process as many possible parses as the unranked one.
03:21 idiosyncrat This compromise does have downsides.  I just pasted a gist when shows an naive attempt to simplify our example by grouping the alternatives.  The result is more elegant, but it breaks R2 ranking.
03:23 idiosyncrat It break ranking because it adds a layer of indirection.  It adds <Item> ::= <Item1> | <Item2> | <Item3>, which saves typing all 3 choices in two different places.
03:24 idiosyncrat But that breaks ranking, because ranks are not evaluated recursively, so that adding a layer of indirection (which in most cases in Marpa::R2 has almost no effect) hides the rule rank -- it now becomes the rank not of the predot child, but of the child of the predot child.
22:24 ronsavage joined #marpa
23:30 idiosyncrat joined #marpa

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