第四章语法分析句法分析方法分类下推自动机（PDA）与2型文法下推自动机下推自动机下推自动机确定的下推自动机下推自动机的格局下推自动机接受的语言下推自动机设计思路：要检查左右括号配对，必须记住尚未配对的左括号个数，因此建立一个下推栈，每读入一个左括号就下推一个栈符号A入栈，而每遇到一个右括号则从栈中弹出一个A，若输入串结束且栈为空（仅剩栈底符号Z0），则输入串正确，否则输入串不是该下推自动机所接收的句子（或称句法错误）。解：令PDAM=(VT,,Q,δ,q,Z0,Qf)VT={(,)},={A,Z0},Q={q}=Qfδ：δ(q,(,A)=(q,AA)δ(q,(,Z0)=(q,AZ0)δ(q,),A)=(q,ε)δ(q,,Z0)=接收对w=(()())，格局的变化为：(q,(()()),Z0)├—(q,()()),AZ0)├—(q,)()),AAZ0)├—(q,()),AZ0)├—(q,)),AAZ0)├—(q,),AZ0)├—(q,,Z0)接收所以输入串是PDAM的句子。问题：1.若括号不配对能否判定是多一个左括号，还是少一个右括号？为什么？2.若括号不配对，何时能发现错？这说明了什么？下推自动机（PDA）与2型文法几点说明几点说明预测分析方法LL(1)文法及其句法分析方法例1（续）对输入串W的分析过程为：表示法FIRST和FOLLOW的性质例2：设文法G[<S>]的产生式是：<S>→<A>a<B>FIRST(<A>a<B>)={a,f,g}<S>→<B>bFIRST(<B>b)={d,e,b}<A>→a<D>FIRST(a<D>)={a}<A>→<D>FIRST(<D>)={f,g}<B>→dFIRST(d)={d}<B>→eFIRST(e)={e}<B>→εFIRST(ε)={ε}<D>→f<D>FIRST(f<D>)={f}<D>→gFIRST(g)={g}FOLLOW(<B>)={b,}LL(1)文法LL(1)文法例3：考察文法G[<E>]引入0号产生式：(0)<E”>→<E>(1)<E>→<T><E’>(2)<E’>→+<T><E’>(3)<E’>→(4)<T>→<P><T’>(5)<T’>→*<P><T’>(6)<T’>→(7)<P>→(<E>)(8)<P>→i产生式#3、#6是可空产生式，非终结符<E’>、<T’>是可空非终结符，各产生式的选择集合为：SELECT(#0)=SELECT(#1)=FIRST(<T><E’>)={(，i}SELECT(#2)={+}SELECT(#3)=FOLLOW(<E’>)=FOLLOW(<E>)={)，}SELECT(#4)=FIRST(<P><T’>)={(，i}SELECT(#5)={*}SELECT(#6)=FOLLOW(<T’>)={+}∪FOLLOW(<E’>)={+，)，}SELECT(#7)={(}SELECT(#8)={i}文法G[<E>]是LL(1)文法。LL（1）句法分析LL(1)文法的句法分析表的构造预测分析表例4：文法G[<E>]的预测分析表：亦可如下表示：分析算法控制矩阵方法控制矩阵方法例对输入串w=i+i*i，M的工作过程：§4.3文法的等价变换提取公共左公因子最左角替换消除左递归左递归可以分为直接/间接左递归具有左递归产生式的文法不是LL(K)例3：考察文法G[<S>]：<S><S>a<S>b即<A>=<S>=<S>a=b考虑最左推导<S>i<S>ai<S>aai与最左推导<S>i<S>aibaii0表示i次直接推导当ik时FIRSTk(<S>aai)∩FIRSTk(bai)=bak-1∴G[<S>]不是LL(k)文法。消除直接左递归ii)采用扩展BNF表示由（*）式可知上述文法与如下表示等价<A>{}n0其中0~n表示可重复0次或n次（n1）例4：算术表达式文法G[<E>]<E><E>+<T>|<T><E><T><E’><T><T>*<F>|<F><E’>+<T><E’>|<F>(<E>)|i<T><F><T’><T’>*<F><T’>|<F>(<E>)|i也可表示为：<E><T>{+<T>}<T><F>{*<F>}<F>(<E>)|i消除间接左递归递归下降分析方法基本思想实现方法为每个非终结符<A>VN编制过程A：主过程为：