[Baypiggies] extended LL(1) parser with backtrack ?
warren at muse.com
Thu Jan 31 01:49:37 CET 2008
Hey Rick, I might have something that you can use. Not sure if it is a
true LL(1), but it uses a BNF like declaration, with recursive fixup
of forward declares. The resulting parse tree is a hierarchy of Python
dictionaries. Unfortunately, I've been too busy to clean up and post
the source. Here's an example of how I defined a domain specific
tr3 = Indent who what tpy* sibs* kids* Dedent
tpy = when | how | why
sibs = ',' tr3
kids = tr3
who = path
path = (step | name)+
name = alphanum
step = '.' | '*' | '∞' | '//'
what = (list+ | tupple )+
list = '[' branches ']'
tupple = '(' branches ')'
branches = branch (',' branches)?
branch = (path list*) | leaf | image | bindc
leaf = range | values
range = min? op max? dfault?
min = value
op = slice | cycle
slice = ':'
cycle = '%'
max = value
dfault = '=' value
values = value (','* values)?
alphanum = r'[A-Za-z0-9_]'
num = r'[0-9.]+'
value = num | alphanum | bindc | image
image = '_i_'
bindc = '_c_'
when = whenOp Indent where+
whenOp = attach | detach | increment | decrement | named | dename |
register | dereg
attach = '<<'
detach = '<!'
named = '<c
dename = '<!c'
register = '<r'
dereg = '<!r'
how = (':' Indent (where | link*) Dedent)
where = pykey | branches | parens
pykey = 'and' | 'assert' | 'break' | 'class' | 'try' | 'while' | 'yield'
parens = '(' where ')'
link = path '(' when path ')'
why = (tilde | hash | tquote)*
tilde = '~' Indent linestr* Dedent
hash = '#' linestr
tquote = r'(\"\"\")^\1+\1'
linestr = r'^\n+'
Sorry about the length of the example. To be honest, it has been a
while since I've played with this. I also have a bootstrap parser that
defines how the parsing definition will look.
What does your user see and do? How soon do you need it? Can it wait
until the next Baypiggies meeting?
On Wed Jan 30 15:09:59 2008, Rick Kwan <kenobi at gmail.com> wrote:
> I know this seems like an oxymoron, but ... before I write my own
> thing, I'm looking for an extended LL(1) parser with backtrack. (If
> "extended LL(1)" doesn't register with you, think extended BNF or
> railroad tracks courtesy of Niklaus Wirth. And if that doesn't cut
> it, you may want to ignore this message.)
> Why in the world would I want to backtrack? This is for user input,
> where the user is able to go back and give a different set of tokens
> from what was originally given.
> Of course, I'm looking for something which executes in Python. (I've
> looked at ANTLR and YAPPS2; I don't think either handles
> --Rick Kwan
> Baypiggies mailing list
> Baypiggies at python.org
> To change your subscription options or unsubscribe:
More information about the Baypiggies