Re: parsing, PEG parsers, and backtracking HTML templating: toward a bright parsing future (examples in OCaml, C++, and Ruby)

> if it's more trouble than it's worth to bootstrap...

In retrospect, if I've understood the DSL properly, it's easy enough  
to use a precedence climbing parser, which, being deterministic,  
sidesteps the issue completely.

Please ignore my fast, cheap, and out of control sketch; see instead  
Martin Richard's MCPL code[0] for much cleaner, saner, small OP parsers.

-Dave

[0] http://www.cl.cam.ac.uk/~mr10/mcplman.pdf
Theorem Prover, pp 57-58
Lambda Calculator, p 63

:: :: ::

LIT, VAR, JUX, ALT, SEQ, COM, LOOP = list("LVjascl")
################

E       = lambda c,n: {
         LIT:    lambda t: t[0],
         VAR:    lambda t: lookup(c,t[0]),
         JUX:    lambda t: reduce(conj,mapE(c,t),""),
         ALT:    lambda t: reduce(disj,mapE(c,t),None),
         SEQ:    lambda t: reduce(seq, mapE(c,t),""),
         COM:    lambda t: E(c,t[0]),
         LOOP:   lambda t: loop(c,t),
         }[n[0]](n[1:])

lookup  = lambda c,var: reduce(disj,[e.get(var,None) for e in kludge 
+c],None)
kludge  = [{'':[]}] # null context so var-less LOOPs substitute for DOCs
mapE    = lambda c,t: map(lambda n: E(c,n),t)
loop    = lambda c,(var,n): docomma(doloop(c,var,lbody(n)))
docomma = lambda (comma,xs):            comma.join(xs) if xs else None
doloop  = lambda c,var,(_,body,comma): (E(c,comma), [E([e]+c,body)
                                         for e in (lookup(c,var) or  
[])])
lbody   = lambda n: n if (n[0]==COM) else (COM,n,(LIT,""))
conj    = lambda x,y: x+y if (p(x) and p(y)) else None
disj    = lambda x,y: x if p(x) else y
seq     = lambda x,y: (x or "")+(y or "")
p       = lambda x:   x is not None

################

O = { '{': (lambda t,a,b: (JUX,a,(LOOP,t[1:],b)), 6,0) # BUGGY should  
be unary
     ,None: (lambda t,a,b: (JUX,a,(VAR,t),b),      5,5) # default is  
varname
     , '=': (lambda t,a,b: (EQ,a,b),               4,4)
     , '|': (lambda t,a,b: (ALT,a,b),              3,3)
     , ';': (lambda t,a,b: (SEQ,a,b),              2,2)
     , ',': (lambda t,a,b: (COM,a,b),              1,1)
     , '}': (lambda t,a,b: None,                   0,None) }

parse = lambda s:      expr(0, brack(s))[0]
brack = lambda s:      sum([seg.split('<') for seg in s.split('>')],[])
expr  = lambda p,xs:   exp1(p,((LIT,xs[0]),xs[1:]))
exp1  = lambda p,ctx:  exp1(p,next(ctx)) if p < prec(ctx) else ctx
prec  = lambda (_,xs): op(xs[0])[1] if xs else -1
op    = lambda x:      O.get(x[0],O[None])
next  = lambda (a,xs): dyad(xs[0],a, rarg(op(xs[0]),xs[1:]))
rarg  = lambda (node,_,tp),tl:     (node,)+expr(tp,tl)
dyad  = lambda tok,a,(node,b,xs):  (node(tok,a,b),xs)

################

if __name__ == "__main__":
         bibt    = "In <booktitle>.<;> <month> <year>."
         bibloop = "\n\t<{author><name><,>, <}>."
         ctx = [{ "year"      : "1381"
                , "month"     : "Farvardin"
                , "booktitle" : "Proc. of Tehran Acad. of  
Linguistics" }]
         auths = [{ "author": [{"name": "Taher Marzian"},
                               {"name": "Shahriar Afshar"}] }]
         for c in [ctx,ctx+auths]:
             for tmpl in [parse(bibt),parse(bibt+bibloop)]:
                 print E(c,tmpl) or ""


-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss