From: Caleb Clausen Date: 2005-05-27T13:14:29+09:00 Subject: Re: cursor-0.6 Eric Mahurin wrote: > Funny you ask for that - cursor===regexp. Instead, my grammar > package will support grammar===cursor. I think the only case I > could fully implement cursor===regexp is when the data the > cursor is accessing is a string. I can't do it for the case > when the cursor is a IO (unless I read the whole file into a > String). Regexp is too tied to String. Also, right now, > nothing in Cursor is tied specifically to Strings (or > characters). I want to keep it that way - dealing with > elements and element sequences. > > This === pattern matching would be better placed in the pattern > matching class if it is possible - regexp=== cursor, > grammar===cursor, or reg===cursor. This is the right way, with the pattern on the left side of === and the data on the right. (I've done it the other way before, but it's yukky.) However, I still want a more sophisticated matcher built-in to Cursor, else I'm not sure how to make use of Cursors. Regexp#===(FileCursor) is just as hard as the other way around. How would that be implemented? > I provide some operator overloading to make specifying a > Grammar like BNF - "|" (Grammar::Alteration), "+" > (Grammar::Sequence), "*" (Grammar::Repeat), etc. I also put > some of these in built-in classes (String, Range) to make it > even easier (i.e. "hi"|"hello" makes a Grammar that matches > either "hi" or "hello"). I've done much the same with Reg. However, I don't mix-in these capabilites to any standard class except Regexp. (The user can always request that they be mixed in, tho, so my equivalent to your "hi"|"hello" is "hi".reg|"hello", which I admit is a bit ugly.) Are you allowing Regexps in your language? Or is the idea that users can build up Regexp-like patterns with the (equivalent) mechanisms you're supplying? Regexps are one of the few things in ruby that are actually fast; doing your own will be much slower... I suppose you could translate a Regexp into an equivalent Grammar (or Reg), but again, it will be slow. (And a lot of work.) I wish you could tell me more about Grammar (or Syntax) internals... Is it an LL or LR thang? How is matching actually done at runtime? Do you compile to a parse table? Or 'interpret' the parsing at runtime, as I am doing. My own system is Regexp-like, featuring an mostly unoptimized DFA engine. Reg::Constant makes possible recursive patterns, which makes the whole thing LL-equivalent (I think). What happens when this code runs: "foo"|"bar"|"baz"===cursor Does cursor get scanned 3 times, for "foo", then "bar", then "baz"? That's going to be slow... especially if cursor is a FileCursor. Alternation doesn't need to be so slow... you can scan until you see the first f or b, then attempt a match from there. This eliminates the need to go through the cursor's data multiple times. But I don't see support for this kind of thing in Cursor. I understand your need to keep Cursor clean desire to get on to the fun stuff, but I beg you to add this one additional feature: to read data from the cursor position until you find a member of a set of items given to you by the user. I think this capability makes possible an NFA engine atop Cursor, which should be reasonably fast. And it ought to be easy enough for you. In other words, I'd like to see Cursor#get(Set) or Cursor#get(CharSet), where which one you pass depends on the type of cursor. (This actually gets kind of complicated when it comes to objects... in addition to a Set, you'd like to be able to take a Proc too... or maybe just an object that responds to ===. > With this you can make a parser that works directly on the > Cursor (from an IO, String, etc) Please tell me how this would work, because I have never been able to envisage it properly, but I like the idea. > token = (tokenGrammar===ioCursor) > > tokenCursor = Cursor of tokens (lexer) > > parsetree = (parserGrammar===tokenCursor) > > Like the ideas? Well, yes, very much so. Actually, I'm suspecting esp again. Have you given any thought to having a Cursor into the object graph, or Cursors into graphs in general? This is related to something I want to do with Reg, but I haven't figured it out yet... Oh, and incidently, Grammar::Alteration should really be Grammar::Alternation.