Perl 6 - the future is here, just unevenly distributed

IRC log for #marpa, 2015-06-09

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

All times shown according to UTC.

Time Nick Message
00:00 Cheery want an IDE? rewrite parser
00:00 Cheery want some auto documentation? rewrite parser
00:01 jeffreykegler Going over to Marpa requires re-visualizing the grammar in declarative terms
00:01 Cheery want XXX related to your syntax? rewrite parser
00:01 jeffreykegler speaking of parsing, I'm not sure what the internal question mark in the last 3 sentences conveys -- were those questions?
00:01 Cheery yeah. I'm at fortunate point that I can still change the syntax and semantics.
00:02 Cheery they were kind of condition? action required to fullfill condition
00:03 jeffreykegler Ron savage uses Marpa in a kind of middle way -- he makes it half declarative, half procedural by using the event mechanism
00:05 Cheery it can be this is going to be all right.
00:05 jeffreykegler I created the event mechanism to allow you to use both Marpa's native declarative logic, but also to stop and start processing, inserting your own logic.
00:05 jeffreykegler Ron likes this way of doing things, and has created several examples.
00:05 jeffreykegler I prefer staying as declarative as possible ...
00:06 jeffreykegler if you don't mix declarative and procedural in the right way, you get the worst of both worlds, instead of the best.
00:07 jeffreykegler But my focus on declarative is unusual these days -- I tend to see things like significant whitespace and line-oriented languages as symptoms, instead of techniques.
00:08 jeffreykegler And I think like they did in the 70's when ALGOL and Pascal were created, ...
00:08 jeffreykegler when they thought of languages in terms of their BNF.
00:08 Cheery they can very well be symptoms. I tried to build up projective editor before this round of studying parsers
00:09 jeffreykegler By way of encouragement, in tackling these issues you are being a pioneer.
00:10 jeffreykegler BNF, for actual use, is almost forgotten these days, so it's like it has to be rediscovered all over again.
00:11 Cheery it can be I may still try to build a projective editor some day, but I'll probably apply the stuff learned from marpa
00:12 jeffreykegler I think the key insight into Marpa, which may need emphasizing, it that you *actually get the grammar you declare* ...
00:13 jeffreykegler and to make effective use of Marpa, you have to take advantage of that.
00:13 jeffreykegler Rec decscent and friends don't scale because you don't actually know what the grammar is that you are parsing ...
00:13 jeffreykegler which makes it hard to figure out how to extend/expand the parser.
00:14 Cheery I'm not sure how you mean that. but I read one of posts about how you avoided having significant whitespace or ending markers
00:14 jeffreykegler What I mean is that you *actually get the grammar in the BNF*,
00:15 jeffreykegler while in rec descent (or worse PEG) you do not get the implied grammar -- you get if you are lucky something close enough to what you intended, perhaps after some hackery.
00:16 Cheery well in PEG it's obvious it's putting the user to harms way.
00:16 jeffreykegler But that means in Marpa you have to think out the BNF, if you are going to make effective use of it.
00:16 Cheery PEG arbitrarily chooses one meaning
00:16 Cheery I've been actually bitten by that in coffeescript few times
00:16 jeffreykegler By the way, a warning about using Marpa events ...
00:17 jeffreykegler They allow full use of procedural logic, plus with Marpa helping to understand where you are in the parse, but ...
00:17 jeffreykegler events take place *as the parse proceeds*, while
00:17 Cheery but i don't understand how the "you actually get the grammar you declare" applies to LR parsing?
00:18 jeffreykegler actions *take place afterwards*, so mixing this is very tricky.
00:18 Cheery oh that's obvious
00:18 jeffreykegler LALR/yacc is another tool which may or may not deliver what you've described in the BNF.
00:19 jeffreykegler The good news with LALR/yacc, is that it delivers for a wider class of grammars ...
00:19 jeffreykegler the bad news is that when it does not deliver (and in practice it usually does not) it tends to give you not a clue as to why ...
00:20 Cheery and the answer is you use events to extend what is described. "red lamb is on the street?, we may shift with this symbol"
00:20 Cheery whereas actions are things you take after the parse is understood
00:20 jeffreykegler and the two require very careful planning if you want to mix them.
00:21 Cheery I guess if you mix, you will use events to annotate or craft tokens
00:21 jeffreykegler IIRC Ron just gives up on actions, and does it all with events,.
00:21 jeffreykegler Yes, that's how I do it.  I use events to fine-tune the tokens,
00:21 Cheery I suppose.. LR(1) is kind of equivalent to just having events. it does decisions while parsing the input
00:21 jeffreykegler and try to delay all the real work of the semantics to the actions.
00:22 Cheery and that may be why I so often require extracting additional meaning after parsing.
00:22 Cheery (lisp style of reading input)
00:23 Cheery that is. LR doesn't finish the job.
00:23 jeffreykegler Ron has pioneered a different approach to Marpa -- he does everything he can in the events, which does mean he has to be extra careful about ambiguity.
00:23 Cheery I suppose I understand that.
00:24 jeffreykegler I am glad to see people trying different approaches myself, but my own parsers favor a declarative approach.
00:25 jeffreykegler This makes natural sense for the author of Marpa, because Marpa is about bringing the declarative element back into parsing, so naturally its author would have a declarative bias.
00:26 Cheery in LR I have a problem that although I've studied it a lot, I manage to produce rules that cause conflicts, and solving those conflicts require lot of effort.
00:26 Cheery although the language you possibly defined isn't ambiguous as such.
00:26 jeffreykegler Cheery: btw have you ever read my "timeline" blog post?
00:26 Cheery I may have, but I can't know.
00:27 Cheery LR(1) parsing gives me quite lot similar experience as using haskell, sort of.
00:27 Cheery or C.
00:27 jeffreykegler Anyway, the kind of problem you encounter with LR has driven the people who pioneered it to turn their backs on it.
00:27 Cheery it forces to coerce a nice model into something else, to get it pass through
00:28 ronsavage I'll use 'actions' have as Marpa means actions. So far I have avoided mixing events and actions in a simple BNF, although I often ponder its applicability. I do use actions sometimes, and they are quite neat, but usually I feel more comfortable with events. And the latter mean complexity as Jeffrey says, but allow me more find-tuned access to the flow of tokens coming out of Marpa.
00:28 Cheery yeah. I suppose after you get hit by that few times, any advantage over just writing a hand written parser is lost.
00:28 jeffreykegler The flagship C compiler (now GCC), Ken Thompson and Larry Wall, the very people who were LALR's top users, have given it up.
00:29 ronsavage What's amazing about Marpa is the very fact that we have a choice. What other parsing technology offers that?
00:30 Cheery jeffreykegler: this: http://blogs.perl.org/users/jeffrey_kegler/2014/09/parsing-a-timeline.html ?
00:30 jeffreykegler Cheery: yes -- I was going to give you the link, but you beat me to it
00:32 Cheery I'm not exactly sure how to implement events into my system, but I guess I'll implement something that lets me specify additional conditions.
00:32 jeffreykegler That has been my most popular blog post, btw, by far -- it's even been translated into Russian.
00:33 Cheery then I'll add that direct interpretation from the parsing structure, and see what I can do with it.
00:34 Cheery hm. I'm not even sure how this compares to marpa btw. But's it looks like this now: https://bpaste.net/show/95efd960a0bf
00:34 Cheery there are several entry points that are covered by others. the one in use is using custom tokenizer not present.
00:35 Cheery if you comment the excess entry points off, it should run in any python interpreter.
00:37 jeffreykegler wildly guessing, it may be a chart parser.
00:37 Cheery well, marpa is sort of a chart parser too?
00:38 Cheery anyway it's present if you get curious.
00:38 jeffreykegler People use the term "chart parsing" in different ways.
00:39 jeffreykegler I use it to mean a kind of generalization of Jay Earley's dynamic programming technique -- more flexible, more powerful, but slower.
00:39 jeffreykegler People sometimes say the Earley parsing (and Marpa is an Earley parser) is chart parsing ...
00:40 jeffreykegler that's OK but it reverses the historical order.
00:41 jeffreykegler Chart parsing is really cool, but it is slower and it also has the same disadvantage as rec decscent -- each parser must be hand-written -- it is not syntax driven.
00:41 jeffreykegler I have hopes for Marpa in doing NLP, but chart parsing may beat Marpa out on that.
00:43 Cheery one thing I've considered for a while is to embed this kind of parser into GUI
00:43 jeffreykegler A big advantage of Marpa is that it is a canned, mathematical algorithm -- it could be put on a chip for example, which you could never do with recursive descent, because RD is not strictly an algorithm, but a technique.
00:44 Cheery http://en.wikipedia.org/wiki/Inverse_parser
00:45 Cheery I suppose, if I get inspired from vim and that, it might lead to something interesting.
00:45 jeffreykegler Patented, it says.
00:47 Cheery who knows if it's expired already
00:47 Cheery that's an old thing.
00:51 Cheery ohwell
00:51 Cheery getting to sleep
00:51 Cheery I'll try to get the adjustments to my parser tomorrow, and test it sometime during this week.
02:31 koo6 joined #marpa
05:35 ronsavage joined #marpa
05:51 jeffreykegler joined #marpa
06:45 jeffreykegler joined #marpa
07:36 jeffreykegler joined #marpa
07:43 jeffreykegler joined #marpa
08:52 lwa joined #marpa
10:52 ronsavage joined #marpa
16:02 jeffreykegler joined #marpa
17:44 Cheery I wonder. could marpa be used for incremental parsing?
17:45 Cheery or algorithms behind
17:46 Aria Yeah, you can feed it tokens as they arrive. Though you can't get a useful AST unless you're at certain points in the grammar, and even then I think it kills adding further tokens.
17:47 Cheery I mean incremental in another way
17:48 Cheery http://lakhin.com/projects/papa-carlo/demo/
17:50 Cheery such as parsing structures when they arrive.
17:51 Cheery by the user modifing them into the file
17:54 Aria Mmmm. That's tricky!
17:54 Cheery it is. :)
17:54 Aria Probably a better chance of it in marpa than others but I bet it'd take deep mods.
17:55 Cheery it's okay. I wonder if it's possible modification for earley parsing.
17:58 Aria I think so. A change might cascade out and invalidate every further parse table.
17:58 lwa joined #marpa
17:59 Aria But if you ran the parser until the state matched the existing ones, I bet you could stop there.
18:02 Cheery there's probably some earley related papers that would apply.
18:02 Cheery and yeah, the changes would probably cascade
18:03 Aria I think in a lot of practical cases, it won't. And if you know the scope of the change before hand, you can control it.
18:03 Cheery the parser I shown works by recognizing invariant parts. But I also saw one implemented on LR that didn't do that
18:08 Aria Yeah. That's how I'd go about it.
18:08 Aria I've thought about this a bunch, actually, because I want to bolt a parser to an editor.
18:08 Aria Open source software that really understands written code.
18:12 Cheery I keep wondering which way I'd  go about this.
18:17 Cheery how marpa events happen to work?
18:18 Cheery I noticed, adding conditions in the way I thought would require me to replace a hash table with list in my implementation
18:23 Aria Yeah. I don't know Marpa's implementation quite well enough to speak to it. I've been working on my own and coming to grips with the limits and implications of how it works
18:33 Cheery https://bpaste.net/show/557dfa7496a5
18:33 Cheery on the line 33
18:34 Cheery my engine collects those into conditions.
18:35 Cheery they consume a token if succeeded
18:35 Aria ... Whoa. This code could almost be run by my parser.
18:36 Aria The rule definition syntax is identical.
19:34 Cheery theoretically all my nonterminals are also valid terminals
19:42 Cheery the implications could reason another try at structure editing
19:47 Cheery consider for a moment that instead of disallowing ambiguity, you would implement a system that builds up structures from what user writes, and resolves ambiguity by probabilities there, unless user describes he means for another than proposed
19:48 Aria I'd love to play with such a thing
19:49 Cheery I know a mechanism to construct a spreadsheet -like array of cells for that kind of use
19:49 Cheery and editing f or it
20:12 Cheery but my last structure editor is probably still too far away in design, that I could just simply try it out on that.
20:13 Cheery interesting btw.. I can also use conditions as nonterminals
20:14 Cheery Now I have everything in my parser ready for parsing the input language I designed.
20:16 Cheery to use it in my language I'd have to rewrite it in rpython, but it doesn't easily coerce into rpython model.
20:16 Cheery maybe requires me to reimplement it in that language.
20:18 Cheery the traversal approach I took allows me to neatly construct error reports that broadly references the ambiguous site.
20:19 Cheery basically it reads out entire span for structures before proceeding with it
20:19 Aria Nice!
20:20 Cheery if it finds multiple, it stops.
20:20 Cheery at the same time it halts the already started compiling stage
20:24 Cheery I wondered a bit about that structure editing concept
20:24 Cheery figuring I may have enough knowledge and theory behind to construct the design on paper entirely, before attempting to implement it.
20:41 Cheery yay
20:42 Cheery space sensitivity for any symbol. :)
20:43 Cheery and practical extensibility, long as the language stays consistent
20:56 Cheery but got two bugs. First one is that my chainer doesn't reconstruct right recursive constructs
20:56 Cheery and my table builder handles right recursives with empty rules wrong.
21:12 ronsavage joined #marpa
21:14 Cheery ohman. optimizing right recursion prevents my method of constructing the chain.
21:19 jeffreykegler joined #marpa
21:20 jeffreykegler Cheery: re modifying grammars ...
21:20 Cheery listening
21:20 jeffreykegler you might consider simply creating new grammars from scratch -- this may be fast enough for an editor
21:21 jeffreykegler The grammar creation code is in C within Libmarpa
21:21 jeffreykegler I hope Kollos will have grammar-modification capabilities, but you wouldn't be seeing those very soon.
21:23 jeffreykegler have to run -- AFK
21:44 Cheery hmm. freaky.
21:45 Cheery found a possible culprit. for some reason I had written in "if parent == i: continue" into the stepper
21:45 Cheery I no longer remember why.
21:46 Cheery but now the thing produces reductions that are impossible, and claiming them as ambiguity
21:58 Cheery well.
21:58 Cheery managed to remove those, with a cost of introducing bit of complexity
22:00 Cheery I will package this and wonder later about that all..
22:00 Cheery especially annoyed a bit that I didn't manage to retain the right recursion elimination
22:01 Cheery I'll try to fix it later.
22:34 ronsavage joined #marpa

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