编译原理第二次答辩的时候，出了一点点问题。答辩时天神说递归下降是可以hold住所有语法的，不需要保证语法是没有左递归的。到现在一直还是不是很理解，于是就看了看课本。PS: 课本为龙书～

关于大作业

大作业是跟橙汁大腿(大腿无误)以及QKQ一起在写。其实说是三个人一起写，多是橙汁写，我们看着`_(:з」∠)_`

项目开源在Github上->https://github.com/gaocegege/CompilerLab，定位是一个LL语法的编译器前端生成器。据橙汁说，我们的大作业是用递归下降的方法来做的，嗯。

递归下降语法分析

关于这个，书上的定义是这样的：

一个递归下降语法分析程序由一组过程组成，每个非终结符号对应一个过程，程序的执行从开始符号对应的过程开始，如果这个过程的过程体扫描了整个输入串，它就停止并宣布语法分析成功。

下面是一个在自顶向下的语法分析器中一个非终结符号对应的典型过程：

void A(){
	chooses a predict A->X1 X2 X3 ... Xk;
	for (int i = 1; i <= k; i++){
		if (Xi is non-terminal)
			Xi();
		else if (Xi == the input char a)
			input the next char to a
		else
			err();
	}
}

这种根据非终结符号决定应用哪个产生式的方法，就是通过上面这种方式来实现，不过会多回溯的过程。

那我们最大的问题在于递归下降的算法能不能hold住左递归的语法。书上有这样一种说法：

一个左递归的文法会使得它的语法分析起进入一个无限循环。即使带回溯的语法分析器也是如此。也就是说，当我们试图展开一个非终结符号A的时候，我们可能会没有读入任何输入符号就再次试图展开A。

举个例子来看看吧～

A -> Aa | b

这样一个简单的语法，看上去是可以用递归下降来做的，但是其实是不可以的。因为在读入第一个字符b的时候，是不能确定要调用哪个产生式的。我试着写了下，可能代码的样子是这样的：

void A(string &str, int &ptr)
{
	if (str[ptr] == 'b')
	{
		ptr++;
		if (ptr == str.size())
			cout << "successs!\n";
		else
		{
			ptr--;
		}
	}
	
	A(str, ptr);
	if (str[ptr] == 'a')
		ptr++;
}

代码看上去是有一个死循环的，所以跑的时候会爆Segmentation fault。死循环的原因就是A的一个产生式的第一个符号就是它自己，所以程序就在判断A->b的产生式失败后，执行A->Aa产生式然后不停递归，就死循环了。感觉这种一个非终结符号对应一个过程的方法是没办法处理左递归的。不知道天神所说的可以处理是用另外的方法还是怎么样。。。

LL(1)语法分析

LL(1)其实也是递归下降的方法吧，只是不再需要回溯，而且可以用更加高效的预测分析表格法来实现。这种方法既然是一种递归下降的方法，那也是解决不了左递归的问题的。

结

所以LL(1)，和带回溯的递归下降都是不能解决左递归的问题的。如果能有方法解决，请务必联系我～