5

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.

  • 2
    I think it might be useful if you do static analysis, e.g. to detect common operator priority mistakes, like a & 3 == 1. – Igor Skochinsky Mar 22 '13 at 10:56
  • 1
    It can also be useful when you want to convert ASTs back into source code, to get more readable code. It might make sense not to introduce a parenthesis AST node though, as it would make code working on the AST that doesn't care about them more complex. Adding a parenthesis flag to expression AST nodes seems to be the better option to me, it can be ignored by parts that do not care about them. It can also be retrofitted or removed without having to restructure everything. – jix Mar 22 '13 at 11:21
  • @jix but on the other hand you can regenerate parenthesis following the language rules. This will also produce the code with no unnecessary or missing parenthesis. Thou it may affect readability – Uko Mar 22 '13 at 11:58
  • Yes my point was about readability. – jix Mar 22 '13 at 12:21
  • 3
    This is more a question about how best to model an AST, than it is a question about reverse engineering. – Jesper.Reenberg Mar 22 '13 at 14:30
5

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_parentheses in gcc/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 (see DiagnoseBitwisePrecedence in SemaExpr.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).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.