{"id":1932,"date":"2019-06-06T14:35:40","date_gmt":"2019-06-06T13:35:40","guid":{"rendered":"https:\/\/rosetta.vn\/short\/?p=1932"},"modified":"2019-06-06T14:35:40","modified_gmt":"2019-06-06T13:35:40","slug":"deciphering-python-how-to-use-abstract-syntax-trees-ast-to-understand-code-%c2%b7-matt-layman","status":"publish","type":"post","link":"https:\/\/rosetta.vn\/short\/2019\/06\/06\/deciphering-python-how-to-use-abstract-syntax-trees-ast-to-understand-code-%c2%b7-matt-layman\/","title":{"rendered":"Deciphering Python: How to use Abstract Syntax Trees (AST) to understand code \u00b7 Matt Layman"},"content":{"rendered":"

M\u1ed9t \u0111o\u1ea1n ch\u01b0\u01a1ng tr\u00ecnh Python \u0111\u01b0\u1ee3c parse ra d\u1ea1ng abstract syntax tree (AST), l\u00e0 c\u1ea5u tr\u00fac bi\u1ec3u di\u1ec5n ch\u01b0\u01a1ng tr\u00ecnh, \u0111\u1ec3 tr\u00ecnh th\u00f4ng d\u1ecbch c\u00f3 th\u1ec3 ph\u00e2n t\u00edch v\u00e0 th\u1ef1c thi c\u00e1c l\u1ec7nh.<\/p>\n

Xem th\u00eam: https:\/\/docs.python.org\/3\/library\/ast.html<\/a><\/p>\n

G\u00f3i astor gi\u00fap chuy\u1ec3n t\u1eeb Python code sang Python’s AST v\u00e0 t\u1eeb AST sang Python: https:\/\/astor.readthedocs.io\/en\/latest\/<\/a><\/p>\n

L\u01b0u \u00fd: m\u1ed7i phi\u00ean b\u1ea3n Python c\u00f3 th\u1ec3 c\u00f3 c\u1ea5u tr\u00fac AST kh\u00e1c nhau. M\u1ed7i ng\u00f4n ng\u1eef l\u1eadp tr\u00ecnh khi \u0111\u01b0\u1ee3c bi\u00ean d\u1ecbch th\u00ec tr\u00ecnh bi\u00ean d\u1ecbch c\u0169ng d\u00f9ng c\u1ea5u tr\u00fac AST n\u00e0o \u0111\u00f3.<\/p>\n

—<\/p>\n

Let\u2019s get a little \u201cmeta\u201d about programming.<\/p>\n

How does the Python program (better know as the interpreter) \u201cknow\u201d how to run your code? If you\u2019re new to programming, it may seem like magic. In fact, it still seems like magic to me after being a professional for more than a decade.<\/p>\n

The Python interpreter is not magic (sorry to disappoint you). It follows a predictable set of steps to translate your code into instructions that a machine can run.<\/p>\n

At a fairly high level, here\u2019s what happens to your code:<\/p>\n

    \n
  1. The code is\u00a0parsed<\/em>\u00a0(i.e., split up) into a list of pieces usually called\u00a0tokens<\/em>. These tokens are based on a set of rules for things that should be treated differently. For instance, the keyword\u00a0if<\/code>\u00a0is a different token than a numeric value like\u00a042<\/code>.<\/li>\n
  2. The raw list of tokens is transformed to build an Abstract Syntax Tree, AST, which is the subject we will explore more in this post. An AST is a collection of nodes which are linked together based on the grammar of the Python language. Don\u2019t worry if that made no sense now since we\u2019ll shine more light on it momentarily.<\/li>\n
  3. From an abstract syntax tree, the interpreter can produce a lower level form of instructions called bytecode. These instructions are things like\u00a0BINARY_ADD<\/code>\u00a0and are meant to be very generic so that a computer can run them.<\/li>\n
  4. With the bytecode instructions available, the interpreter can finally run your code. The bytecode is used to call functions in your operating system which will ultimately interact with a CPU and memory to run the program.<\/li>\n<\/ol>\n

    Many more details could fit into that description, but that\u2019s the rough sketch of how typed characters are executed by computer CPUs.<\/p>\n

    ASTs as analysis tools<\/h2>\n

    By the time your source code is turned into bytecode, it\u2019s too late to gain much understanding about what\u00a0you<\/em>\u00a0wrote. Bytecode is very primitive and very tuned to making the interpreter fast. In other words, bytecode is designed for computers over people.<\/p>\n

    On the other hand, abstract syntax trees have enough structured information within them to make them useful for learning about your code. ASTs still aren\u2019t very people friendly, but they are more sensible than the bytecode representation.<\/p>\n

    Because Python is a \u201cbatteries included\u201d language, the tools you need to use ASTs are built into the standard library.<\/p>\n

    The primary tool to work with ASTs is the\u00a0ast<\/code>\u00a0module. Let\u2019s look at an example to see how this works.<\/p>\n

    ast<\/code>\u00a0by example<\/h2>\n

    Below is\u00a0the example Python script<\/a>\u00a0that we\u2019ll use. This script answers the question of \u201cwhat modules were imported?\u201d<\/p>\n

    \n
    import<\/span> ast\r\nfrom<\/span> pprint import<\/span> pprint\r\n\r\n\r\ndef<\/span><\/span> main<\/span><\/span>()<\/span>:<\/span>\r\n    with<\/span> open(\"ast_example.py\"<\/span>, \"r\"<\/span>) as<\/span> source:\r\n        tree = ast.parse(source.read())\r\n\r\n    analyzer = Analyzer()\r\n    analyzer.visit(tree)\r\n    analyzer.report()\r\n\r\n\r\nclass<\/span><\/span> Analyzer<\/span><\/span>(ast<\/span><\/span>.<\/span><\/span>NodeVisitor)<\/span>:<\/span>\r\n    def<\/span><\/span>__init__<\/span>(self)<\/span>:<\/span>\r\n        self.stats = {\"import\"<\/span>: [], \"from\"<\/span>: []}\r\n\r\n    def<\/span><\/span> visit_Import<\/span><\/span>(self, node)<\/span>:<\/span>\r\n        for<\/span> alias in<\/span> node.names:\r\n            self.stats[\"import\"<\/span>].append(alias.name)\r\n        self.generic_visit(node)\r\n\r\n    def<\/span><\/span> visit_ImportFrom<\/span><\/span>(self, node)<\/span>:<\/span>\r\n        for<\/span> alias in<\/span> node.names:\r\n            self.stats[\"from\"<\/span>].append(alias.name)\r\n        self.generic_visit(node)\r\n\r\n    def<\/span><\/span> report<\/span><\/span>(self)<\/span>:<\/span>\r\n        pprint(self.stats)\r\n\r\n\r\nif<\/span> __name__ == \"__main__\"<\/span>:\r\n    main()<\/code><\/pre>\n<\/div>\n
    This code does a couple of major things:<\/p>\n
      \n
    1. Transforms a Python file\u2019s text (in this case, the example code itself) into an abstract syntax tree.<\/li>\n
    2. Analyzes the AST to extract some information out of it.<\/li>\n<\/ol>\n
      You can run this code as:<\/p>\n
      \n
      $ python3 ast_example.py\r\n{'from'<\/span>: ['pprint'<\/span>], 'import'<\/span>: ['ast'<\/span>]}<\/code><\/pre>\n<\/div>\n
      Transform to AST<\/h3>\n
      \n
      with<\/span> open(\"ast_example.py\"<\/span>, \"r\"<\/span>) as<\/span> source:\r\n    tree = ast.parse(source.read())<\/code><\/pre>\n<\/div>\n
      In two lines of code, we read a file and create an AST named\u00a0tree<\/code>. The\u00a0ast.parse<\/code>\u00a0function makes this a snap! There is a ton happening under the hood of that function that we can blissfully ignore.<\/p>\n
      With one function call, Python processed all the tokens, followed all the rules of the language, and built a data structure (i.e., a tree) containing all the relevant information to run the code.<\/p>\n
      Before moving on, let\u2019s take a moment to consider what a tree is. Trees are a very deep topic in software development so consider this a primer rather than an exhaustive explanation.<\/p>\n
      A tree is a way to hold data as a set of \u201cnodes\u201d connected by \u201cedges.\u201d<\/p><\/blockquote>\n
      \n
               +-----+\r\n         |  A  |\r\n         +-----+\r\n        \/       \\\r\n       \/         \\\r\n+-----+           +-----+\r\n|  B  |           |  C  |\r\n+-----+           +-----+<\/code><\/pre>\n<\/div>\n
      In this diagram, A, B, and C are all nodes and there are edges connecting A to B and A to C.<\/p>\n
      One way to represent this tree in code could be:<\/p>\n
      \n
      class<\/span><\/span> Node<\/span><\/span>:<\/span>\r\n    def<\/span><\/span>__init__<\/span>(self, value)<\/span>:<\/span>\r\n        self.value = value\r\n        self.children = []\r\n\r\ntree = Node('A'<\/span>)\r\ntree.children.append(Node('B'<\/span>))\r\ntree.children.append(Node('C'<\/span>))<\/code><\/pre>\n<\/div>\n
      Notice that the\u00a0tree<\/code>\u00a0is actually a node! When we work with a tree, we\u2019re really dealing with a collection of nodes, and the tree variable is a reference to the \u201croot\u201d node (e.g., node A). By having this kind of structure, we can check each node in the tree and take action. We do that by visiting each node in the tree and processing its data.<\/p>\n
      \n
      def<\/span><\/span> print_node_value<\/span><\/span>(value)<\/span>:<\/span>\r\n    print(value)\r\n\r\ndef<\/span><\/span> visit<\/span><\/span>(node, handle_node)<\/span>:<\/span>\r\n    handle_node(node.value)\r\n    for<\/span> child in<\/span> node.children:\r\n        visit(child, handle_node)\r\n\r\n# tree is from the previous example.<\/span>\r\nvisit(tree, print_node_value)\r\n# This should print:<\/span>\r\n# A<\/span>\r\n# B<\/span>\r\n# C<\/span><\/code><\/pre>\n<\/div>\n
      Now that we have an idea of what a tree is, we can consider what the next section of the example script does. The tree structure of the Python abstract syntax tree is more involved because of the count of its nodes and the type of data stored, yet the core idea of nodes and edges is the same.<\/p>\n
      Analyze the AST<\/h3>\n
      Once we have the tree, the\u00a0Analyzer<\/code>\u00a0follows the visitor pattern that I showed above to extract information out of the tree.<\/p>\n
      I noted that a Python AST is more complex than my basic\u00a0Node<\/code>\u00a0design. One difference is that it tracks various\u00a0types<\/em>\u00a0of nodes. This is where\u00a0ast.NodeVisitor<\/code>\u00a0is useful.<\/p>\n
      A\u00a0NodeVisitor<\/code>\u00a0can respond to any type of node in the Python AST. To visit a particular type of node, we must implement a method that looks like\u00a0visit_<node type><\/code>.<\/p>\n
      My example code is trying to find out about imports. To learn about imports, the code pulls from the\u00a0Import<\/code>\u00a0and\u00a0ImportFrom<\/code>\u00a0node types.<\/p>\n
      \n
      def<\/span><\/span> visit_Import<\/span><\/span>(self, node)<\/span>:<\/span>\r\n    for<\/span> alias in<\/span> node.names:\r\n        self.stats[\"import\"<\/span>].append(alias.name)\r\n    self.generic_visit(node)\r\n\r\ndef<\/span><\/span> visit_ImportFrom<\/span><\/span>(self, node)<\/span>:<\/span>\r\n    for<\/span> alias in<\/span> node.names:\r\n        self.stats[\"from\"<\/span>].append(alias.name)\r\n    self.generic_visit(node)<\/code><\/pre>\n<\/div>\n
      This code takes the name of the module and stores it in a list of statistics. While the code is not fancy, it shows you how to interact with AST nodes.<\/p>\n
      With the\u00a0NodeVisitor<\/code>\u00a0class defined, we can use it to analyze the tree.<\/p>\n
      \n
      analyzer = Analyzer()\r\nanalyzer.visit(tree)<\/code><\/pre>\n<\/div>\n
      The\u00a0visit<\/code>\u00a0method will delegate to your\u00a0visit_<node type><\/code>\u00a0method whenever that type of node is encountered while traversing through the tree structure.<\/p>\n
      So, what kinds of node types are there? You can find the full list in theAbstract Grammar<\/a>\u00a0section of the\u00a0ast<\/code>\u00a0module documentation. Truthfully, I find that documentation a little hard to absorb. You may have more success by referring to a more exhaustive guide like the\u00a0Green Tree Snakes<\/a>\u00a0Nodes guide.<\/p>\n
      Wrapping up<\/h2>\n
      By now, you hopefully understand how to:<\/p>\n
        \n
      1. Build an AST from Python source code.<\/li>\n
      2. Do analysis on the AST using a\u00a0NodeVisitor<\/code>.<\/li>\n<\/ol>\n
        I think you can answer many interesting questions about your code by using abstract syntax trees. Questions like:<\/p>\n