Pep is an Earley Parser. Earley parsers are chart-based and bottom-up. The Pep implementation is class-based, not a file processor like most yacc-style parsers. You create an instance of Grammar, loaded with whatever context-free grammar you want; the grammar can be used to parse (or just recognize) strings (sequence of tokens).
This parser fills out a chart based on the specified tokens for a specified seed category. Because of this, it can be used to recognize strings that represent any rule in the grammar. The parse returns a Parse object that encapsulates the completed chart, the tokens given and the seed category for that parse.
It builds an AST (actually all possible parse trees) as it goes, and sends events to notify you as nodes are added and combined.
My Fan page has a blurb about the algorithm, and a link to download the zip. The zip has the compiled pod, full source and generated Fandoc, and some examples, including a (mostly) ANTLR-ready Fan grammar. (thanks Brian, for recent updates to the grammar page)
The package has a dozen or so main classes, EarleyParser being the primary entry point, and about ten test classes which give a good picture of how to use the thing and what it can do.
I've put up version 0.2 of podlist too, btw. This now works directly with Flux -- just drop in the pod, restart Flux, and you get the Pod List pane as an option on the View menu. This is a good way to browse the Pep classes; the doc comments are pretty complete and descriptive. (I just ported; the guy (Scott Martin) that wrote the package gets kudos from me.)
Now I'm off to get an Earley start -- with the tests all green, I wanna start trying it out on Fan grammar. Cheers!
brianThu 21 May 2009
Sounds pretty cool - so are you going to try this as an Fan IDE parser?
KevinKelleyFri 22 May 2009
Yes, absolutely. It seems like it's got all the hooks I need for keystroke by keystroke response, instantaneous info on exactly what ast nodes are completed, it's even got prediction. You get an event whenever it adds a prediction edge to its chart; perfect opportunity to pop up a (for example) close brace ahead of the cursor for accepting.
Throw in some type info, and maintain a lexical scope stack for variables in scope, prediction gets way cool. It's gonna know within a few chars into any name, what it should be.
I'm thinking, use a dimmed look to show the predicted text out ahead of the cursor; when it's correct you hit the spacebar and cursor jumps ahead. If you really wanted space instead, backspace undoes the prediction.
Or another hotkey, if it turns out that gets in the way.
KevinKelley Thu 21 May 2009
I have just finished a port of PEP to Fan.
Pep is an Earley Parser. Earley parsers are chart-based and bottom-up. The Pep implementation is class-based, not a file processor like most yacc-style parsers. You create an instance of Grammar, loaded with whatever context-free grammar you want; the grammar can be used to parse (or just recognize) strings (sequence of tokens).
This parser fills out a
chartbased on the specified tokens for a specified seedcategory. Because of this, it can be used to recognize strings that represent any rule in the grammar. The parse returns a Parse object that encapsulates the completed chart, the tokens given and the seed category for that parse.It builds an AST (actually all possible parse trees) as it goes, and sends events to notify you as nodes are added and combined.
My Fan page has a blurb about the algorithm, and a link to download the zip. The zip has the compiled pod, full source and generated Fandoc, and some examples, including a (mostly) ANTLR-ready Fan grammar. (thanks Brian, for recent updates to the grammar page)
The package has a dozen or so main classes, EarleyParser being the primary entry point, and about ten test classes which give a good picture of how to use the thing and what it can do.
I've put up version 0.2 of podlist too, btw. This now works directly with Flux -- just drop in the pod, restart Flux, and you get the Pod List pane as an option on the View menu. This is a good way to browse the Pep classes; the doc comments are pretty complete and descriptive. (I just ported; the guy (Scott Martin) that wrote the package gets kudos from me.)
Now I'm off to get an Earley start -- with the tests all green, I wanna start trying it out on Fan grammar. Cheers!
brian Thu 21 May 2009
Sounds pretty cool - so are you going to try this as an Fan IDE parser?
KevinKelley Fri 22 May 2009
Yes, absolutely. It seems like it's got all the hooks I need for keystroke by keystroke response, instantaneous info on exactly what ast nodes are completed, it's even got prediction. You get an event whenever it adds a prediction edge to its chart; perfect opportunity to pop up a (for example) close brace ahead of the cursor for accepting.
Throw in some type info, and maintain a lexical scope stack for variables in scope, prediction gets way cool. It's gonna know within a few chars into any name, what it should be.
I'm thinking, use a
dimmedlook to show the predicted text out ahead of the cursor; when it's correct you hit the spacebar and cursor jumps ahead. If you really wanted space instead, backspace undoes the prediction.Or another hotkey, if it turns out that gets in the way.
Way psyched about this thing, gonna be cool.