[Baypiggies] extended LL(1) parser with backtrack ?

[Warren Stringer]

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  
language:

"""
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   = '<!'
increment= '<+'
decrement= '<-'
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?

Cheers,

Warren


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
> backtracking.)
>
> --Rick Kwan
> _______________________________________________
> Baypiggies mailing list
> Baypiggies at python.org
> To change your subscription options or unsubscribe:
> http://mail.python.org/mailman/listinfo/baypiggies
>



\~/

Warren Stringer
www.muse.com
Voice: 408-497-4747