标签: abstract-syntax-tree

(免责声明:这些示例是在构建编译器的上下文中给出的,但是这个问题都是关于访问者模式的,并且不需要任何编译器理论知识.)我将通过Andrew Appel的Java中的现代编译器实现来尝试自学编译器理论(所以不,这不是家庭作业),我无法理解他想如何使用访客模式将AST转换为IR树.(注意:我在Python中这样做,所以我也可以学习Python,这就是为什么即将推出的示例不是Java的原因.)据我所知,访问者模式中的访问和接受方法是无效的设计类型,所以,如果我有类似的东西

class PlusExp(Exp):
    def __init__(self, exp_left, exp_right):
        self.exp_left = exp_left
        self.exp_right = exp_right

    def accept(self, v):
        v.visit_plus_exp(self)

那么我希望能够写一个像访问者的方法

def visit_plus_exp(self, plus_exp):
    return BINOP(BinOp.PLUS, 
                 plus_exp.exp_left.accept(self), 
                 plus_exp.exp_right.accept(self))

这会将两个子表达式转换为IR,然后将它们与表示加号表达式的BINOP链接起来.当然,这是不可能的,除非我修改所有的接受函数以返回额外的信息,这也很麻烦,因为有时你只是想要一个不返回任何内容的打印访问者.然而,本文坚持认为访问者是正确的方式,而在Java中,这意味着它可以在没有Python灵活性的情况下完成.我想不出任何不太令人难以置信的解决方案 - 任何人都可以启发我的预期设计吗？

我正在玩python ast(抽象语法树).

我写了以下内容,它访问了AST的所有节点.

import ast

class Py2Neko(ast.NodeVisitor):
    def generic_visit(self, node):
              print type(node).__name__
              ast.NodeVisitor.generic_visit(self, node)

       def visit_Name(self, node):
              print 'Name :', node.id

       def visit_Num(self, node):
              print 'Num :', node.__dict__['n']

       def visit_Str(self, node):
              print "Str :", node.s

if __name__ == '__main__':

    node = ast.parse("a = 1 + 2")

    print ast.dump(node)

    v = Py2Neko()
    v.visit(node)

然后为Py2Neko类添加了一些方法

def visit_Print(self, node):
    print "Print :"

def visit_Assign(self, node):
    print "Assign :"

def visit_Expr(self, node):
    print "Expr :"

但是当它遇到一个"打印"声明或一个表达或一个表达时,它似乎停止了,而不是更进一步.

它输出:

Module(body=[Assign(targets=[Name(id='a', ctx=Store())], value=BinOp(left=Num(n=1), op=Add(),       right=Num(n=2)))])
Module
Assign …

我有一种语言与C++类似的语法.词法分析器和解析器就位并产生正确的AST.对于最大的部分,后端也已完成.

编译器用于创建类型的基本系统非常简单:所有类型都被认为是内置的,所有实例都是全局的.因此,只有一个简单的映射,它将类型名称与创建变量的方法相匹配,该变量基本上是一个泛型类型,如boost :: any.另一个变量名称为key且Variable为value的映射用作全局范围:

std::map< std::string, std::function< Variable() > typeList;

  //register some types
typeList[ "X" ] = Variable::Create<X>;
typeList[ "Y" ] = CreateInstanceOfY;
....

当编译器获得AST节点进行初始化时就像X myVar;它基本上一样

std::map< std::string, Variable > globalScope;
globalScope[ "myVar" ] = typeList[ "X" ]();

当稍后使用myVar时,可以通过简单的类型调度来访问它

X& x = myVar.GetReference<X>();

现在我想扩展一下并使用简单的模板.假设存在使用向量实现的类型"数组".我可以注册一切像

typeList[ "array<X>" ] = Variable::Create< std::vector< X > >;

但这不是很可管理的,因为它必须对所有组合重复.理想情况下,我需要功能允许写这样的东西:

typeList.CreateTemplateVariable( "array", "X" )

然后会创建一个内部包含std :: vector <X>的Variable实例.我努力了,但无法弄清楚如何做到这一点.也许我只是用简单的类型映射开始了错误的方式,这就是我无法理解它的原因.

所以问题很简单:是否可以这样做？如何？

有没有一个开源的java api允许比较两个抽象语法树的java源代码？

我想看看两个语法树之间的差异,类似于在diff工具中完成的方式.

我有一个AST(抽象语法树),现在我想测试我的编译器,给它2个或更多的数字,并期望输出与数学运算的结果(如计算器).

我的问题是,构建解释器的最佳方法是什么？访问AST节点是递归的,所以我不知道有多少封装计算存在,直到我到达树的末尾.但由于这是通过迭代迭代完成的,我怎样才能最终完成所有操作？

谢谢

我一直对编程/解释器设计/实现感兴趣,只要我编程(现在只有5年),它总是看起来像幕后的"魔术",没有人真正谈论过(我至少知道) 2个用于操作系统开发的论坛,但我不知道编译器/解释器/语言开发的任何社区).无论如何,最近我决定开始自己的工作,希望扩展我对整个编程的知识(嘿,这很有趣:).因此,基于我所拥有的有限数量的阅读材料和维基百科,我已经为编译器/解释器开发了这个组件的概念:

源代码 - >词法分析 - >抽象语法树 - >句法分析 - >语义分析 - >代码生成 - >可执行代码.

(我知道代码生成和可执行代码还有更多,但我还没有那么远:)

有了这些知识,我创建了一个非常基本的词法分析器(在Java中)从源文件中获取输入,并将标记输出到另一个文件中.示例输入/输出如下所示:

输入:

int a := 2
if(a = 3) then
    print "Yay!"
endif

输出(来自词法分析器):

INTEGER
A
ASSIGN
2
IF
L_PAR
A
COMP
3
R_PAR
THEN
PRINT
YAY!
ENDIF

就个人而言,我认为从那里进行语法/语义分析,甚至可能甚至是代码生成都会非常容易,这让我有一个问题:为什么使用AST,当我的词法分析员看起来做得同样好的时候呢？但是,我用来研究这个主题的100%的资源似乎都坚持认为这是任何编译器/解释器的必要部分.我是否错过了AST的真正含义(显示程序逻辑流程的树)？

TL; DR:目前正在开发编译器,完成词法分析器,在我看来,输出将使得简单的句法分析/语义分析,而不是做AST.那为什么要用一个？我错过了一点吗？

谢谢!

我有一个ANTLR3语法,可以构建一个抽象语法树.我正在寻求升级到ANTLR4.但是,似乎ANTLR4只构建解析树而不是抽象语法树.例如,output=AST不再识别该选项.此外,"The Definitive ANTLR4 reference"的文本中既没有出现"AST"也没有出现"抽象语法".

我想知道我是否遗漏了什么.

我的应用程序目前知道如何爬行ANTLR3生成的AST.更改它以处理解析树并非不可能,但这将是一项工作.在我开始走这条路之前,我想确定它是必要的.

我正在尝试编写一段代码,它将采用ANTLR4解析器并使用它为输入生成AST,类似于grun(misc.TestRig)上的-tree选项给出的输入.但是,我还希望输出包含所有行号/偏移信息.

例如,而不是打印

(add (int 5) '+' (int 6))

我想得到

(add (int 5 [line 3, offset 6:7]) '+' (int 6 [line 3, offset 8:9]) [line 3, offset 5:10])

或类似的东西.

ANTLR4还没有大量的访问者示例,但我很确定我可以通过复制toStringTree(由grun使用)的默认实现来完成大部分工作.但是,我没有看到有关行号或偏移量的任何信息.

我希望能够编写如下的超简单代码:

String visit(ParseTree t) {
    return "(" + t.productionName + t.visitChildren() + t.lineNumber + ")";
}

但它似乎并不那么简单.我猜我应该能够从解析器中获取行号信息,但我还没弄清楚如何这样做.如何在遍历中获取此行号/偏移量信息？

为了填写下面解决方案中的几个空白,我使用了:

List<String> ruleNames = Arrays.asList(parser.getRuleNames());
parser.setBuildParseTree(true);
ParserRuleContext prc = parser.program();
ParseTree tree = prc;

得到的tree和ruleNames. program是我语法中顶级作品的名称.

我使用ANTLR4为PL/SQL代码生成抽象语法树(AST).对于某些查询,它工作正常,但对于某些代码,它生成一个只有一个节点不正确的AST.

例如:

DECLARE
   a   RAW;            -- migrate to BLOB
   b   LONG RAW;       -- migrate to BLOB
   c   LONG VARCHAR;   -- migrate to LOB
   d   LONG;           -- migrate to LOB
   x   VARCHAR;
   CURSOR mycur RETURN LONG;     -- should flag
   FUNCTION myfunc RETURN LONG RAW    -- should flag
   IS
      z  LONG RAW;    -- should flag
   BEGIN 
      RETURN z;
   END;  
BEGIN
   SELECT mycol, CAST(col2 AS RAW)      -- should flag
     INTO a 
     FROM mytab 
    WHERE (b IS OF …

今年我一直在研究Perl6中的代码问题,并试图用语法来解析第3天的输入.

给出这种形式的输入:#1 @ 1,3: 4x4和我创建的这个语法:

grammar Claim {
  token TOP {
    '#' <id> \s* '@' \s* <coordinates> ':' \s* <dimensions>
  }

  token digits {
    <digit>+
  }

  token id {
    <digits>
  }

  token coordinates {
    <digits> ',' <digits>
  }

  token dimensions {
    <digits> 'x' <digits>
  }
}

say Claim.parse('#1 @ 1,3: 4x4');

我有兴趣从坐标中提取匹配的实际标记,即id,x + y,以及从结果解析的维度中提取高度+宽度.我知道我可以将它们从生成的Match对象中拉出来Claim.parse(<input>),但我必须深入研究每个语法生成以获得我需要的值,例如

say $match<id>.hash<digits>.<digit>;

这看起来有点乱,是否有更好的方法？