编译原理实验-自上而下语法分析-2 预测分析法

本文主要是介绍编译原理实验-自上而下语法分析-2 预测分析法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用预测分析法（表驱动）分析文法 G 的正确句子和错误句子

不如直接给一个例子，根据例子了解预测分析法的分析过程

产生式和它的SELECT集

对应的预测分析表

分析过程

代码实现

好久没写Kotlin了，正好复习Kotlin语法

Main.kt

fun main() {(mutableMapOf("E" infer symStr("T", "E'") select symStr("(", "id"),"E'" infer symStr("+", "T", "E'") select symStr("+"),"E'" infer symStr("ε") select symStr("#", ")"),"T" infer symStr("F", "T'") select symStr("(", "id"),"T'" infer symStr("*", "F", "T'") select symStr("*"),"T'" infer symStr("ε") select symStr("+", "#", ")"),"F" infer symStr("(", "E", ")") select symStr("("),"F" infer symStr("id") select symStr("id"),)fuck mkGrammar("E".also { print("开始符$it\n待分析串") })).analyze(symStr("id", "+", "id", "*", "id", "#").also(::println)){ symbolStr, grammar, stack ->val mutableSymbolStr = symbolStr.toMutableList()println("序号" + "\t".repeat(2) + "符号栈" + "\t".repeat(6) + "输入串" + "\t".repeat(6) + "所用产生式")stack.repeatWhile({ it.isNotEmpty() }) { _, index ->val peek = stack.peek()val currentSymbol = mutableSymbolStr[0]var findProduct: Product? = nullprintln("$index" + "\t".repeat(2)  + "$stack" + "\t".repeat(8 - stack.size) + "$mutableSymbolStr" + "\t".repeat(8 - mutableSymbolStr.size) +when {peek != currentSymbol -> {// 如果不可以匹配，则找表达式findProduct = grammar.findProduct(peek, currentSymbol)findProduct}else -> {// 如果可以匹配，则栈和串同时去掉一位mutableSymbolStr.removeAt(0)"“$currentSymbol”匹配"}})stack.pop()findProduct?.apply {right.takeIf { right[0] != "ε" }?.let {it.reversed().forEach { sym ->stack.push(sym)}}}}}
}

SimonGrammar.kt

import java.util.*typealias Symbol = String // 符号
typealias SymbolStr = List<String> // 符号串fun symStr(vararg elements: Symbol) = elements.asList() // 快速将多个符号组成符号串data class Product(val left: Symbol, val right: SymbolStr) {override fun toString(): String {return "$left->$right"}
} // 产生式infix fun Symbol.infer(right: SymbolStr) = Product(this, right) // 生成一个产生式data class SimonGrammar(val startSymbol: Symbol) {val selectMap: MutableMap<Product, SymbolStr> = mutableMapOf()
}fun mkGrammar(startSymbol: String) = SimonGrammar(startSymbol)infix fun <R> Product.select(that: R): Pair<Product, R> {return Pair(this, that)
}infix fun MutableMap<Product, SymbolStr>.fuck(target: SimonGrammar): SimonGrammar {target.selectMap.putAll(this)return target
}fun SimonGrammar.analyze(symbolStr: SymbolStr, block: (SymbolStr, SimonGrammar, Stack<Symbol>) -> Unit) {val stack = Stack<Symbol>()stack.push("#") // 结束符入栈stack.push(this.startSymbol)  // 开始符入栈block.invoke(symbolStr, this, stack)
}fun <T> Stack<T>.repeatWhile(condition: (Stack<T>) -> Boolean, action: (Stack<T>, index: Int) -> Unit) {var index = 0while (condition.invoke(this)) {action.invoke(this, ++index)}
}fun SimonGrammar.findProduct(left: Symbol, target: Symbol): Product? {// 如果values中包含了target，那就判断该values对应的产生式的左部是不是你要的return this.selectMap.filter {it.value.contains(target) && it.key.left == left}.map {it.key}.firstOrNull()
}