语法分析程序的功能是以词法分析器生成的单词符号序列作为输入，根据语言的语法规则（文法），识别出各种语法成分，并在分析过程中进行语法检查，检查所给单词符号序列是否是该语言的文法的一个句子。若是，则以该句子的某种形式的语法树作为输出；若不是，则表明有错误，并指出错误的性质和位置。递归下降法LL(1)分析法■自顶向下的分析例：已知符号串S=cad文法G[Z]:Z→cAdA→ab|a求解SL(G[Z])3.选用A的右部符号串匹配输入串A有两个右部,选第一个■文法左递归的消除A→Aα1|Aα2|…|Aαn|β1|β2|…|βm（2）采用扩充BNF表示法改写含直接左递归的规则■回溯的消除First集合和Follow集合1.若X,则FIRST(X)={X}2.若XN,且有产生式Xa…，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY…是一个产生式且YN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2…YK是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)=>*),则把FIRST(Yj)中的所有非元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj,j=1,2,…,K)均含有,则把加到FRIST(X)中.■求First集合综合举例求文法G的FIRST集合G:(1)E→EaopT(2)E→T(3)aop→+(4)aop→-(5)T→TmopF(6)T→F(7)mop→*(8)mop→/(9)F→(E)(10)F→i1)求文法G的FIRST集合(Simpleintegerexpressiongrammar)expr→expraddopterm∣termaddop→+|-term→termmulopfactor∣factormulop→*factor→(expr)∣number2)求文法G的FIRST集合(Leftfactoredgrammarofif-statement)statement→if-stmt|otherif-stmt→if(exp)statementelse-partelse-part→elsestatement|εexp→0|13)求文法G的FIRST集合(Grammarforstatementsequences)stmt-sequence→stmtstmt-seq’stmt-seq’→;stmt-sequence|εstmt→s■求First集合举例2定义：FOLLOW(A)={a|S=>*…Aa…，a∈T}A∈N,S开始符号特殊地：若S=>*...A，则$∈FOLLOW(A)●举例1●举例2●举例3●课堂练习■First集合和Follow集合的比较■Select集合一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则Aαβ满足：Select(Aα)∩Select(Aβ)=■LL(1)文法判断举例●左递归若文法中含有左递归，即非终结符S+Sa对这个文法的句子不能用LL(1)文法进行分析将文法G：A→αβ|αγ提取左因子。1)将文法G提取左因子。if-stmt→if(exp)statement∣if(exp)statementelsestatement■§4.2自上而下分析法的复习与整合■§4.2自上而下分析法的复习与整合■求First集合综合举例■求Follow集合综合举例■§4.2自上而下分析法的复习与整合■LL(1)文法举例■§4.2自上而下分析法的复习与整合■递归下降分析法■预测分析法与预测分析表的构造■预测分析表的构造算法●练习1Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number)Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number)Follow(factor)={$,+,-,*,)}●练习2(1)文法1statement→if-stmt2statement→other3if-stmt→if(exp)statementelse-part4else-part→elsestatement5else-part→ε6exp→07exp→13)求文法G的LL(1)分析表stmt-sequence→stmtstmt-seq’stmt-seq’→;stmt-sequence|εstmt→s(2)First集和Follo