{"id":4005,"date":"2024-02-27T19:52:07","date_gmt":"2024-02-27T18:52:07","guid":{"rendered":"https:\/\/oopm.org\/?page_id=4005"},"modified":"2024-12-13T13:45:44","modified_gmt":"2024-12-13T12:45:44","slug":"10-1-3-an-abstract-syntax-tree","status":"publish","type":"page","link":"https:\/\/oopm.org\/?page_id=4005","title":{"rendered":"10.1.3 An abstract syntax tree"},"content":{"rendered":"
\"image_pdf\"<\/a>\"image_print\"<\/a><\/div>\n

In this section, we will show how to represent an expression by means of an abstract syntax tree. An abstract syntax tree<\/em> (AST<\/em>) or just syntax tree<\/em> is a data structure that may represent the structure of a text described by a grammar. <\/p>\n\n\n\n

The “tree<\/em>” in AST refers to the fact that an AST is an example of a common data structure called a tree. A tree represents a hierarchical structure with a set of connected nodes<\/em>. A node may have zero or more children<\/em> which are also nodes. A child has exactly one parent<\/em>. Nodes that have no children are called leaf nodes<\/em>. The top node in a tree is called the root<\/em> and have no parent. <\/p>\n\n\n\n

A binary tree <\/em>is a common used data structure where each parent has at most two children and the two nodes are often ordered in a left<\/em> node and a right<\/em> node.<\/p>\n\n\n\n

For our expression grammar we will use a binary tree and the tree in the figure below shows a representation of the expression \"10 + 11 * (1 + 9)\"<\/code>.<\/p>\n\n\n\n

\"\"
An AST for \u201c10 + 11 * (1 + 9)\u201d<\/figcaption><\/figure>\n\n\n\n

In the following, we introduce classes to represent a binary AST for our expression grammar as shown in the figure. We start by introducing a general class being the superclass of all nodes of an AST:<\/p>\n\n\n\n

class<\/strong> Node(label: var<\/strong> char, left: ref<\/strong> Node, right: ref<\/strong> Node): \n   eval -> v: var integer:<\n      inner(eval)\n   print(ind: var integer):\n         ...<\/code><\/pre>\n\n\n\n
Class Node<\/code> has three parameters, the label<\/code> of the node, and left<\/code> and right<\/code> representing the two children of the Node<\/code>. In addition, a Node<\/code> has an eval<\/code>-method and a print<\/code>-method. We return to these later in this section.<\/p>\n\n\n\n
For each nonterminal except <Primary><\/code>, we have a subclass of Node<\/code>:<\/p>\n\n\n\n
class<\/strong> ExpNode: Node\n   eval::\n      v := left.eval + right.eval\nclass<\/strong> TermNode: Node\n   eval::\n      v := left.eval * right.eval\nclass<\/strong> NumberNode: Node\n   eval::\n      if (right == none) :then\n         v := left.eval\n      :else\n         v := (left.eval * 10) + right.eval\nclass<\/strong> DigitNode: Node\n   eval::\n       v := label - '0'<\/code><\/pre>\n\n\n\n
The next figure shows how the above tree representing \"10 + 11 * (1 + 9)\"<\/code> may be represented as objects of these classes:<\/p>\n\n\n\n
\"\"
AST-b\/An object diagram for \u201c10 + 11 * (1 + 9)\u201d<\/figcaption><\/figure>\n\n\n\n
The eval<\/code>-method performs a recursive traversal of the tree and evaluates the expression represented by the tree. If root<\/code> is a reference to the root of the tree, root.eval<\/code> will return the value 120.<\/p>\n\n\n\n
Building the AST<\/h2>\n\n\n\n
We now extend the parser to build the AST during parsing. Each method will then return the AST for the string being parsed by the method. Consider exp<\/code>:<\/p>\n\n\n\n
exp -> N: ref<\/strong> Node:\n   N := term\n   addOp: do\n      if (ch = '+') :then\n         rN: ref<\/strong> Node\n         nextChar\n         rN := term\n         N := expNode('+',N,rN)\t\n         restart(addOp)<\/code><\/pre>\n\n\n\n
As can be seen the return value of exp<\/code> is a Node<\/code> represented by the reference variable N<\/code>. The method term<\/code> is assumed to return the AST representing the string parsed by term<\/code>.<\/p>\n\n\n\n
If no '+'<\/code> character is following the first call of term<\/code> (ch = '+'<\/code>) then exp<\/code> just returns the Node<\/code> returned by term. If a '+'<\/code> character is met, term<\/code> invoked again, and exp<\/code> returns an ExpNode<\/code> with the first argument being a '+'<\/code>, and the second and third argument being the nodes returned by the first an second call of term<\/code>. This is repeated as long as ch = '+'.<\/code><\/p>\n\n\n\n
The revised methods term<\/code> and primary<\/code> may look as follows:<\/p>\n\n\n\n
term ->  N: ref<\/strong> node:\n   N := primary\n   multOp: do\n      if (ch = '*') :then\n         rN: ref<\/strong> Node\n         nextChar\n         rN := primary\t \n         N := termNode('*',N,rN)\n         restart(multOP)\nprimary -> N: ref<\/strong> Node:\n   if (ch = '(') :then\n      nextChar        \n      N := exp\n      if (ch = ')') :then\n         nextChar\n      :else\n         syntaxError(1)\n   :else\n      N := number<\/code><\/pre>\n\n\n\n
As can be seen, the structure of term<\/code> similar to exp<\/code> whereas primary<\/code> just returns the Node<\/code> returned by exp<\/code> or number<\/code>.<\/p>\n\n\n\n
Next we show the revised versions of number<\/code> and digit<\/code>:<\/p>\n\n\n\n
number -> N: ref<\/strong> node:\n   N := digit\n   moreDigits: do\n      if (ascii.isDigit(ch)) :then\n         rN: ref Node\n         rN := digit\n         N := NumberNode('N',N,rN)\t    \n         restart(moreDigits)\n      :else\n         N := NumberNode('N',N,none)\ndigit -> N: ref<\/strong> Node:\n   if (ascii.isDigit(ch)) :then\n      N:= digitNode(ch,none,none)\n      nextChar\n   :else\n       syntaxError(2)<\/code><\/pre>\n\n\n\n
These should be straightforward to understand. Note, however, that both may return a Node<\/code> where the left and\/or right child is none<\/code>.<\/p>\n\n\n\n
Finally we may show the new version of the parse<\/code> method:<\/p>\n\n\n\n
parse:\n   N: ref Node\n   inn :=  \"10 + 11 * (1 + 9)\"\n   console.print((\"\\nParse: \" + inn + \"\\n\")\n   nextChar\n   N := exp      \n   if (ch <> ascii.null) :then\n      syntaxError(3)\n   if (not hasSyntaxErrors) :then\n      console.print(\"\\nResulting AST:\\n\")\t  \n      console.print(N.print(0))\n      console.print(\"Evaluation of exp is: N.eval))<\/code><\/pre>\n\n\n\n
If no syntax errors have happened during the exp<\/code>-call, the resulting AST is printed and the result of evaluating it is also printed.<\/p>\n\n\n\n
We have not shown details of a print<\/code>-method and leave this to the reader. The parameter of print<\/code> is supposed to be the level of a given Node<\/code> in an AST where the root<\/code> is at level 0 and the children of the root at level 1, etc. This should make it easier to print an indented text version of the AST.<\/p>\n
\n\t\t<\/a>\n\t\t<\/div>","protected":false},"excerpt":{"rendered":"
In this section, we will show how to represent an expression by means of an abstract syntax tree. An abstract syntax tree (AST) or just syntax tree is a data structure that may represent the structure of a text described by a grammar. The “tree” in AST refers to the fact that an AST is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1282,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4005","page","type-page","status-publish","hentry"],"mb":[],"mfb_rest_fields":["title","gutenberg_elementor_mode"],"_links":{"self":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/4005","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4005"}],"version-history":[{"count":43,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/4005\/revisions"}],"predecessor-version":[{"id":10344,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/4005\/revisions\/10344"}],"up":[{"embeddable":true,"href":"https:\/\/oopm.org\/index.php?rest_route=\/wp\/v2\/pages\/1282"}],"wp:attachment":[{"href":"https:\/\/oopm.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4005"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}