考虑无二义性的文法, 这意味着每个句子对应唯一的一颗语法分析树。 分为两大类,绿色与蓝色,自顶向下,自底向上

理解定语

自顶向下的,递归下降的,基于预测分析表的,适用于LL(1)文法的LL(1)语法分析器。

自顶向下

构造语法分析树,从根节点开始, 根节点:文法的起始符号S; 中间节点:表示对某个非终结符应用某个产生式进行推导。

问题:1.选择哪个非终结符,2.以及选择哪个产生式

  1. 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