编译原理-简单的递归下降语法分析器LL(1)

在网上看了很多篇关于递归下降分析器的博文，均没有满意的，一是所写的程序不对、二是解释的不够清楚。所以想自己写一篇，顺便总结一下所学。

递归下降分析法

递归下降分析法的原理是利用函数之间的递归调用来模拟语法树自上而下的构建过程。从根节点出发，自顶向下为输入串中寻找一个最左匹配序列，建立一棵语法树。在不含左递归和每个非终结符的所有候选终结首字符集都两两不相交条件下，我们就可能构造出一个不带回溯的自顶向下的分析程序，这个分析程序是由一组递归过程（或函数）组成的，每个过程（或函数）对应文法的而一个非终结符。

准备知识

对文法中的每一个非终结符计算它们的Fisrt集，Follow集和Select集。感觉书上的定义是真的难理解，下面不贴定义和数学符号，仅贴博主个人的理解。

• 计算First集
  1. 终结符的First集是它本身；
  2. 若非终结符A可以推出以终结符开头的串，那么这个终结符属于
  Fisrt(A)；若A可以推导出空串ε，那么空串ε属于First(A)；
  3. A->B… 是一个产生式，B是一个非终结符，那么First(B)中除去空串ε都包含在First(A)；
  4. 若A是非终结符；B1，B2，…，Bi 也是非终结符，且有产生式 A->B1 B2 … Bn；当B1，B2 … Bn-1都能推导出ε时，则First(B1)、FIRST(B2)、…、First(Bn-1)的所有非空元素和First(Bn) 包含在First(A)中；
  5. 若4中B1，B2 … Bn都能推导出ε时则First(B1)、FIRST(B2)、…、First(Bn)的所有非空元素包含在First(A)中，并且ε属于First(A)。
• 计算Follow集
  Follow集合，顾名思义，就是文法符号后面可能跟随的终结符的集合（不包括空串ε）。Follow集针对的是非终结符。
  1. 首先设 S 为文法中开始符号，把 {#} 加入Follow(S)中；
  2. 若A->αBβ 是一个产生式，则把First(β)的非空元素加入
  Follow(B)中。如果β能够推导出ε则把Follow(A)也加入Follow(B)中，以此类推。
• 计算Select集
  给定上下文无关文法的产生式A->α，A是非终结符， 若α不能推导出ε，则Select(A->α)=First(α)； 如果α能推导出ε，Select(A->α)=(First(α) –{ε})∪Follow(A)。

示例

文法G:
E->TE’
E’->+E|ε
T->FT’
T’->T|ε
F->PF’
F’->*F’|ε
P->(E)|a|b|v
经过计算的Select集为：
Select(E->TE’) = {(，a，b，v}
Select(E’->+E) = {(，+}
Select(E’->ε) = {(，#}
Select(T->FT’) = {(，a，b，v}
Select(T’->T) = {(，a，b，v}
Select(T’->ε) = {+，)，#}
Select(F->PF’) = {(，a，b，v}
Select(F’->*F’) = {*}
Select(F’->ε) = {(，a，b，v，)，+，#}
Select(P->(E)) = {(}
Select(P->a) = {a}
Select(P->b) = {b}
Select(P->v) = {v}

程序实现

1. 每一个非终结符对应于一个函数（子过程）；
2. 非终结符所对应的右侧产生式为函数体；
3. 每遇到一个终结符，则需要判断所输入字符是否与之匹配，若匹配则读取下一个，若不匹配，则进行出错处理。

C语言代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>#define LEN 100char str[LEN];
int i;
bool flag=true;void E();
void E1();
void T();
void T1();
void F();
void F1();
void P();int main(){int m;printf("请输入测试的次数:");scanf("%d",&m);while(m--){printf("请输入字符串(以#结束):");scanf("%s",&str);i=0;E();if(flag==true){printf("%s为合法字符串!\n",str);}else{printf("%s为非法字符串!\n",str);}strcpy(str,"");}
} void E(){if(flag){if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){T();E1();}else{flag=false;}}
}void E1(){if(flag){if(str[i]=='+'){i++;E();}else if(str[i]!='#'&&str[i]!=')'){flag=false;}}
}void T(){if(flag){if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){F();T1();}else{flag=false;}}
}void T1(){if(flag){if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){T();}else if(str[i]!='+'&&str[i]!=')'&& str[i]!='#'){flag = false;}}
}void F(){if(flag){ if(str[i]=='('||str[i]=='a'||str[i]=='b'||str[i]=='v'){P();F1();}else{flag=false;}}   
}void F1(){if(flag){if(str[i]=='*'){i++;F1();}else if(str[i]!='('&&str[i]!='a'&&str[i]!='b'&&str[i]!='v'&&str[i]!='+'&&str[i]!=')'&&str[i]!='#'){flag = false;}}
}void P(){if(flag){if(str[i]=='('){i++;E();if(str[i]==')'){i++;}}else if(str[i]=='a'){i++;}else if(str[i]=='b'){i++;}else if(str[i]=='v'){i++;}else{flag=false;}}
}