考虑无二义性的文法, 这意味着每个句子对应唯一的一颗语法分析树。
分为两大类,绿色与蓝色,自顶向下,自底向上
理解定语
自顶向下的,递归下降的,基于预测分析表的,适用于LL(1)文法的LL(1)语法分析器。
自顶向下
构造语法分析树,从根节点开始, 根节点:文法的起始符号S; 中间节点:表示对某个非终结符应用某个产生式进行推导。
问题:1.选择哪个非终结符,2.以及选择哪个产生式
- LL(1):每次选择最左边的非终结符进行展开,leftmost;LL(1)从左向右读入词法单元,left-to-right。两个L的含义
叶节点词法单元流w(\表示结束,标志位),仅包含终结符号和特殊的文件结束符$(EOF)
递归下降
描述LL(1)这一类语法分析器的实现方式,递归。算法。
为每个非终结符写一个递归函数,内部按需调用其他非终结符对应的递归函数,下降一层 用for循环去遍历x1到xk这k个符号,分三种情况。
void A()
选择一个A产生式,A->X1,X2...Xk;
for(i=1tok){
if(Xi是一个非终结符号)
调用过程Xi();
else if(Xi =当前的输入符号a)
读入下一个输入符号;
else/*发生了一个错误*/
}
Example
