宜昌教育云网站建设,兰州网站设计有限公司,做合约交易哪个网站好,wordpress 新建数据库文章目录 1 词法分析2 语法分析3 遍历语法分析树3.1 Listener3.2 Visitor 4 总结 1 词法分析
词法分析就是对给定的字符串进行分割#xff0c;提取出其中的单词。
在antlr4中#xff0c;词法规则的名称的首字母需要大写#xff0c;右侧必须是终结符#xff0c;通常将词法… 文章目录 1 词法分析2 语法分析3 遍历语法分析树3.1 Listener3.2 Visitor 4 总结 1 词法分析
词法分析就是对给定的字符串进行分割提取出其中的单词。
在antlr4中词法规则的名称的首字母需要大写右侧必须是终结符通常将词法规则的名称全部大写。
例如要匹配C语言中的变量名就需要知道C语言中的变量名的规范
变量只能由字母、数字、下划线组成变量名的第一个字符必须是字母或者下划线不能是数字
于是变量名的词法规则就可以是
VARNAME: [a-zA-Z_][a-zA-Z_0-9]*;antlr4提供关键字fragment用于定义词法片段可以把比较常用的正则表达式的一部分定义为片段进行复用它本身并不会生成任何标记但是能够提高可读性。
fragment DIGIT : [0-9]
fragment ALPHABET: [a-zA-Z]UNDERLINE: _;VARNAME: (ALPHABET|UNDERLINE)(ALPHABET|UNDERLINE|DIGIT)*首先分别定义字母和数字的fragment然后定义下划线的词法规则再结合字母、数字、下划线定义变量名的词法规则。
2 语法分析
词法分析得到单词流后就可以通过语法分析生成语法分析树。
语法规则的民成的首字母需要小写以区分词法规则通常将语法规则的名称全部小写。
例如要匹配一个赋值表达式就需要知道赋值表达式由哪些部分构成。
赋值表达式通常由四部分构成
等号左侧左侧通常是变量名但是也可能在定义变量时进行初始化不过也可能赋值给指针等号等号右侧右侧可能是常量也可能是函数调用表达式结尾的分号
这里为了简化处理只实现以下的赋值语句
等号左侧只是变量名等号右侧只有整数常量
语法规则就是
ASSIGN: ;
SEMI: ;;
NUMBER: DIGIT;assign_expr: VARNAME ASSIGN NUMBER SEMI;3 遍历语法分析树
在编写antlr4的语法规则文件时可以在其中加入特定语言的动作例如需要在访问到某个规则的时候输出得到的字符串就可以直接将该逻辑写在语法规则文件中但是这种方式会使得语法规则文件和解析程序耦合不同语言需要不同的节点访问逻辑因此编写完成语法规则文件后通常生成对应语言的解析程序。利用该解析程序可以实现对语法分析树的遍历。
下一步就是对语法分析树进行遍历为了方便对antlr4提供了两种遍历语法分析树的模式
ListenerVisitor
在使用antlr4工具生成对应语言的程序时可以通过-listener和-visitor选项生成对应的遍历语法分析树的代码-listener是默认选项也就是默认得到Listener类型的遍历器。
在说明Listener和Visitor之前需要了解下语法分析树的结构和相关类型以下的{GrammarName}表示语法名称也就是grammar语句中的名称{RuleName}表示语法文件中的规则名称也就是冒号前面的单词。
antlr4为我们生成的解析器{GrammarName}Parser继承自antlr4.Parser{GrammarName}Parser中会对每条规则定义一个类类继承自antlr4.ParserRuleContext例如如果规则名是expr就会创建一个类class ExprContext(ParserRuleContext)同时对每条规则也会创建一个对应的方法用于返回对应的类对象例如如果规则名是expr那么方法就是def expr(self)该方法会返回ExprContext的对象。在创建{GrammarName}Parser对象时需要传递antlr4.TokenStream作为参数antlr4.TokenStream可以理解为词法分析的单词流解析器就是对单词流进行分析。 在创建{GrammarName}Parser解析器对象后就可以通过第一条规则的规则名作为方法名得到语法分析树的根节点接下来就可以通过Listener或者Visitor机制遍历该语法分析树。语法分析树的每个节点对应一条规则都是继承自antlr4.ParserRuleContext的对象而叶子节点则是词法分析的单词类型是TerminalNodeImpl。 因此在实际的开发者解析语法分析树的主函数代码通常是
# 使用输入的字符串创建输入流然后将输入流给到词法分析器
# 使用词法分析器就得到TokenStream对象
input_stream InputStream(10112\n)
lexer exprLexer(input_stream)
token_stream CommonTokenStream(lexer)# 使用TokenStream对象创建antlr4为我们生成的解析器对象
parser exprParser(token_stream)# prog就是g4语法规则文件的第一条规则
# 因此调用解析器的prog方法得到语法分析树的根节点
# 在其他程序中也需要使用第一条规则的规则名进行调用
tree parser.prog()# 此处使用Listenser的方式遍历得到的语法分析树
listener Listener()
walker ParseTreeWalker()
walker.walk(listener, tree)3.1 Listener
Listener的基本思想是给树的节点定义回调函数当访问语法分析树时自动调用定义的回调函数实现树的自动访问。
在使用antlr4工具生成对应语言的程序时会默认生成{GrammarName}Listener.py的代码文件这里以python为例。
在{GrammarName}Listener.py的文件中会生成一个继承自antlr4.tree.Tree.ParseTreeListener的{GrammarName}Listener类该类中会每条规则定义了两个方法
enter{RuleName}()方法例如规则名为expr则方法名为enterExpr参数为{GrammarName}Parser.ExprContextexit{RuleName}()方法例如规则名为expr则方法名为exitExpr参数为{GrammarName}Parser.ExprContext
看方法名可以知道enterExpr()就是在访问到expr这个规则的子树时调用的方法函数的参数就是子树的树根exitExpr()就是在访问完expr这个子树时调用的方法函数的参数就是子树的树根。
一般情况下开发者不会去修改antlr4生成的Listener文件而是重新继承{GrammarName}Listener然后在其中重写enter/exit方法。
在enter/exit方法中参数是当前遍历的节点因此可以使用继承自antlr4.ParserRuleContext的方法访问当前节点的属性和数据
getChild(i)获取第i个子节点getChildren()获取所有孩子节点getChildCount()获取孩子节点的个数getText()获取节点的字符串通常只会在叶子节点才会调用中间节点调用得到的就是本条规则匹配的字符串getParent()获取父节点只有叶子节点才能调用depth()获取当前节点在树中的深度
由于参数是当前节点并且没有返回值无法将当前节点的处理后得到的数据往上传递因此如果在遍历语法分析树时需要进行数据的传递需要使用额外的数据结构例如第一篇文章中的计算器程序在得到当前节点计算的值后将数据保存到字典中在处理上层节点时再从字典中读取。
对于Listener需要使用antlr4.tree.Tree.ParseTreeWalker进行遍历首先创建一个ParseTreeWalker的对象然后调用对象的walk()函数遍历函数的参数是ParseTreeListener和ParseTree在每个节点类型的ParserRuleContext的派生类{RuleName}Context中都会有定义两个函数enterRule和exitRule在调用walk()时其实就会用深度优先遍历的方式遍历每个节点然后在开始遍历孩子节点前执行enterRule在遍历完成孩子节点后执行exitRule
class ParseTreeWalker(object):DEFAULT Nonedef walk(self, listener:ParseTreeListener, t:ParseTree):对树执行深度优先遍历在遍历当前节点的孩子节点之前先判断当前节点是否是叶子节点这里分为错误节点和正确的叶子节点分别调用listener的visitErrorNode和visitTerminal因此可以在我们自己的Listener中增加visitErrorNode和visitTerminal用于处理叶子节点在遍历孩子节点之前先执行enterRule在遍历完所有孩子节点后执行exitRuleif isinstance(t, ErrorNode):listener.visitErrorNode(t)returnelif isinstance(t, TerminalNode):listener.visitTerminal(t)returnself.enterRule(listener, t)for child in t.getChildren():self.walk(listener, child)self.exitRule(listener, t)def enterRule(self, listener:ParseTreeListener, r:RuleNode):执行当前节点的enterRulectx r.getRuleContext()listener.enterEveryRule(ctx)ctx.enterRule(listener)def exitRule(self, listener:ParseTreeListener, r:RuleNode):执行当前节点的exitRulectx r.getRuleContext()ctx.exitRule(listener)listener.exitEveryRule(ctx)可以看到使用这种方式的好处是开发者只需要编写遍历节点的回调函数即可自动实现树的遍历但是没办法控制遍历过程以及实现值的传递。
3.2 Visitor
将g4文件使用命令antlr4 -DlanguagePython3 -visitor -no-listener expr.g4就可以得到只有Visitor的代码生成的代码与Listener的区别就是有一个exprVisitor.py的文件。
exprVisitor.py中是默认生成的vistorexprVisitorexprVisitor继承自antlr4.tree.Tree.ParseTreeVisitor。exprVisitor中对于每条规则会生成一个visitor{RuleName}()方法参数还是{RuleName}Context。
与Listener有所不同Visitor模式下{RuleName}Context中没有定义enter/exit方法而是定义了accept(ParseTreeVisitor)方法
def accept(self, visitor:ParseTreeVisitor):if hasattr( visitor, visitProg ):return visitor.visitProg(self)else:return visitor.visitChildren(self)在accept(ParseTreeVisitor)中如果ParseTreeVisitor中有visit{RuleName}方法就会调用visit{RuleName}否则就会访问孩子节点。
class ParseTreeVisitor(object):# 提供给外部调用的函数# 参数就是树的根节点def visit(self, tree):# 调用的就是节点的accept()函数return tree.accept(self)# 访问孩子节点def visitChildren(self, node):result self.defaultResult()n node.getChildCount()for i in range(n):if not self.shouldVisitNextChild(node, result):return resultc node.getChild(i)childResult c.accept(self)result self.aggregateResult(result, childResult)return resultdef visitTerminal(self, node):return self.defaultResult()def visitErrorNode(self, node):return self.defaultResult()def defaultResult(self):return Nonedef aggregateResult(self, aggregate, nextResult):return nextResultdef shouldVisitNextChild(self, node, currentResult):return True开发者需要基于exprVisitor创建自己的Visitor重写里面的visitor{RuleName}()方法在主逻辑中就可以调用Visitor.visit()访问语法分析树
# 使用输入的字符串创建输入流然后将输入流给到词法分析器
# 使用词法分析器就得到TokenStream对象
input_stream InputStream(10112\n)
lexer exprLexer(input_stream)
token_stream CommonTokenStream(lexer)# 使用TokenStream对象创建antlr4为我们生成的解析器对象
parser exprParser(token_stream)# prog就是g4语法规则文件的第一条规则
# 因此调用解析器的prog方法得到语法分析树的根节点
# 在其他程序中也需要使用第一条规则的规则名进行调用
tree parser.prog()# 创建Visitor并调用visit访问tree
visitor Visitor()
print(visitor.visit(tree))下面是一个简易的计算器程序的VisitorvisitExpr就是访问表达式如果这个表达式只有一个孩子节点说明它的孩子节点应该是个叶子节点也就是经过词法分析匹配得到的操作数则直接返回该操作数即可如果这个表达式有3个节点说明当前子树是个需要计算的表达式访问第1个孩子获取操作符左边的值访问第3个孩子获取操作符右边的值然后根据第2个孩子的值进行对应的计算并返回。最后在主逻辑中打印visitor.visit(tree)就可以得到表达式最终的结果。
class Visitor(exprVisitor):def visitProg(self, ctx:exprParser.ProgContext):if ctx.getChildCount() 2:return self.visit(ctx.getChild(0))return self.visitChildren(ctx)def visitExpr(self, ctx:exprParser.ExprContext):if ctx.getChildCount() 1:return ctx.getChild(0).getText()elif ctx.getChildCount() 3:left self.visit(ctx.getChild(0))right self.visit(ctx.getChild(2))if ctx.getChild(1).getText() :return int(left) int(right)elif ctx.getChild(1).getText() -:return int(left) - int(right)elif ctx.getChild(1).getText() *:return int(left) * int(right)elif ctx.getChild(1).getText() /:return int(left) / int(right)return self.visitChildren(ctx)可以看到跟Listener的区别在于使用Visitor的方式可以自己控制是否访问子树并且可以得到子树的值。
4 总结
定义好词法和语法规则就可以对提供的输入串进行词法分析和语法分析得到语法分析树语法分析树的非叶子节点的类型是{RuleName}Context叶子节点的类型为TerminalNodeImpl然后使用解析器的第一条规则名作为函数得到树的根节点antlr4提供了Listener和Visitor两种机制遍历语法分析树Listener中生成的{RuleName}Context中会增加enterRule()和exitRule()方法它们分别调用listener中定义的enter{RuleName}和exit{RuleName}方法ParseTreeWalker.walk(ParseTreeListener, ParseTree)使用深度优先搜索遍历树的根节点在遍历当前节点的孩子节点之前会调用当前节点的enterRule()方法在遍历完当前节点的孩子节点后会调用当前节点的exitRule()方法从而来调用listener中定义的enter{RuleName}和exit{RuleName}方法。这种方式适合不需要传递值的场景例如语法检查Visitor中生成的{RuleName}Context中会增加accept(ParseTreeVisitor)在使用ParseTreeVisitor.visit(ParseTree)遍历语法分析树时就会访问根节点的accept方法从而访问Visitor中的visit{RuleName}方法开发人员在重写visit{RuleName}方法时可以使用visit方法得到子树的值这种方式适合需要在子树和父节点传递值的场景
