left-recursion-killer

大三 - 编译原理 - 左递归消除程序

算法

修正课本P29页的算法如下：

把文法G中的所有非终结符号排序为A1, A2, ..., An
for (i = 1; i <= n; ++i){
	消除Ai产生式中的直接左递归
	for (j = 1; j <= i - 1; ++j){
		if (Aj -> δ1 | δ2 | ... | δn是当前关于Aj的所有产生式){
			if (存在形如Ai -> Ajγ的生成式){
				把每个形如Ai -> Ajγ的产生式改写为Ai -> δ1γ | δ2γ | ... | δnγ
			}
			消除Ai产生式中的直接左递归
		}
	}
}
// 化简文法，去除无用的非终结符和产生式

如何使用

输入要求：

• 输入的文法无环路
• 输入的文法无ε-产生式

输入方式：

• 直接拖拽文件或多个文件到可执行文件即可执行
• 也可以直接双击启动可执行文件再手动输入生成式，输入空行表示结束

输入格式：

• 解析时会忽略所有空格和制表符，所以如果为了美观可以添加任意数量的空格和制表符
• 每行只能有一个非终结符的生成式，但是生成式可以有多个候选式。候选式使用|分隔
• 允许一个非终结符有多行生成式
• 单个非终结符以大写字母开头，后面可以接任意个英文单引号'
• 生成式的左侧只能有一个非终结符，此非终结符后面必须有箭头->。
• 只识别每行的第一个箭头->，同一行后面还有箭头会视为终结符
• 字符~表示ε，即空串
• 上面没有提到的可打印符号均可作为终结符。终结符后面可以接任意个英文单引号'
• 根据上面的规则，如果不想让~表示空串，可以加一个英文单引号用~'表示

输出局限：

• 没有去除无用的非终结符和产生式
• 不能判断错误输入或不需要消除左递归的输入