您可以自由地共享和演绎本文稿, 只需遵守开源协议[CC By 4.0]
如果这篇文章帮助到你, 可以请我喝一杯咖啡~
语法分析的难点
我们在词法分析中将源输入程序的ASCII字符串转化成了若干初级抽象的词法单元，接下来我们就要在句子的层面上来考察这些词法单元的结构了。这个过程称为语法分析：我们将一个词法单元序列转化成一个描述语法结构的语法分析树。
有一个很直观的想法就是，是否可以继续使用正则表达式来描述句法，也就是语法、是否可以继续使用DFA来进行词法分析呢？答案是否定的。比如下面的例子：
c = (((((((((x + 2)) + 1;
我们之前提到过，自动机是不计数的。因此如果想要描述括号表达式，我们只能通过(*.*)*的方式表述，那么我们会发现，上边的表达式在DFA看来是一个合适的表达，然而很明显，它不是一个语法上良构的句子。因此我们需要一个比正则表达式更强大的描述语法的表达，也需要一个比DFA更强大的算法来支持语法分析。
很幸运，我们有。这个工具被称为上下文无关文法。
上下文无关文法
一个上下文无关文法由：
- 一个
终结符号集合：终结符号就是由词法分析得到的具体词法单元，它不能够继续推到出其他结构，因此它叫终结符号 - 一个
非终结符号集合：一个非终结符号可以视为一个中间变量，它可以继续推导为若干终结符号和非终结符号的任意组合 - 一个
产生式集合：产生式描述了一个非终结符号是如何推导为若干终结符号和非终结符号的串的 - 一个
文法开始符号：它是最高级的、最根本的非终结符号
比如，一个十位数内的+/-表达式的语法可以写为：
\[list→ list + digit\] \[list→ list - digit\] \[list→ digit\] \[digit→ 0|1|2|3|4|5|6|7|8|9\]这里，非终结符号集合是list, digit，终结符号集合是0 - 9，产生式集合是上述的四个式子，分别解释了各个非终结符号。我们注意到，一个非终结符号可以有数个产生式，每一个被称为这个非终结符号的候选，比如list有3个候选，digit有10个候选。文法开始符号是list。因为没有任何更高级的符号可以推出list。
产生式与推导
我们在这一部分仔细解释一下产生式。
产生式均是形如：
\[A→ B\]的式子，A被称为左部或者产生式头，B被称为产生式体。而所谓推导，就是从开始符号开始，不断将现有表达式串内的非终结符号以相应产生式的产生式体替换。(具体如何选择产生式、如何匹配等我们目前暂时不考虑)
比如。还是考虑上边的list文法，我们来进行一次语法推导。
- 最初，我们只有一个开始符号
list - 我们以产生式
list→ list - digit推导：得到串list - digit - 将list以
list→ digit推导，得到digit - digit - 将第一个
digit换为3，第二个digit换为5，得到了具体的3 - 5，被称为一个文法的句子或者实例
语法分析树
我们可以将上述的过程以树的形式画出来：
- 每一个非终结符号均有与它产生式长度相当个数的子树
- 每一个终结符号都是叶子
这样，我们就将产生式的选择和句子的逻辑层次用树的方式表达出来。我们对这个树执行中序遍历，就可以知道它的返回值。
递归向下语法分析 - 导引
那么，如何建立这种语法分析树呢？
一种做法是递归向下语法分析，也就是说，在实际的编程语言中，将每一个非终结符号编写为一个函数调用，它的函数体应该反映出它的全部产生式结构。比如，还是以上述的文法为例，我们可以写出这样的程序：
void list() {
if (/*选择产生式1的条件*/) {
list();
match('+');
digit();
} else if (/*选择产生式2的条件*/) {
list();
match('-');
digit();
} else if (/*选择产生式3的条件*/) {
digit();
} else {
throw("sytax error");
}
}
void digit() {
match("digit");
}
在这个程序中，match()是容易的，我们只需要向词法分析器请求下一个词法单元并判断其是否匹配即可。
但，我们在这有一个问题，即：如何填写if中的条件？这个需要我们解决。
第二个问题更严重：如果这个if中的条件只与目前读到的词法单元有关(很明显这是一个事实)，那么很明显这个程序有单程递归的危险：在某种情况下，我们选择产生式1，而此时由于没有任何对match()的调用(只有match()才会让词法分析器向前进行)，我们在下一轮调用时仍然会选择产生式1，那么单程递归就产生了。
很明显，这第二个问题是因为文法产生式设计不当导致的。这个问题引发了我们的思考：“我们应当为递归下降分析设计怎样的上下文无关文法”？