面向对象编程语言的AST（抽象语法树）会是什么样子？

programming-languages java compiler-construction abstract-syntax-tree

2022-09-01 19:07:41

我正在阅读有关AST（抽象语法树）的信息，但我看到的所有示例都使用如下表达式：

a + b * c

这可以用类似 lispy 的语法表示为：

(+ a (* b c) )

这将等效于：

  +
 / \
a   * 
   / \
  b   c

我的问题是OOPL中类的AST会是什么样子？

我幼稚的尝试是针对这个Java代码：

 class Person { 
     String name;
     int    age;
     public String toString() { 
        return "name";
     }
 }

是：

;Hand written
(classDeclaration Person 
     (varDeclaration String name)
     (varDeclaration int    age )
     (funcDeclaration String toString 
           (return "name")
     )
 )

但我不太确定我离真正的AST表示有多近或多远。

这取决于我选择的语言。需要多少细节？这些“xyzDeclaraction”是必需的，还是可以作为：

 (Person (String name) (int age))

我在哪里可以看到实际编程语言的“真实”表示，以了解更多信息。

答案 1

AST 是 CST（具体语法树或解析树）的抽象。具体语法树是由用于解析文件的作品（在语法中）生成的树。因此，您的AST基本上是从您的语法定义派生而来的，但是已经进行了转换

                        Exp                    
                      /  |  \                   
                     /   |   \                       *
                 Ident BinOp Ident       into       / \
                  /      |     \                  "x" "y"
                 /       |      \
               "x"       *      "y"

总而言之，我认为您帖子中的示例看起来很好。我可能会将变量声明包装在 a 中，函数声明包装在 a 中，并将 return 语句包装在 .（见下文。varDeclListmethDeclListstmtList

苹果公司在他的书“Java中的现代编译器实现”中或多或少地描述了AST的一种或多或少的“真实”表示。（资源可以在这里找到。

使用这些类，您的程序将表示如下：

Program
    ClassDeclList
        ClassDecl
            Identifier
                id: Person
            VarDeclList
                VarDecl
                    type: String
                    id: name
                VarDecl
                    type: int
                    id: age
            MethDeclList
                MethodDecl
                    modifiers: public
                    returnType: String
                    id: toString
                    Formals
                        (empty)
                    StmtList
                        returnStmt
                            Identifier
                                id: name

答案 2

OP：我在哪里可以看到实际编程语言的真实表示，以了解更多信息？

对于作为文件的源文本人员.java：

class Person {  
    String name;
    int    age;
    public String toString()
      { return "name";     } 
}

以下是具体和抽象语法树，来自我们的DMS软件再工程工具包的解析器树的S表达式式转储，使用其Java1.6解析器。所有表面上的复杂性几乎都是由语言的真正复杂性（例如，Java本身）引起的。

CST 显然比 AST（54 个节点）包含更多的东西（139 个节点）。AST 删除了给定 AST 时可以从语法中自动推断的所有内容。这包括删除非价值携带的叶子，一元生产，以及将左或右递归语法规则引起的棘刺压缩到显式列表节点中。

左帕伦表示新的子树。左边的paren后面是节点类型的名称;@Java~Java1_.6似乎没有必要，直到您了解DMS可以同时处理多种语言，包括嵌套在彼此内部的语言。#nnnnnn是节点的内存地址。^M 表示“此节点具有 M 个父节点，当 M==1 时被忽略。里面的东西[...]是节点值。{ M } 表示此列表节点具有 M 个列表子节点。每个节点都印有位置信息。

这是具体语法树（请参阅下面的 AST）：

(compilation_unit@Java~Java1_6=1#4885d00^0 Line 1 Column 1 File C:/temp/Person.java
 (type_declarations@Java~Java1_6=15#4885cc0 Line 1 Column 1 File C:/temp/Person.java
  (type_declarations@Java~Java1_6=16#4884d80 Line 1 Column 1 File C:/temp/Person.java)type_declarations
  (type_declaration@Java~Java1_6=17#4885ca0 Line 1 Column 1 File C:/temp/Person.java
   (type_class_modifiers@Java~Java1_6=77#4884dc0 Line 1 Column 1 File C:/temp/Person.java)type_class_modifiers
   (class_header@Java~Java1_6=89#4884ec0 Line 1 Column 1 File C:/temp/Person.java
   |('class'@Java~Java1_6=459#4884c60[Keyword:0] Line 1 Column 1 File C:/temp/Person.java)'class'
   |(IDENTIFIER@Java~Java1_6=447#4884e20[`Person'] Line 1 Column 7 File C:/temp/Person.java)IDENTIFIER
   |(type_parameters@Java~Java1_6=408#4884e80 Line 1 Column 14 File C:/temp/Person.java)type_parameters
   )class_header
   (class_body@Java~Java1_6=94#4885c80 Line 1 Column 14 File C:/temp/Person.java
   |('{'@Java~Java1_6=448#4884e60[Keyword:0] Line 1 Column 14 File C:/temp/Person.java)'{'
   |(class_body_declarations@Java~Java1_6=111#4885c60 Line 2 Column 5 File C:/temp/Person.java
   | (class_body_declarations@Java~Java1_6=111#4885380 Line 2 Column 5 File C:/temp/Person.java
   |  (class_body_declarations@Java~Java1_6=110#4885400 Line 2 Column 5 File C:/temp/Person.java
   |   (class_body_declaration@Java~Java1_6=118#4885360 Line 2 Column 5 File C:/temp/Person.java
   |   |(field_declaration@Java~Java1_6=168#4885440 Line 2 Column 5 File C:/temp/Person.java
   |   | (field_modifiers@Java~Java1_6=170#4884f40 Line 2 Column 5 File C:/temp/Person.java)field_modifiers
   |   | (type@Java~Java1_6=191#48852c0 Line 2 Column 5 File C:/temp/Person.java
   |   |  (name@Java~Java1_6=406#48851e0 Line 2 Column 5 File C:/temp/Person.java
   |   |   (IDENTIFIER@Java~Java1_6=447#4884f20[`String'] Line 2 Column 5 File C:/temp/Person.java)IDENTIFIER
   |   |   (type_arguments@Java~Java1_6=407#4885160 Line 2 Column 12 File C:/temp/Person.java)type_arguments
   |   |  )name
   |   |  (brackets@Java~Java1_6=157#4885260 Line 2 Column 12 File C:/temp/Person.java)brackets
   |   | )type
   |   | (variable_declarator_list@Java~Java1_6=179#4884e00 Line 2 Column 12 File C:/temp/Person.java
   |   |  (variable_declarator@Java~Java1_6=181#4885300 Line 2 Column 12 File C:/temp/Person.java
   |   |   (variable_declarator_id@Java~Java1_6=167#4885320 Line 2 Column 12 File C:/temp/Person.java
   |   |   |(IDENTIFIER@Java~Java1_6=447#4885140[`name'] Line 2 Column 12 File C:/temp/Person.java)IDENTIFIER
   |   |   |(brackets@Java~Java1_6=157#4885040 Line 2 Column 16 File C:/temp/Person.java)brackets
   |   |   )variable_declarator_id
   |   |  )variable_declarator
   |   | )variable_declarator_list
   |   | (';'@Java~Java1_6=440#4885100[Keyword:0] Line 2 Column 16 File C:/temp/Person.java)';'
   |   |)field_declaration
   |   )class_body_declaration
   |  )class_body_declarations
   |  (class_body_declaration@Java~Java1_6=118#48852e0 Line 3 Column 5 File C:/temp/Person.java
   |   (field_declaration@Java~Java1_6=168#4885480 Line 3 Column 5 File C:/temp/Person.java
   |   |(field_modifiers@Java~Java1_6=170#4885340 Line 3 Column 5 File C:/temp/Person.java)field_modifiers
   |   |(type@Java~Java1_6=192#4885220 Line 3 Column 5 File C:/temp/Person.java
   |   | (primitive_type@Java~Java1_6=198#4885420 Line 3 Column 5 File C:/temp/Person.java
   |   |  ('int'@Java~Java1_6=479#48853e0[Keyword:0] Line 3 Column 5 File C:/temp/Person.java)'int'
   |   | )primitive_type
   |   | (brackets@Java~Java1_6=157#4885200 Line 3 Column 12 File C:/temp/Person.java)brackets
   |   |)type
   |   |(variable_declarator_list@Java~Java1_6=179#4885540 Line 3 Column 12 File C:/temp/Person.java
   |   | (variable_declarator@Java~Java1_6=181#4885520 Line 3 Column 12 File C:/temp/Person.java
   |   |  (variable_declarator_id@Java~Java1_6=167#4885500 Line 3 Column 12 File C:/temp/Person.java
   |   |   (IDENTIFIER@Java~Java1_6=447#4884fc0[`age'] Line 3 Column 12 File C:/temp/Person.java)IDENTIFIER
   |   |   (brackets@Java~Java1_6=157#48854e0 Line 3 Column 15 File C:/temp/Person.java)brackets
   |   |  )variable_declarator_id
   |   | )variable_declarator
   |   |)variable_declarator_list
   |   |(';'@Java~Java1_6=440#48854c0[Keyword:0] Line 3 Column 15 File C:/temp/Person.java)';'
   |   )field_declaration
   |  )class_body_declaration
   | )class_body_declarations
   | (class_body_declaration@Java~Java1_6=117#4885c40 Line 4 Column 5 File C:/temp/Person.java
   |  (method_declaration@Java~Java1_6=135#4885c00 Line 4 Column 5 File C:/temp/Person.java
   |   (method_modifiers@Java~Java1_6=141#4885700 Line 4 Column 5 File C:/temp/Person.java
   |   |(method_modifiers@Java~Java1_6=142#4884e40 Line 4 Column 5 File C:/temp/Person.java)method_modifiers
   |   |(method_modifier@Java~Java1_6=147#48856a0 Line 4 Column 5 File C:/temp/Person.java
   |   | ('public'@Java~Java1_6=453#48853a0[Keyword:0] Line 4 Column 5 File C:/temp/Person.java)'public'
   |   |)method_modifier
   |   )method_modifiers
   |   (type_parameters@Java~Java1_6=408#4885740 Line 4 Column 12 File C:/temp/Person.java)type_parameters
   |   (type@Java~Java1_6=191#4885900 Line 4 Column 12 File C:/temp/Person.java
   |   |(name@Java~Java1_6=406#48852a0 Line 4 Column 12 File C:/temp/Person.java
   |   | (IDENTIFIER@Java~Java1_6=447#4885660[`String'] Line 4 Column 12 File C:/temp/Person.java)IDENTIFIER
   |   | (type_arguments@Java~Java1_6=407#48851a0 Line 4 Column 19 File C:/temp/Person.java)type_arguments
   |   |)name
   |   |(brackets@Java~Java1_6=157#48858c0 Line 4 Column 19 File C:/temp/Person.java)brackets
   |   )type
   |   (IDENTIFIER@Java~Java1_6=447#48855c0[`toString'] Line 4 Column 19 File C:/temp/Person.java)IDENTIFIER
   |   (parameters@Java~Java1_6=158#48858e0 Line 4 Column 27 File C:/temp/Person.java
   |   |('('@Java~Java1_6=450#4885840[Keyword:0] Line 4 Column 27 File C:/temp/Person.java)'('
   |   |(')'@Java~Java1_6=451#4885620[Keyword:0] Line 4 Column 28 File C:/temp/Person.java)')'
   |   )parameters
   |   (brackets@Java~Java1_6=157#4885060 Line 5 Column 7 File C:/temp/Person.java)brackets
   |   (block@Java~Java1_6=217#4885be0 Line 5 Column 7 File C:/temp/Person.java
   |   |('{'@Java~Java1_6=448#48851c0[Keyword:0] Line 5 Column 7 File C:/temp/Person.java)'{'
   |   |(statement_sequence@Java~Java1_6=218#4885ba0 Line 5 Column 9 File C:/temp/Person.java
   |   | (statement_sequence_member@Java~Java1_6=223#4885b80 Line 5 Column 9 File C:/temp/Person.java
   |   |  (executable_statement@Java~Java1_6=243#4885b60 Line 5 Column 9 File C:/temp/Person.java
   |   |   ('return'@Java~Java1_6=491#4884f60[Keyword:0] Line 5 Column 9 File C:/temp/Person.java)'return'
   |   |   (expression@Java~Java1_6=332#4885ac0 Line 5 Column 16 File C:/temp/Person.java
   |   |   |(conditional_expression@Java~Java1_6=345#4885a60 Line 5 Column 16 File C:/temp/Person.java
   |   |   | (conditional_or_expression@Java~Java1_6=347#4885a20 Line 5 Column 16 File C:/temp/Person.java
   |   |   |  (conditional_and_expression@Java~Java1_6=349#48859e0 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   (inclusive_or_expression@Java~Java1_6=351#48857e0 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |(exclusive_or_expression@Java~Java1_6=353#48855a0 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   | (and_expression@Java~Java1_6=355#4885940 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |  (equality_expression@Java~Java1_6=357#4885880 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   (relational_expression@Java~Java1_6=360#4885800 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   |(shift_expression@Java~Java1_6=366#48856c0 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   | (additive_expression@Java~Java1_6=370#4885180 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   |  (multiplicative_expression@Java~Java1_6=373#4885780 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   |   (unary_expression@Java~Java1_6=383#4885600 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   |   |(unary_expression_not_plus_minus@Java~Java1_6=389#4885680 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   |   | (literal@Java~Java1_6=390#4884f80 Line 5 Column 16 File C:/temp/Person.java
   |   |   |   |   |   |  (STRING@Java~Java1_6=536#4885120[`name'] Line 5 Column 16 File C:/temp/Person.java)STRING
   |   |   |   |   |   | )literal
   |   |   |   |   |   |)unary_expression_not_plus_minus
   |   |   |   |   |   )unary_expression
   |   |   |   |   |  )multiplicative_expression
   |   |   |   |   | )additive_expression
   |   |   |   |   |)shift_expression
   |   |   |   |   )relational_expression
   |   |   |   |  )equality_expression
   |   |   |   | )and_expression
   |   |   |   |)exclusive_or_expression
   |   |   |   )inclusive_or_expression
   |   |   |  )conditional_and_expression
   |   |   | )conditional_or_expression
   |   |   |)conditional_expression
   |   |   )expression
   |   |   (';'@Java~Java1_6=440#48856e0[Keyword:0] Line 5 Column 22 File C:/temp/Person.java)';'
   |   |  )executable_statement
   |   | )statement_sequence_member
   |   |)statement_sequence
   |   |('}'@Java~Java1_6=449#4885b40[Keyword:0] Line 5 Column 28 File C:/temp/Person.java)'}'
   |   )block
   |  )method_declaration
   | )class_body_declaration
   |)class_body_declarations
   |('}'@Java~Java1_6=449#4885bc0[Keyword:0] Line 6 Column 1 File C:/temp/Person.java)'}'
   )class_body
  )type_declaration
 )type_declarations
 (optional_CONTROL_Z@Java~Java1_6=5#4885ce0 Line 7 Column 1 File C:/temp/Person.java)optional_CONTROL_Z
)compilation_unit

这是AST（由DMS从CST自动生成）：

(compilation_unit@Java~Java1_6=1#486f900^0 Line 1 Column 1 File C:/temp/Person.java
 (type_declarations@Java~Java1_6=15#486f4c0 {1} Line 1 Column 1 File C:/temp/Person.java
  (type_declaration@Java~Java1_6=17#486f5e0 Line 1 Column 1 File C:/temp/Person.java
   (type_class_modifiers@Java~Java1_6=77#486eda0 Line 1 Column 1 File C:/temp/Person.java)type_class_modifiers
   (class_header@Java~Java1_6=89#486ee60 Line 1 Column 1 File C:/temp/Person.java
   |(IDENTIFIER@Java~Java1_6=447#486ede0[`Person'] Line 1 Column 7 File C:/temp/Person.java)IDENTIFIER
   |(type_parameters@Java~Java1_6=408#486ee20 Line 1 Column 14 File C:/temp/Person.java)type_parameters
   )class_header
   (class_body@Java~Java1_6=94#486f040 Line 1 Column 14 File C:/temp/Person.java
   |(class_body_declarations@Java~Java1_6=111#486ee40 {3} Line 2 Column 5 File C:/temp/Person.java
   | (class_body_declaration@Java~Java1_6=118#486f300 Line 2 Column 5 File C:/temp/Person.java
   |  (field_declaration@Java~Java1_6=168#486f380 Line 2 Column 5 File C:/temp/Person.java
   |   (field_modifiers@Java~Java1_6=170#486eec0 Line 2 Column 5 File C:/temp/Person.java)field_modifiers
   |   (type@Java~Java1_6=191#486f240 Line 2 Column 5 File C:/temp/Person.java
   |   |(name@Java~Java1_6=406#486f180 Line 2 Column 5 File C:/temp/Person.java
   |   | (IDENTIFIER@Java~Java1_6=447#486eea0[`String'] Line 2 Column 5 File C:/temp/Person.java)IDENTIFIER
   |   | (type_arguments@Java~Java1_6=407#486f0e0 Line 2 Column 12 File C:/temp/Person.java)type_arguments
   |   |)name
   |   |(brackets@Java~Java1_6=157#486f200 Line 2 Column 12 File C:/temp/Person.java)brackets
   |   )type
   |   (variable_declarator@Java~Java1_6=181#486ef20 Line 2 Column 12 File C:/temp/Person.java
   |   |(variable_declarator_id@Java~Java1_6=167#486efe0 Line 2 Column 12 File C:/temp/Person.java
   |   | (IDENTIFIER@Java~Java1_6=447#486f0c0[`name'] Line 2 Column 12 File C:/temp/Person.java)IDENTIFIER
   |   | (brackets@Java~Java1_6=157#486f060 Line 2 Column 16 File C:/temp/Person.java)brackets
   |   |)variable_declarator_id
   |   )variable_declarator
   |  )field_declaration
   | )class_body_declaration
   | (class_body_declaration@Java~Java1_6=118#486f000 Line 3 Column 5 File C:/temp/Person.java
   |  (field_declaration@Java~Java1_6=168#486f320 Line 3 Column 5 File C:/temp/Person.java
   |   (field_modifiers@Java~Java1_6=170#486f2a0 Line 3 Column 5 File C:/temp/Person.java)field_modifiers
   |   (type@Java~Java1_6=192#486eee0 Line 3 Column 5 File C:/temp/Person.java
   |   |(primitive_type@Java~Java1_6=198#486ef60 Line 3 Column 5 File C:/temp/Person.java)primitive_type
   |   |(brackets@Java~Java1_6=157#486ee00 Line 3 Column 12 File C:/temp/Person.java)brackets
   |   )type
   |   (variable_declarator@Java~Java1_6=181#486f2c0 Line 3 Column 12 File C:/temp/Person.java
   |   |(variable_declarator_id@Java~Java1_6=167#486f3a0 Line 3 Column 12 File C:/temp/Person.java
   |   | (IDENTIFIER@Java~Java1_6=447#486f120[`age'] Line 3 Column 12 File C:/temp/Person.java)IDENTIFIER
   |   | (brackets@Java~Java1_6=157#486ef00 Line 3 Column 15 File C:/temp/Person.java)brackets
   |   |)variable_declarator_id
   |   )variable_declarator
   |  )field_declaration
   | )class_body_declaration
   | (class_body_declaration@Java~Java1_6=117#486f7a0 Line 4 Column 5 File C:/temp/Person.java
   |  (method_declaration@Java~Java1_6=135#486f480 Line 4 Column 5 File C:/temp/Person.java
   |   (method_modifiers@Java~Java1_6=141#486f460 {1} Line 4 Column 5 File C:/temp/Person.java
   |   |(method_modifier@Java~Java1_6=147#486f400 Line 4 Column 5 File C:/temp/Person.java)method_modifier
   |   )method_modifiers
   |   (type_parameters@Java~Java1_6=408#486f540 Line 4 Column 12 File C:/temp/Person.java)type_parameters
   |   (type@Java~Java1_6=191#486f740 Line 4 Column 12 File C:/temp/Person.java
   |   |(name@Java~Java1_6=406#486f620 Line 4 Column 12 File C:/temp/Person.java
   |   | (IDENTIFIER@Java~Java1_6=447#486f080[`String'] Line 4 Column 12 File C:/temp/Person.java)IDENTIFIER
   |   | (type_arguments@Java~Java1_6=407#486f640 Line 4 Column 19 File C:/temp/Person.java)type_arguments
   |   |)name
   |   |(brackets@Java~Java1_6=157#486f700 Line 4 Column 19 File C:/temp/Person.java)brackets
   |   )type
   |   (IDENTIFIER@Java~Java1_6=447#486f140[`toString'] Line 4 Column 19 File C:/temp/Person.java)IDENTIFIER
   |   (parameters@Java~Java1_6=158#486f760 Line 4 Column 27 File C:/temp/Person.java)parameters
   |   (brackets@Java~Java1_6=157#486f820 Line 5 Column 7 File C:/temp/Person.java)brackets
   |   (block@Java~Java1_6=217#486f780 Line 5 Column 7 File C:/temp/Person.java
   |   |(statement_sequence@Java~Java1_6=218#486f6e0 Line 5 Column 9 File C:/temp/Person.java
   |   | (statement_sequence_member@Java~Java1_6=223#486f6c0 Line 5 Column 9 File C:/temp/Person.java
   |   |  (executable_statement@Java~Java1_6=243#486f6a0 Line 5 Column 9 File C:/temp/Person.java
   |   |   (unary_expression_not_plus_minus@Java~Java1_6=389#486f720 Line 5 Column 16 File C:/temp/Person.java
   |   |   |(literal@Java~Java1_6=390#486f280 Line 5 Column 16 File C:/temp/Person.java
   |   |   | (STRING@Java~Java1_6=536#486f160[`name'] Line 5 Column 16 File C:/temp/Person.java)STRING
   |   |   |)literal
   |   |   )unary_expression_not_plus_minus
   |   |  )executable_statement
   |   | )statement_sequence_member
   |   |)statement_sequence
   |   )block
   |  )method_declaration
   | )class_body_declaration
   |)class_body_declarations
   )class_body
  )type_declaration
 )type_declarations
 (optional_CONTROL_Z@Java~Java1_6=5#486f4e0 Line 7 Column 1 File C:/temp/Person.java)optional_CONTROL_Z
)compilation_unit

编辑 2015 年 3 月：这是一些C++ AST 示例的链接

2015 年 5 月编辑：DMS 早就完成了 Java 1.7 和 1.8。