Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2014-12-27

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

All times shown according to UTC.

Time Nick Message
00:04 flaviu joined #marpa
02:33 koo5 joined #marpa
02:46 koo5 joined #marpa
03:41 jeffreykegler joined #marpa
03:56 flaviu joined #marpa
04:15 koo5 joined #marpa
04:39 koo5 joined #marpa
05:29 ronsavage joined #marpa
05:33 ronsavage left #marpa
06:38 koo5 joined #marpa
07:08 koo5 joined #marpa
07:14 koo5 joined #marpa
09:52 lwa joined #marpa
12:54 LLamaRider joined #marpa
16:46 jeffreykegler joined #marpa
16:55 flaviu joined #marpa
20:48 sirdancealot joined #marpa
20:58 ronsavage joined #marpa
21:18 jeffreykegler joined #marpa
21:20 jeffreykegler I'm on to a new line of inquiry that I hope may eventually prove interesting.
21:21 jeffreykegler It was prompted by the flaviu's investigation into Marpa's space demands.
21:22 jeffreykegler The solution, which I'm outlining, is to parse in pieces, creating a subtree from each piece.
21:23 jeffreykegler Once the subtree is created, the parse data can be thrown away.
21:23 jeffreykegler Subtrees can be pieced together, using a scheme I'm working out.
21:23 * jeffreykegler is not giving a link to his current write up, because there are some flaws he needs to fix.
21:25 jeffreykegler This should make Marpa useable even for huge databases -- things like all of Wikipedia (with full history) in XML form.
21:26 jeffreykegler But it also reopens the idea of "seamless" parsing -- parsing where there is no separate lexing, even conceptually, but just a single BNF description.
21:26 jeffreykegler [ Perhaps "lexerless" is a better term than "seamless" ]
21:28 jeffreykegler Lexerless parsing is possible with Marpa as it stands, but it increases the space requirements, and piece-wise parsing will be a solution to that.
21:29 jeffreykegler And actually being able to parse in pieces, including with different grammars, opens the way to all sorts of tricks.  For example, now you could really modify the Marpa grammar on the fly -- just start a new piece when you want to add rules and/or symbols.
21:30 flaviu doesn't lexer-less parsing also impose a speed overhead? Marpa would be doing work a optimized lexer could do much more quickly.
21:31 jeffreykegler flaviu: yes, that's correct, but ...
21:31 jeffreykegler the arguments in my post on "Is Earley parsing fast enough" apply here ...
21:32 jeffreykegler But, if it really is a lexing problem, like finding all the links in HTML, where you don't need to determine the structure of the HTML, just lex it.
21:33 jeffreykegler The lexer-driven solution will be faster -- only by a constant, but in the problem is really simple, why take extra time for no gain?
21:34 jeffreykegler The advantage of lexerless grammars in some contexts, it that they are fully composable.
21:34 jeffreykegler Marpa grammars are also fully composable, but that's only assuming the lexing in the two is the same or at least compatible.
21:36 jeffreykegler Composability is already used in Marpa a lot -- when you steal SLIF to do C-style comments from another grammar, and expect that to work, you're using composability.
21:37 jeffreykegler Composability is another of those features that folks take for granted everywhere else except parsing.
21:37 flaviu I can see the use of composable grammars. Just to make certain, lexerless parsing is not an integral part of of the subtree parsing technique, correct?
21:37 jeffreykegler It's a potential application.
21:37 jeffreykegler Not an intergral part.
21:38 jeffreykegler Subtree parsing is just parsing in pieces, creating subtrees and putting them together at some convenient point.  It's simple except for figuring out how to make that actually work smoothly. :-)
21:40 jeffreykegler Once I do have the details ironed out a bit, ...
21:40 jeffreykegler someone could look into it by trying to make the technique work on a specific case, such as a JSON parser.
21:42 jeffreykegler The base theoretical insight I got from Grune & Jacobs, who point out that the suffix of any context-free grammar is a context-free grammar, and show how to write a suffix grammar ...
21:42 jeffreykegler that's many details away from how to parse piecewise and reassemble the pieces, but it was a big start.
21:43 ronsavage Is this new work an update to Marpa::R2 or a separate module, or only in Kollos?
21:44 jeffreykegler It's a concept -- so you could do it using the SLIF, but it will never be built into Marpa::R2
21:45 jeffreykegler I don't know what I'll do with Kollos, it reopens the issue of Kollos' lexing and evaluation strategy.
21:47 jeffreykegler And for those willing to implement directly in Libmarpa, the technique can be applied to a specific grammar, to build a parser which can parse arbitrarily large files in limited memory.
21:54 ronsavage Thanx. I was worried about the stability of Marpa::R2 if much complexity was going to be added, but somehow I did not expect you to add it to Marpa::R2 - but I had to ask!
21:54 jeffreykegler ronsavage: Good question, thanks
21:56 jeffreykegler I'm aware that in a sense Marpa has the problem that the Emperor complains to Mozart about in Amadeus: "Too many notes!"
21:59 jeffreykegler But I think this technique might be useful in, for example, some of the applications Jean-Damien has looked at.
22:03 jeffreykegler Ruminating a bit ---
22:04 jeffreykegler There seem to be some areas where programmers are eager for new ideas -- the more the better -- so much so that time & effort gets lost with over-experimentation.
22:05 jeffreykegler New approaches to object-oriented are one of these areas.
22:06 jeffreykegler Threading is an another.
22:08 jeffreykegler In parsing, however, it's the opposite -- there is a very little tolerance for any new approach to parsing.
22:09 jeffreykegler The interest in combinator parsing is not an exception to this rule -- it's amount to trying to make left parsing interesting by viewing it as a form of functional programming.
22:09 jeffreykegler * it's amount -> it amounts
22:31 ronsavage We may no hear from Jean-Damien for a while! http://www.abc.net.au/news/2014-12-28/snowfall-in-french-alps-leaves-15000-drivers-stranded/5990120
22:31 ronsavage 'no' -> 'not'.

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