精华内容
下载资源
问答
  • 解析树 完成树的实现之后,现在我们来看一个例子,告诉你怎么样利用树去解决一些实际问题。在这个章节,我们来研究解析树解析树常常用于真实世界的结构表示,例如句子或数学表达式。 图 1:一个简单句的解析树 图...
  • 其次,提出了一种丰富的解析树结构,既可以很好地保留必要的结构化信息,又可以通过区分解析树结构的各个部分来有效避免噪声。 对CoNLL'; 2005共享任务的评估表明,新的树内核和丰富的解析树结构都对SRL做出了很大...
  • 2017/3/12 32.1 解析器 访问Python解析树 Python 3.6.1rc1文档 32.1parser访问的Python解析树 该parser模块为Python的内部解析器和字节码编译器提供了一个接口此接口的主要目的是允 许Python代码编辑Python表达式的...
  • 字符串解析器 快速创建用于解析字符串的解析树的工具
  • 用于算术表达式的递归下降解析器,具有解析树和测试的可视化 任务: 为算术表达式(带加号、二元和一元减号、乘法和括号)设计一个简单的上下文无关文法,以消除左递归和右分支 开发一个词法分析器(lexer),跳过...
  • Drain基于固定深度解析树

    千次阅读 2019-12-18 17:15:56
    Drain可以以流方式实时解析日志,为了加快解析过程,Drain使用了固定深度的解析树(请参见上图) 根节点为树的顶层,底层为叶子节点,其他层为内部节点。 根节点和内部节点用于搜索,叶子节点存储日志组(包含日志...

    论文地址:http://jmzhu.logpai.com/pub/pjhe_icws2017.pdf

    Drain可以以流方式实时解析日志,为了加快解析过程,Drain使用了固定深度的解析树(请参见上图)

    根节点为树的顶层,底层为叶子节点,其他层为内部节

    展开全文
  • 其次,提出了一种丰富的解析树结构,以从解析树中很好地导出必要的结构信息,例如适当的潜在注释。 对ACE RDC语料库的评估表明,新的树核和丰富的解析树结构都对R,DC做出了重要贡献,并且我们的树核方法远远优于...
  • 该程序包仅解析Mercury代码,并返回JSON格式的解析树。 它在环境中用于将代码转换为声音和视觉对象。 在将来的版本中,它将在基于浏览器的Mercury中使用。 :pager: 汞? Mercury是用于算法电子音乐的实时编码的一...
  • 解析树 完成树的实现之后,现在我们来看一个例子,告诉你怎么样利用树去解决一些实际问题。在这个章节,我们来研究解析树解析树常常用于真实世界的结构表示,例如句子或数学表达式。 图 1:一个简单句的...

    解析树

    完成树的实现之后,现在我们来看一个例子,告诉你怎么样利用树去解决一些实际问题。在这个章节,我们来研究解析树。解析树常常用于真实世界的结构表示,例如句子或数学表达式。

    图 1:一个简单句的解析树

    图 1 显示了一个简单句的层级结构。将一个句子表示为一个树,能使我们通过利用子树来处理句子中的每个独立的结构。

    图 2: ((7+3)*(5−2)) 的解析树

    如图 2 所示,我们能将一个类似于 ((7+3)*(5−2)) 的数学表达式表示出一个解析树。我们已经研究过全括号表达式,那么我们怎样理解这个表达式呢?我们知道乘法比加或者减有着更高的优先级。因为括号的关系,我们在做乘法运算之前,需要先计算括号内的加法或者减法。树的层级结构帮我们理解了整个表达式的运算顺序。在计算最顶上的乘法运算前,我们先要计算子树中的加法和减法运算。左子树的加法运算结果为 10,右子树的减法运算结果为 3。利用树的层级结构,一旦我们计算出了子节点中表达式的结果,我们能够将整个子树用一个节点来替换。运用这个替换步骤,我们得到一个简单的树,如图 3 所示。

    图 3: ((7+3)*(5−2)) 的化简后的解析树

    在本章的其余部分,我们将更加详细地研究解析树。尤其是:

    • 怎样根据一个全括号数学表达式来建立其对应的解析树
    • 怎样计算解析树中数学表达式的值
    • 怎样根据一个解析树还原数学表达式

    建立解析树的第一步,将表达式字符串分解成符号保存在列表里。这里有四种符号需要我们考虑:左括号,操作符和操作数。我们知道读到一个左括号时,我们将开始一个新的表达式,因此我们创建一个子树来对应这个新的表达式。相反,每当我们读到一个右括号,我们就得结束这个表达式。另外,操作数将成为叶节点和他们所属的操作符的子节点。最后,我们知道每个操作符都应该有一个左子节点和一个右子节点。通过上面的分析我们定义以下四条规则:

    1. 如果当前读入的字符是'(',添加一个新的节点作为当前节点的左子节点,并下降到左子节点处。
    2. 如果当前读入的字符在列表['+', '-', '/', '*']中,将当前节点的根值设置为当前读入的字符。添加一个新的节点作为当前节点的右子节点,并下降到右子节点处。
    3. 如果当前读入的字符是一个数字,将当前节点的根值设置为该数字,并返回到它的父节点。
    4. 如果当前读入的字符是’)’,返回当前节点的父节点。

    在我们编写 Python 代码之前,让我们一起看一个上述的例子。我们将使用 (3+(4*5))
    这个表达式。我们将表达式分解为如下的字符列表:['(', '3', '+', '(', '4', '*', '5' ,')',')']。一开始,我们从一个仅包括一个空的根节点的解析树开始。如图 4,该图说明了随着每个新的字符被读入后该解析树的内容和结构。








    图 4:解析树结构的步骤图

    观察图 4,让我们一步一步地过一遍:

    1. 创建一个空的树。
    2. 读如(作为第一个字符,根据规则 1,创建一个新的节点作为当前节点的左子结点,并将当前节点变为这个新的子节点。
    3. 读入3作为下一个字符。根据规则 3,将当前节点的根值赋值为3然后返回当前节点的父节点。
    4. 读入+作为下一个字符。根据规则 2,将当前节点的根值赋值为+,然后添加一个新的节点作为其右子节点,并且将当前节点变为这个新的子节点。
    5. 读入(作为下一个字符。根据规则 1,创建一个新的节点作为当前节点的左子结点,并将当前节点变为这个新的子节点。
    6. 读入4作为下一个字符。根据规则 3,将当前节点的根值赋值为4然后返回当前节点的父节点
    7. 读入*作为下一个字符。根据规则 2,将当前节点的根值赋值为*,然后添加一个新的节点作为其右子节点,并且将当前节点变为这个新的子节点。
    8. 读入5作为下一个字符。根据规则 3,将当前节点的根值赋值为5然后返回当前节点的父节点
    9. 读入)作为下一个字符。根据规则 4,我们将当前节点变为当前节点*的父节点。
    10. 读入)作为下一个字符。根据规则 4,我们将当前节点变为当前节点+的父节点,因为当前节点没有父节点,所以我们已经完成解析树的构建。

    通过上面给出的例子,很明显我们需要跟踪当前节点和当前节点的父节点。树提供给我们一个获得子节点的方法——通过getLeftChildgetRightChild方法,但是我们怎么样来跟踪一个节点的父节点呢?一个简单的方法就是在我们遍历整个树的过程中利用栈跟踪父节点。当我们想要下降到当前节点的子节点时,我们先将当前节点压入栈。当我们想要返回当前节点的父节点时,我们从栈中弹出该父节点。

    通过上述的规则,使用栈和二叉树来操作,我们现在编写函数来创建解析树。解析树生成函数的代码如下所示。

    这四条建立解析树的规则体现在四个if从句,它们分别在第 11,15,19,24 行。如上面所说的,在这几处你都能看到规则的代码实现,并需要调用一些BinaryTreeStack的方法。这个函数中唯一的错误检查是在else语句中,一旦我们从列表中读入的字符不能辨认,我们就会报一个ValueError的异常。现在我们已经建立了一个解析树,我们能用它来干什么呢?第一个例子,我们写一个函数来计算解析树的值,并返回该计算的数字结果。为了实现这个函数要利用树的层级结构。重新看一下图 2,回想一下我们能够将原始的树替换为简化后的树(图 3)。这提示我们写一个通过递归计算每个子树的值来计算整个解析树的值。

    就像我们以前实现递归算法那样,我们将从基点来设计递归计算表达式值的函数。这个递归算法的自然基点是检查操作符是否为叶节点。在解析树中,叶节点总是操作数。因为数字变量如整数和浮点数不需要更多的操作,这个求值函数只需要简单地返回叶节点中存储的数字就可以。使函数走向基点的递归过程就是调用求值函数计算当前节点的左子树、右子树的值。递归调用使我们朝着叶节点,沿着树下降。

    为了将两个递归调用的值整合在一起,我们只需简单地将存在父节点中的操作符应用到两个子节点返回的结果。在图 3 中,我们能看到两个子节点的值,分别为 10 和 3。对他们使用乘法运算得到最终结果 30。

    递归求值函数的代码如 Listing1 所示,我们得到当前节点的左子节点、右子节点的参数。如果左右子节点的值都是 None,我们就能知道这个当前节点是一个叶节点。这个检查在第 7 行。如果当前节点不是一个叶节点,查找当前节点的操作符,并用到它左右孩子的返回值上。

    为了实现这个算法,我们使用了字典,键值分别为'+','-','*''/'。存在字典里的值是 Python 的操作数模块中的函数。这个操作数模块为我们提供了很多常用函数的操作符。当我们在字典中查找一个操作符时,相应的操作数变量被取回。既然是函数,我们可以通过调用函数的方式来计算算式,如function(param1,param2)。所以查找opers['+'](2,2)就等价于operator.add(2,2)

    Listing 1

    最后,我们将在图 4 中创建的解析树上遍历求值。当我们第一次调用求值函数时,我们传递解析树参数parseTree,作为整个树的根。然后我们获得左右子树的引用来确保它们一定存在。递归调用在第 9 行。我们从查看树根中的操作符开始,这是一个'+'。这个'+'操作符找到operator.add函数调用,且有两个参数。通常对一个 Python 函数调用而言,Python 第一件做的事情就是计算传给函数的参数值。通过从左到右的求值过程,第一个递归调用从左边开始。在第一个递归调用中,求值函数用来计算左子树。我们发现这个节点没有左、右子树,所以我们在一个叶节点上。当我们在叶节点上时,我们仅仅是返回这个叶节点存储的数值作为求值函数的结果。因此我们返回整数 3。

    现在,为了顶级调用operator.add函数,我们计算好其中一个参数了,但我们还没有完。继续从左到右计算参数,现在递归调用求值函数用来计算根节点的右子节点。我们发现这个节点既有左节点又有右节点,所以我们查找这个节点中存储的操作符,是'*',然后调用这个操作数函数并将它的左右子节点作为函数的两个参数。此时再对它的两个节点调用函数,这时发现它的左右子节点是叶子,分别返回两个整数 4 和 5。求出这两个参数值后,我们返回operator.mul(4,5)的值。此时,我们已经计算好了顶级操作符'+'的两个操作数了,所有需要做的只是完成调用函数operator.add(3,20)即可。这个结果就是整个表达式树 (3+(4*5)) 的值,这个值是 23。

    树的遍历

    之前我们已经了解了树的基本功能,现在我们来看一些应用模式。按照节点的访问方式不同,模式可分为 3 种。这三种方式常被用于访问树的节点,它们之间的不同在于访问每个节点的次序不同。我们把这种对所有节点的访问称为遍历(traversal)。这三种遍历分别叫做先序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。我们来给出它们的详细定义,然后举例看看它们的应用。

    1. 先序遍历
      在先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树。
    2. 中序遍历
      在中序遍历中,我们递归使用中序遍历访问左子树,然后访问根节点,最后再递归使用中序遍历访问右子树。
    3. 后序遍历
      在后序遍历中,我们先递归使用后序遍历访问左子树和右子树,最后访问根节点。

    现在我们用几个例子来说明这三种不同的遍历。首先我们先看看先序遍历。我们用树来表示一本书,来看看先序遍历的方式。书是树的根节点,每一章是根节点的子节点,每一节是章节的子节点,每一小节是每一章节的子节点,以此类推。图 5 是一本书只取了两章的一部分。虽然遍历的算法适用于含有任意多子树的树结构,但我们目前为止只谈二叉树。

    图 5:用树结构来表示一本书

    设想你要从头到尾阅读这本书。先序遍历恰好符合这种顺序。从根节点(书)开始,我们按照先序遍历的顺序来阅读。我们递归地先序遍历左子树,在这里是第一章,我们继续递归地先序遍历访问左子树第一节 1.1。第一节 1.1 没有子节点,我们不再递归下去。当我们阅读完 1.1 节后我们回到第一章,这时我们还需要递归地访问第一章的右子树 1.2 节。由于我们先访问左子树,我们先看 1.2.1 节,再看 1.2.2 节。当 1.2 节读完后,我们又回到第一章。之后我们再返回根节点(书)然后按照上述步骤访问第二章。

    由于用递归来编写遍历,先序遍历的代码异常的简洁优雅。Listing 2 给出了一个二叉树的先序遍历的 Python 代码。

    Listing 2

    我们也可以把先序遍历作为BinaryTree类中的内置方法,这部分代码如 Listing 3 所示。注意这一代码从外部移到内部所产生的变化。一般来说,我们只是将tree换成了self。但是我们也要修改代码的基点。内置方法在递归进行先序遍历之前必须检查左右子树是否存在。

    Listing 3

    内置和外置方法哪种更好一些呢?一般来说preorder作为一个外置方法比较好,原因是,我们很少是单纯地为了遍历而遍历,这个过程中总是要做点其他事情。事实上我们马上就会看到后序遍历的算法和我们之前写的表达式树求值的代码很相似。只是我们接下来将按照外部函数的形式书写遍历的代码。后序遍历的代码如 Listing 4 所示,它除了将print语句移到末尾之外和先序遍历的代码几乎一样。

    Listing 4

    我们已经见过了后序遍历的一般应用,也就是通过表达式树求值。我们再来看 Listing 1,我们先求左子树的值,再求右子树的值,然后将它们利用根节点的运算连在一起。假设我们的二叉树只存储表达式树的数据。我们来改写求值函数并尽量模仿后序遍历的代码,如 Listing 5 所示。

    Listing 5

    我们发现 Listing 5 的形式和 Listing 4 是一样的,区别在于 Listing 4 中我们输出键值而在 Listing 5 中我们返回键值。这使我们可以通过第 6 行和第 7 行将递归得到的值存储起来。之后我们利用这些保存起来的值和第 9 行的运算符一起运算。

    在这节的最后我们来看看中序遍历。在中序遍历中,我们先访问左子树,之后是根节点,最后访问右子树。 Listing 6 给出了中序遍历的代码。我们发现这三种遍历的函数代码只是调换了输出语句的位置而不改动递归语句。

    Listing 6

    当我们对一个解析树作中序遍历时,得到表达式的原来形式,没有任何括号。我们尝试修改中序遍历的算法使我们得到全括号表达式。只要做如下修改:在递归访问左子树之前输出左括号,然后在访问右子树之后输出右括号。修改的代码见 Listing 7。

    Listing 7

    我们发现printexp函数对每个数字也加了括号,这些括号显然没必要加。

    展开全文
  • 的遍历包括前序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。 前序遍历(preorder):在前序遍历中,先访问根节点,然后递归地前序遍历访问左子树,再递归地前序遍历访问右子。 中序遍历(inorder)...

    解析树:也称具体语法树(concrete syntax tree),是一个反映某种形式语言字符串的语法关系的有根有序树。解析树一般按照两种相反的法则生成,一种是依存语法,一种是短语结构语法。解析树和抽象语法树是不同的。

    树的遍历包括前序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。

    前序遍历(preorder):在前序遍历中,先访问根节点,然后递归地前序遍历访问左子树,再递归地前序遍历访问右子树。
    中序遍历(inorder):在中序遍历中,递归地中序遍历访问左子树,然后访问根节点,最后再递归地中序遍历访问右子树。
    后序遍历(postorder):在后序遍历中,先递归地后序遍历访问左子树和右子树,最后访问根节点。

    完整代码:

    import operator  									#操作符模块
    
    # 自定义栈类
    class Stack(object):
         def __init__(self):							#初始化空栈
             self.items = []
    
         def isEmpty(self):								#是否为空
             return self.items == []
    
         def push(self, item):							#入栈
             self.items.append(item)
    
         def pop(self):									#出栈
             return self.items.pop()
    
         def peek(self):								#查看栈顶元素
             return self.items[len(self.items)-1]
    
         def size(self):								#查看栈的大小
             return len(self.items)
    
    # 自定义二叉树类
    class BinaryTree(object):
    	# 初始化二叉树
    	def __init__(self, rootObj):
    		self.root = rootObj
    		self.leftChild = None
    		self.rightChild = None
    
    	# 插入左子树
    	def insertLeft(self, newNode):
    		if self.leftChild == None:					#若左子树为空,则
    			self.leftChild = BinaryTree(newNode)	#直接生成左子树
    		else:										
    			t = BinaryTree(newNode)					#生成初始二叉树
    			t.leftChild = self.leftChild 			#将原左子树赋值给新二叉树的左子树
    			self.leftChild = t 						#再将新二叉树赋值给原二叉树的左子树
    
    	# 插入右子树
    	def insertRight(self, newNode):
    		if self.rightChild == None:
    			self.rightChild = BinaryTree(newNode)
    		else:
    			t = BinaryTree(newNode)
    			t.rightChild = self.rightChild
    			self.rightChild = t
    
    	# 获取右子树
    	def getRightChild(self):
    		return self.rightChild
    
    	# 获取左子树
    	def getLeftChild(self):
    		return self.leftChild
    
    	# 设置根节点值
    	def setRootVal(self, obj):
    		self.root = obj
    
    	# 获取根节点值
    	def getRootVal(self):
    		return self.root
    
    # 解析树生成函数
    def buildParseTree(fpexp):
    	fplist = fpexp.split()								#将传入的完全括号表达式以空格分割成list
    	pStack = Stack()									#实例化栈类
    	eTree = BinaryTree('')								#实例化二叉树类,必须有''
    	pStack.push(eTree)									#将空二叉树的根节点(空)入栈
    	currentTree = eTree 								#将空二叉树的根节点(空)作为当前节点
    	for i in fplist:									#循环处理表达式list元素
    		if i == '(':									#遇到"(",则
    			currentTree.insertLeft('')					#创建当前节点的空左子节点
    			pStack.push(currentTree)					#将当前节点入栈
    			currentTree = currentTree.getLeftChild()	#将该左子节点作为当前节点
    		elif i not in ['+', '-', '*', '/', ')']:		#遇到操作数,则
    			currentTree.setRootVal(int(i))				#将操作数设为当前节点的根值
    			currentTree = pStack.pop() 					#将出栈节点(父节点)作为当前节点
    		elif i in ['+', '-', '*', '/']:					#遇到操作符,则
    			currentTree.setRootVal(i)					#将操作符设为当前节点的根植
    			currentTree.insertRight('')					#创建当前节点的空右子节点
    			pStack.push(currentTree)					#将当前节点入栈
    			currentTree = currentTree.getRightChild()	#将该右子节点作为当前节点
    		elif i == ')':									#遇到")",则
    			currentTree = pStack.pop()					#将出栈节点(父节点)作为当前节点
    		else:
    			raise ValueError 							#抛出异常
    	return eTree
    
    # 求值函数,parseTree为当前整个解析树的根节点
    def evaluate(parseTree):
    	# opers字典是操作符与其对应的运算函数的集合
    	opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
    	leftC = parseTree.getLeftChild()			#获取解析树根节点的左子树
    	rightC = parseTree.getRightChild()			#获取解析树根节点的右子树
    	if leftC and rightC:						#若当前节点存在左右子树,说明该节点不是叶节点,则
    		fn = opers[parseTree.getRootVal()]		#获取解析树根节点值对应的opers字典值作为运算函数
    		return fn(evaluate(leftC),evaluate(rightC))	#将递归获取的左右子树值运算后返回
    	else:										#若当前节点不存在左右子树,说明该节点是叶节点,则
    		return parseTree.getRootVal()			#返回解析树的根节点值
    
    # 前序遍历函数
    def preorder(tree):
    	if tree:									#若树不为None,则
    		print(tree.getRootVal())				#打印根节点值
    		preorder(tree.getLeftChild())			#前序遍历左子树
    		preorder(tree.getRightChild())			#前序遍历右子树
    
    # 中序遍历函数
    def inorder(tree):
    	if tree:									#若树不为None,则
    		inorder(tree.getLeftChild())			#中序遍历左子树
    		print(tree.getRootVal())				#打印根节点值
    		inorder(tree.getRightChild())			#中序遍历右子树
    
    # 后序遍历函数
    def postorder(tree):
    	if tree:									#若树不为None,则
    		postorder(tree.getLeftChild())			#后序遍历左子树
    		postorder(tree.getRightChild())			#后序遍历右子树
    		print(tree.getRootVal())				#打印根节点值
    
    pt = buildParseTree("( ( 10 + 5 ) * 3 )")		#将完全括号表达式生成解析树
    print(evaluate(pt))								#求该解析树的值
    preorder(pt)									#前序遍历树
    inorder(pt)										#中序遍历树
    postorder(pt) 									#后序遍历树
    

    结果为:

    45
    *
    +
    10
    5
    3
    10
    +
    5
    *
    3
    10
    5
    +
    3
    *
    
    展开全文
  • 绘制解析树 解析树 (S (NP (PRP I)) (VP (VBP have) (NP (DT a) (NN book))) (. .)) JS库 d3.js: ://d3js.org/ dagre-d3: :
  • 2017/3/12 32.4 symbol 用于Python解析树的常量 Python 3.6.1rc1文档 32.4symbol 用于Python解析树的常量 源代码 Lib / symbol.py 该模块提供表示解析树的内部节点的数值的常数与大多数Python常量不同 它们使用小写...
  • 解析树结构并导出 excel 自动计算并合并单元格 树结构保留 API简洁 高度内聚 依赖 FileSaver.js exceljs 数据格式要求 [ { value: "value 1", list: [ { value: "value 2" }, ] } ] 示例 // 数据 const ...
  • 2017/3/12 32.5 token 用于Python解析树的常量 Python 3.6.1rc1文档 32.5token 用于Python解析树的常量 源代码 Lib / token.py 该模块提供了表示分析树 终端令牌 的叶节点的数值的常量有关Grammar/Grammar 语言语 法...
  • 编译器 使用 lex 和 yacc ,生成解析树和符号表
  • 生成解析树 (AST) 的快速正则表达式引擎。 它以匹配的文本大小的线性时间执行此操作,并以模式大小的 O(m*log(m)) 缩放。 算法 该算法描述于 尼科·施瓦茨。 可扩展的代码克隆检测。 博士论文,伯尔尼大学,2014 年...
  • d3-dependency-parse-tree 使用 D3 库进行依赖解析树可视化。
  • 解析树字符串化为普通的 SSA/ASS 字幕格式。 应用程序接口 assStringify(ass) 返回一个文本字符串。 有关示例,请参见test/sample.ass 。 参考 有关的 - SSA/ASS 解析器。 安装 npm install ass-stringify 执照...
  • Tex2py转换成LaTeX的一个Python解析树,用 。 这允许您使用默认或自定义层次结构将乳胶文件导航为树。 有关降价分析树,请参见 。 注意tex2py当前仅支持Python3。 由创建 安装 通过pip安装。 pip install tex2py...
  • hive解析树

    千次阅读 2016-11-17 15:19:09
    Hive的ParseDriver类中,通过antlr生成的语法AST。 例子:Select name,ip from zpc where age > 10 and area in (select area from city) (TOK_QUERY  (TOK_FROM  (TOK_TABREF  (TOK_TABNAME zpc)...
    Hive的ParseDriver类中,通过antlr生成的语法树AST。
    例子:Select name,ip from zpc where age > 10 and area in (select area from city)


    (TOK_QUERY 
    (TOK_FROM 
    (TOK_TABREF 
    (TOK_TABNAME zpc)
    )
    (TOK_INSERT 
    (TOK_DESTINATION (TOK_DIR TOK_TMP_FILE)) 
    (TOK_SELECT 
    (TOK_SELEXPR (TOK_TABLE_OR_COL name)) (TOK_SELEXPR (TOK_TABLE_OR_COL ip))
    (TOK_WHERE 
    (and 
    (> (TOK_TABLE_OR_COL age) 10) 
    (TOK_SUBQUERY_EXPR (TOK_SUBQUERY_OP in) 
    (TOK_QUERY 
    (TOK_FROM 
    (TOK_TABREF 
    (TOK_TABNAME city)
    )
    (TOK_INSERT 
    (TOK_DESTINATION (TOK_DIR TOK_TMP_FILE)) 
    (TOK_SELECT 
    (TOK_SELEXPR (TOK_TABLE_OR_COL area))
    )
    )
    (TOK_TABLE_OR_COL area)
    )
    )
    )
    )
    )


    注:1.TOK_INSERT个节点是在语法改写中特意 增加了的一个节点。原因是Hive中所有查询的数据均会保存在HDFS临时的文件中,无论是中间的子查询还是查询最终的结果,Insert语句最终会将数 据写入表所在的HDFS目录下。
    2. 每个表生成一个TOK_TABREF节点。

    目标:可以遍历AST,获取到table和table对应的列名。
    另外可以从mysql中获取table的列及类型对应信息。(调用desc table即可)。

    调用hive树的遍历:((SemanticAnalyzer) sem).doPhase1(ast, qb, null);
    QBParseInfo info = qb.getParseInfo();
    QBParseInfo中可以获取表名,分区名,列名,别名等信息。
    判断QB的属性和方法后,觉得QB中的信息并不是想要的信息。

    结论:自定义遍历器,来遍历AST树中的表名。遍历器的实现其实也很简单,深度遍历,判断对应的token节点获取相应的值。


    hiveQL编译过程参考:


    展开全文
  • source_size 一个简单的python脚本,以行,标记和解析树节点的形式衡量源文件的大小
  • 多态——解析树实例分析

    千次阅读 2009-10-02 19:51:00
    本文已搬家至【C++学习】多态——解析树实例分析
  • js解析树结构菜单

    2012-09-26 15:15:44
    前端通过js把数据库里的菜单展现出来,形成动态的菜单!
  • JavaCC、解析树和 XQuery 语法

    千次阅读 2006-11-08 09:06:00
    第 1 部分使用 BNF 和 JavaCC 构建定制的解析器在简要讨论了语法、解析器...第 2 部分接着将演示如何使用辅助工具 ― JJTree 来构建同一解析的解析树表示,以及如何在运行时遍历该树,以发现其状态信息。文章将以开发构
  • JavaCC、解析树和 XQuery 语法,第 2 部分 使用 JJTree 构建和遍历定制解析树
  • LISP 就是语法解析树的前缀表达

    千次阅读 2006-04-04 01:22:00
    LISP 就是语法解析树的前缀表达,有趣的说法,哈哈。有空看看这本书:How to Design Programs
  • Android开发之解析树形json数据

    千次阅读 2018-06-12 16:57:06
    形json数据不同于一般的json数据,其大多有多层嵌套。如果用Android Studio中的GsonFormat或者其他工具往往不能正确生成数据格式。//形结构[ { "name": "a", "size": "4&...
  • 使用NLTK找出所有的语法解析树

    千次阅读 2018-11-21 17:16:08
    然后使用nltk对这些句子进行语法树解析,打印最终语法列表的长度即可: from nltk import load_parser sentences=['fall leaves fall', 'fall leaves fall and spring leaves spring', 'the fall leaves left'...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 279,226
精华内容 111,690
关键字:

解析树