Generate an AST

[seantalts]

I'm looking for a C++ parsing library that will easily let me generate an AST. I saw #20 and that seemed close, but I don't care if the grammar is read in at runtime or compile-time. I've had good experiences building compilers in other languages separating out parsing, type checking, and semantics into separate stages that all operate on a (sometimes decorated) AST. Is this something planned?

[d-frey]

The issue you've seen was more about generating a grammar at run-time, which is why we closed it as "wont-fix". For the AST, we made some experiments and the result is included in the examples. It's already quite powerful, but we are not sure about the interface's stability. You could give it a try and we'd be happy to receive some feedback, if there are any issues please let us know as well and we can try to improve it.

[ghost]

Would love to see the interface become more stable. I am currently experimenting with it and it is really useful. Maybe adding source location info would be a next step?

[d-frey]

@samvv It does contain the source location, the example is printing it out in the print_node function. It does not contain the source name currently (e.g. the filename you are parsing), as this would probably be quite inefficient if I would store a std::string in each node. And storing a const char* seems too dangerous as nested parsing of different sources (think #include) could run into lifetime issues. But the position (line/column) is already available. If you really need to store the source name, we probably need to accept the overhead - maybe I could conditionally enable it at compile time so you could choose. Do you need it?

[ghost]

Whoops my bad, I went over it too quickly. But yes in fact that would be required ... I'm thinking of how Clang does it with a FileID wich, I guess, is an integer pointing into some kind of simple hash table. Not sure it would be a fit solution for PEGTL, just dropping it here.

Conditionally enabling at compile-time sounds like a good solution for now 👍

[d-frey]

@samvv I've decided to keep it simple for now and simply added the source. Changing the source handling from a string to an ID sounds interesting, but it will be a 3.0-thing as it'll break the existing API, we'll consider it another time. And for the efficiency, there are even better ways than separately storing the file ID, line, column and byte, for now this is beyond the 2.x-scope.

Note that for matches that store a range, we only store the source once - the one active at the begin of the match. I hope this is good enough for you?

[ghost]

That's perfect, thanks for being so quick! 😃

[d-frey]

FYI: I just refactored the parse tree support and added some initial documentation. Let me know if you have any questions, remarks, etc.

[skyrich62]

I've added a new repo: https://github.com/skyrich62/stringID, which maps unique strings onto integers. It's header only and doesn't require hashing. The interface is simple:

   auto id = stringID::from_string("foo");
   std::cout << id.name();

This class can be used to easily store filenames as a stringID, (which is only the size of a size_t), and easily reconstruct the original filename again.

[ghost]

@skyrich62 Cool, thanks for the tip! I really don't know if it is the best method for this project, but it to me personally it certainly sounds something worth giving a shot.

A short note, though. You seem to be using <map> instead of <unordered_map>. I think this can lead to some performance issues in the case of many strings being added. Was this intentional? Other than that, it looks really useful.

[skyrich62]

@samvv Hi. I thought that the number of strings, (filenames in this case), would be fairly small. But if unordered_map makes more sense to you, by all means use that. :) I use this technique in my work, and the performance really isn't a problem.

[ColinH]

Since this thread of discussion seems to have petered out, and we have since added some parse tree support, we are closing this issue.

Feel free to open a new one if there are any questions to the current state of the parse tree support and/or suggestions on how to further improve on it.