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

Question

我正在阅读有关 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))

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

Answer 1

AST 是 CST 的抽象（具体语法树，或解析树）。具体语法树是由用于解析文件的产生式（在语法中）产生的树。所以你的 AST 基本上是从你的语法定义中派生出来的，但是已经进行了转换

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

总而言之，我认为您帖子中的示例看起来不错。我可能会将变量声明包装在

varDeclList

中，将函数声明包装在

methDeclList

中，并将 return 语句包装在

stmtList

中。（见下文。）

Apple 在他的《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

Answer 2

OP：

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

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

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

接下来是来自我们的

DMS Software Reengineering Toolkit 的解析器树的 S 表达式风格转储中的具体语法树和抽象语法树，使用其 Java1.6 解析器。所有表面上的复杂性几乎都是由语言（例如 Java 本身）的实际复杂性引起的。

CST 显然比 AST（54 个节点）包含更多的内容（139 个节点）。给定 AST，AST 会丢弃所有可以从语法中自动推断出的内容。这包括删除不带值的叶子、一元产生式以及将由左或右递归语法规则引起的脊椎压缩到显式列表节点中。

左括号表示一个新的子树。左括号后面是节点类型的名称； @Java~Java1_.6 可能看起来没有必要，直到您了解 DMS 可以同时处理多种语言（包括相互嵌套的语言）。 #nnnnnn 是节点的内存地址。 ^M 表示“此节点有 M 个父节点，当 M==1 时被关闭。[...] 内的内容是节点值。A { 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。

Answer 3

查看

Eclipse JDT AST 实现。

作为第一个介绍，您也可以阅读这个

教程。

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

问题描述投票：0回答：3

3个回答

最新问题

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

问题描述 投票：0回答：3

3个回答

最新问题

问题描述投票：0回答：3