I'm developing an AST model for a source code reverse engineering platform. My question is, should I keep parenthesis data in my AST? Because I have everything in a tree, I already know which operation will be executed first.
1 Answer
This is a fairly general question, and the right decision will depend on what kind of analysis you wish to do. When reverse engineering, I'm of the philosophy that more information is better.
Syntax Analysis
As mentioned by Igor, the C programming language parses a & 3 == 1 as a & (3 == 1), leading to a large number of bugs in code. There is nothing invalid about the code, but it is unlikely to be what the developer intended, and the syntactic pattern can be found and a warning can be given. Several compilers implement this already:
- GCC does not store parentheses in its AST, but warns about this during parsing, showing that parentheses needn't be in the AST to detect problems (see the call to
warn_about_parenthesesingcc/c-typeck.c). - Clang, on the other hand, stores the parentheses in the AST as a node called
ParenExpr. This allows for checks for common error conditions to be separated from the parser (seeDiagnoseBitwisePrecedenceinSemaExpr.cpp).
Having read both implementations, the Clang design seems preferable. The design makes it possible to add more modules that analyse the syntax of the code without modifying the parser. Clang also uses whitespace information to warn about things like x =+ 1 (as opposed to x = +1), and code origin information to prevent warnings when macros are responsible for excessive parentheses. Although that exact functionality is unlikely to be needed in any non-C-derived language, it illustrates that the more information you have in your AST, the more you can do with it.
Code Regeneration and Debugging
As mentioned by jix, discarding information about parentheses can be detrimental to the readability of code generated from your AST. Without storing information about parentheses, a code-regenerator is likely to turn x & (y == z) into x & y == z, which is both correct and confusing.
This also goes for debugging - the more closely your AST models the source code, the easier it is for you to look at your AST and see how it corresponds to the input code.
Semantic Analysis
As noted in your question, once everything is parsed into a tree, you no longer need information about parentheses to understand the semantics of your code. If this is your sole intent, then your tree will be smaller and simpler without parentheses.
Decompilers reconstruct ASTs from binary code and perform extensive analysis and transformation on them, with no knowledge about parentheses. The language's operator precedence is used to figure out where parentheses need to be put at the end of the decompilation process.
Implementation
If you wish to keep parentheses in your AST for any of the reasons mentioned above, I would use Clang's approach and add a simple node for parenthesised expressions. This probably won't add more than ten lines to any code that traverses the tree.
jix noted above that you could use a flag for grouped expressions. It should be noted that this is inadequate for expressing the valid code ((x + 5)), and is likely to encourage code-duplication by making each node responsible for printing its own parentheses (although I'm sure you can engineer around that).
a & 3 == 1.