Re: Reducing Pegged ASTs
On Wednesday, 26 November 2014 at 06:09:12 UTC, Philippe Sigaud via Digitalmars-d-learn wrote: IIRC there is a free function in Pegged that does it. What's the name of this function? I did not automate it, because every time I cut down severely a parse tree, I later regret it because I lost information that way. Cutting while still retaining original info (who is this node's ancestor) is more difficult: you would have to store it somewhere anyhow. You cannot create node classes to represent the hierarchy, because of loops in the grammar: an Identifier can have many different ancestors. Note also that Pegged produces parse trees (complete parsing information), not ASTs. ASTs would indeed be much smaller, but we would have to define what are the master nodes in the D grammar. What do you mean with master nodes? If you want to remember the intermediate nodes you cut down, not really, since you still need to store them somehow. I don't quite understand your formulation in English here. Could you elaborate? I think what's consuming memory right now is that I duplicate the matched strings at each level What do you mean with duplicate? Doesn't Pegged use string slices that reference the original source? If this problem is related to (im)mutability and If I understand you correctly you could use something like static if (isImmutable!Source) node.text = source_text[i..j]; else node.text = source_text[i..j].idup; right? Where in Pegged could this logic be injected?
Reducing Pegged ASTs
Is there a way to (on the fly) reduce Pegged parse results such as C [0, 6][int, x, ;] +-C.TranslationUnit [0, 6][int, x, ;] +-C.ExternalDeclaration [0, 6][int, x, ;] +-C.Declaration [0, 6][int, x, ;] +-C.DeclarationSpecifiers [0, 4][int] | +-C.TypeSpecifier [0, 4][int] +-C.InitDeclaratorList [4, 5][x] +-C.InitDeclarator [4, 5][x] +-C.Declarator [4, 5][x] +-C.DirectDeclarator [4, 5][x] +-C.Identifier [4, 5][x] to C [0, 6][int, x, ;] +-C.TranslationUnit [0, 6][int, x, ;] +-C.ExternalDeclaration [0, 6][int, x, ;] +-C.Declaration [0, 6][int, x, ;] +-C.TypeSpecifier [0, 4][int] +-C.Identifier [4, 5][x] and still, when needed, be able query that C.Identifier is an instance of C.DirectDeclarator etc? If not this seems like a cool feature to have ;) I guess it would reduce memory requirements by about a magnitude right?
Re: Reducing Pegged ASTs
On Tuesday, 25 November 2014 at 15:12:39 UTC, Nordlöw wrote: I guess it would reduce memory requirements by about a magnitude right? Correction: For consistency we probably want this example to be reduced to +-C.Declaration [0, 6][int, x, ;] +-C.TypeSpecifier [0, 4][int] +-C.Identifier [4, 5][x]
Re: Reducing Pegged ASTs
On Tuesday, 25 November 2014 at 15:15:40 UTC, Nordlöw wrote: +-C.Declaration [0, 6][int, x, ;] +-C.TypeSpecifier [0, 4][int] +-C.Identifier [4, 5][x] Correction again: +-C.Declaration [0, 6][int, x, ;] +-C.TypeSpecifier [0, 4][int] +-C.Identifier [4, 5][x]
Re: Reducing Pegged ASTs
On 2014-11-25 10:12, Nordlöw wrote: Is there a way to (on the fly) reduce Pegged parse results such as I've made an asn.1 parser using pegged tree map, it's not so complex and does the reducing as well. https://github.com/globecsys/asn1.d Most of the meat is in asn1/generator/ In short, it's much easier when you put all the info in the same object, in this case it's an AEntity: https://github.com/globecsys/asn1.d/blob/master/asn1/generator/asntree.d#L239 When the whole tree is done that way, you can easily traverse it and move nodes like a linked list.. I've made a helper function here: https://github.com/globecsys/asn1.d/blob/master/asn1/generator/asntree.d#L10 You can see it being used here: https://github.com/globecsys/asn1.d/blob/38bd1907498cf69a08604a96394892416f7aa3bd/asn1/generator/asntree.d#L109 and then here: https://github.com/globecsys/asn1.d/blob/master/asn1/generator/generator.d#L500 Also, the garbage collector really makes it easy to optimize memory usage, ie. when you use a node in multiple places and need to re-order the tree elements. I still have a bunch of work to do, and I intend on replacing botan's ASN1 functionalities with this and a DER serialization module. Beware, the pegged structure isn't insanely fast to parse because of the recursion limits I implemented very inefficiently because I was too lazy to translate the standard asn.1 BNF into PEG.. Also, the bigger bottleneck would be error strings. For a 1-2 months of work (incl. learning ASN.1), I'm very satisfied with the technology involved and would recommend intermediate structures with traversal helpers.
Re: Reducing Pegged ASTs
On Tue, Nov 25, 2014 at 4:12 PM, Nordlöw digitalmars-d-learn@puremagic.com wrote: Is there a way to (on the fly) reduce Pegged parse results such as C [0, 6][int, x, ;] +-C.TranslationUnit [0, 6][int, x, ;] +-C.ExternalDeclaration [0, 6][int, x, ;] +-C.Declaration [0, 6][int, x, ;] +-C.DeclarationSpecifiers [0, 4][int] | +-C.TypeSpecifier [0, 4][int] +-C.InitDeclaratorList [4, 5][x] +-C.InitDeclarator [4, 5][x] +-C.Declarator [4, 5][x] +-C.DirectDeclarator [4, 5][x] +-C.Identifier [4, 5][x] to C [0, 6][int, x, ;] +-C.TranslationUnit [0, 6][int, x, ;] +-C.ExternalDeclaration [0, 6][int, x, ;] +-C.Declaration [0, 6][int, x, ;] +-C.TypeSpecifier [0, 4][int] +-C.Identifier [4, 5][x] and still, when needed, be able query that C.Identifier is an instance of C.DirectDeclarator etc? The reducing can be done, either with operators or semantic actions. IIRC there is a free function in Pegged that does it. I did not automate it, because every time I cut down severely a parse tree, I later regret it because I lost information that way. Cutting while still retaining original info (who is this node's ancestor) is more difficult: you would have to store it somewhere anyhow. You cannot create node classes to represent the hierarchy, because of loops in the grammar: an Identifier can have many different ancestors. Note also that Pegged produces parse trees (complete parsing information), not ASTs. ASTs would indeed be much smaller, but we would have to define what are the master nodes in the D grammar. If not this seems like a cool feature to have ;) I guess it would reduce memory requirements by about a magnitude right? If you want to remember the intermediate nodes you cut down, not really, since you still need to store them somehow. I think what's consuming memory right now is that I duplicate the matched strings at each level, even concatenating them at the higher levels. I should let them only in the 'leaves' of the tree (heck, like an AST). Halas, I've no free time to code anything in D these days... but of course, feel free to push any pull request you might have!
