Kotlin 写一个解释器（2）--- 语法分析，安卓项目开发范例大全

factor->NUMBER

其中 exp 和 factor 为非终结符，NUMBER、+、-为终结符，*代表着前面有 0 个或者多个((+|-)factor)。

对于 2+3 的推导过程

exp

|

factor((+|-)factor)*

|

factor+factor

|

NUMBER+NUMBER

|

2+3

上面展示了一个完整的 exp 的语法的推导过程，只要最终推导后的结果和词法分析器的词法流的数据一致，那么语法就是正确的。

结合性

考虑 1+2+3 这个表达式，在计算的时候实际上和（1+2）+3 是相同的，1-2-3 和（1-2）-3 是相同的，连乘和连除类似，对于 2，当它的左右两侧有相同的运算符时（如+），我们需要确定哪个运算符适用于 2，我们规定+为左结合的运算符，2 和左面的+结合在一起，相当于（1+2）+3，我们称这种符号为左结合的，除了左结合自然还有右结合的。

优先级

优先级这个上过小学的都应该知道，先算乘除，再算加减，2+3*7,等价于 2+(3**7)而不是（2+3)*7,从优先级的角度看，乘除的优先级是高于加减的优先级的。

语法表达

对于优先级语法的设计，有一个规则就是为每个优先级定义一个非终结符。非终端产品的主体应包含该级别的算术运算符和下一个更高优先级的非终结符。为基本的表达单位（在我们的情况下为整数）创建一个附加的非终止因子。一般规则是，如果您具有 N 个优先级，则总共将需要 N + 1 个非终结符：每个优先级有一个非终结符，再加上一个基本表达单元的非终结符。所以我们最终的四则运算语法产生式如下。

exp->term((+|-)term)*

term->factor((|/)factor)

factor->NUMBER

抽象语法树

这期我们的语法分析器会产生一个抽象语法分析树，抽象语法树是一种树的数据结构，也是编译器的一种中间表达形式，下一篇的解释器就是用来分析抽象语法树，生成相应的结果。对于算数表达式 1+2*(3+4)，对应的抽象语法树就是

因为后续我们编写解释器进行计算的时候，会对抽象语法树采用后续遍历的方式得到所有元素，所以只要保证优先级高的算法的深度比其他的深，就能保证它先计算。

代码

语法树节点表示

open class AST {

}

class BinOp(val left: AST, val op: Token, val right: AST) : AST() {

override fun toString(): String

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

{val sb = StringBuilder()sb.append(op.value).append("\n").append(left.toString()).append(" ").append(right.toString())return sb.toString()}}

class Num(val token: Token) : AST() {

override fun toString(): String = token.value}

这里先定义一个基类节点 AST，每个运算符对应一个 BinOp 节点，有两个成员变量，每个数字对应 Num 节点

语法解析器

class Parser(val lexer: Lexer) {

private var curToken: Token = lexer.getNextToken()

fun parse(): AST = exp()

private fun eat(tokenType: TokenType) {if (tokenType == curToken.tokenType) {curToken = lexer.getNextToken()} else {throw RuntimeException("TokenType 是 ${tokenType.value}语法格式错误")}}

private fun exp(): AST {var node = term()while (TokenType.MIN == curToken.tokenType || TokenType.PLUS == curToken.tokenType) {val tmpToken = curTokenif (TokenType.MIN == curToken.tokenType) {eat(TokenType.MIN)} else {eat(TokenType.PLUS)}node = BinOp(node, tmpToken, term())}return node}

fun term(): AST {var node = factor()while (TokenType.MUL == curToken.tokenType || TokenType.DIV == curToken.tokenType) {val tmpToken = curTokenif (TokenType.MUL == curToken.tokenType) {eat(TokenType.MUL)} else if (TokenType.DIV == curToken.tokenType) {eat(TokenType.DIV)}node = BinOp(node, tmpToken, factor())}return node}

fun factor(): AST {val tmpToken = curTokenreturn when {TokenType.NUMBER == curToken.tokenType -> {