Kotlin写一个解释器（2）---语法分析

2023-10-12 09:19:10

语法

之前的文章中我们写了一个简单的词法分析器，具体见文章（Kotlin写一个解释器（1）—词法分析），有了词，那么如何将这些词组合成正确的句子呢？这里就是语法分析要做的了，首先说什么是语法，简单来说语法就是用词构成句子的规则。比如说汉语中我们常见的句子构造一般由主语+谓语+宾语构成，比如小明玩游戏，其中小明按照词类来看属于名词，这里作为主语，玩按照词类来看是动词，属于谓语，游戏按词类来看是名词，属于宾语。语法分析的目的就是根据之前词法分析获得的词法单元的序列判断是否符合相应的语法要求。

上下文无关语法

如何表示一个语法，在编译器过程中，我们经常用到的是一种名为上下文无关语法的符号表示法，上下文无关语法描述了一系列规则，用来表示语句是如何形成的。拿上面的主谓宾的语法规则举例。

句子->主语谓语宾语

|主语谓语

主语->名词

谓语->动词

宾语->名词|形容词

在上面的描述中，描述了一系列语法规则，其中每一条代表着一个产生式，箭头左边是产生式头，箭头右边是产生式体，所有斜体代表非终结符，用来表示一个语法变量，非斜体代表的是终结符，每个单词都是一个终结符，|代表着或，语法分析的目的就是根据输入的单词流和相应的语法规则来判断输入的单词流在程序设计语言中是否是一个合法的语句。

还有一个知识点就在于什么是上下文无关，在应用一个产生式进行推导时，前后已经推导出的部分结果就是上下文。上下文无关的意思的，只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导。比如说水玩人，如果有上下文约束的话，其实这个句子是个病句，应该是人玩水，但是按照我们的语法规则，其中水可以作为主语，玩可以作为谓语，人可以作为宾语，它就是符合我们语法规则的句子。

四则运算语法表达

下面说一下关于四则运算的语法表达，这里先说一下加法和减法的语法

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

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 {
        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 = curToken
            if (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 = curToken
            if (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 = curToken
        return when {
            TokenType.NUMBER == curToken.tokenType -> {
                eat(TokenType.NUMBER)
                Num(tmpToken)
            }
            TokenType.LBRACKETS==curToken.tokenType -> {
                eat(TokenType.LBRACKETS)
                val node = exp()
                eat(TokenType.RBRACKETS)
                node
            }
            else -> {
                throw RuntimeException("TokenType是${curToken.value}语法格式错误")
            }
        }
    }

}

下面我们将语法转换为源代码的准则。通过遵循它们，您可以将语法从字面上转换为有效的解析器：

1.语法中定义的每个规则R都将成为具有相同名称的方法，并且对该规则的引用将成为方法调用：R()，如exp(),term(),factor()
2.替代（a1 | a2 | aN）成为if-elif-else语句,如exp中的

if (TokenType.MIN == curToken.tokenType) { eat(TokenType.MIN) } else { eat(TokenType.PLUS) }

3.替代（…）*成为while语句，可以循环零次或多次，如exp中的

while (TokenType.MIN == curToken.tokenType || TokenType.PLUS == curToken.tokenType)

4.当碰到终结符时（这里是NUMBER），调用eat（）方法。 eat方法的工作方式是，如果参数的TokenType和当前token的tokenType相同，从词法分析器获取一个新的标记并将该标记分配给curToken内部变量。

测试代码

fun main() {
    while (true) {
        val scanner = Scanner(System.`in`)
        val text = scanner.nextLine()
        val lexer = Lexer(text)
//        var nextToken = lexer.getNextToken()
//        while (TokenType.EOF != nextToken.tokenType) {
//            println(nextToken.toString())
//            nextToken = lexer.getNextToken()
//        }
        val parser = Parser(lexer)
        val ast = parser.parse()
        println(ast)
    }
}

代码已经上传到github，后续会不断更新 CompilerDemo

Kotlin写一个解释器（1）—词法分析

明天就是五一了，祝各位大佬五一快乐

关注我的公众号:滑板上的老砒霜

码农公寓