Closed awalterschulze closed 10 years ago
By default PEG stores an AST in a "flat array tree" format. Each array element is a token16 or token32:
type token16 struct { /* a matched rule, {action}, <capture> */ Rule /* tree depth is being stored in next, I should probably rename this... */ begin, end, next int16 }
as the input grows the tree is converted to a token32 array:
type token32 struct { Rule begin, end, next int32 }
This is probably over optimization. An example flat array tree:
{Child, Child, Parent, Child, Child, Parent, Grand_Parent}
The grammar that produced this tree could look like:
Grand_Parent <- Parent* !. Parent <- Child* Child <- .*
Your best bet would be to convert the flat array tree into a real tree. This could probably be done by looking at the begin, end, and depth (next) as you iterate across the flat array tree. (Take a look at Tokens() in the TokenTree interface defined in bootstrap.peg.go or peg.go) A sketch of the algorithm:
An AST() function has been added.
Really cool. Thank you very much.
Hi We are trying to write a parser for a grammar that needs more lookahead than what LR(1) in http://code.google.com/p/gocc/ provides. I am pretty sure we will be able to Pegify the grammar, but I was wondering if we are able to access the parse tree in some way or is it easy to build an AST in a bottom up way in this PEG implementation?
We have really easy to use SDT rules in gocc to build up an AST in a bottom up way.
I have not used PEG before, but I have read an article and I am really amped :)
Please help, Thank you Walter Schulze