第三章语法分析语法分析器的作用上下文无关文法（CFG）形式语言分类正规式与上下文无关文法CFG产生语言的基本方法——推导定义：由CFGG所产生的语言L(G)={ω|Sωandω∈T*}称为上下文无关语言，ω称为句子。若Sα,α∈(N∪T)*,则称α为G的一个句型。只含终结符的句型是句子。定义：在推导中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，产生的句型称为左句型。最右推导也称为规范推导。例：已知G(E),E→E+E|E*E|(E)|-E|idid+(id*id)的推导过程：最左推导：EE+Eid+Eid+(E)id+(E*E)id+(id*E)id+(id*id)最右推导：EE+EE+(E)E+(E*E)E+(E*id)E+(id*id)id+(id*id)定义：①设αβ是上下文无关文法G的一个句型,如果有SαA,并且Aβ,则称β是句型αβ关于非终结符A的一个短语,或称β是句型αβ的一个短语。②直接短语（简单短语）：A→β③句柄：一个句型的最左直接短语。④素短语:含有终结符的短语,但不存在也具有相同性质的真子串短语：以非终结符为根的子树中所有从左到右排列的叶子；直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2）；句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。素短语:子树末端结点组成的符号串含终结符,且在该子树中不再有包含含有终结符的更小子树例：G(E)：E→E+T|TT→T*F|FF→(E)|i句型：i*i+i的短语、直接短语、句柄和素短语短语：i1*i2+i3,i1*i2,i1,i2,i3直接短语：i1,i2,i3句柄：i1素短语:i1，i2，i3分析树：①根由开始符号标记；②每个叶子由一个终结符、非终结符或ε标记；③每个内部结点由一个非终结符标记；④若A→X1X2…Xn是一个产生式，则标记为A的内部结点从左到右有子结点X1，X2，…，Xn；⑤若A→ε，则ε必是叶结点，且它是A的唯一子结点。例：语法树：①根与内部结点由表达式中的操作符标记；②叶子由表达式中的操作数标记；③用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中；例：语法树只反映句型的结构，忽略了推导句型的过程。二义性与二义性的消除自上而下语法分析2.存在的问题(1)回溯——公共左因子的存在A→1|2(2)左递归A→Aα或AAα提取左因子，以避免回溯；消除左递归，以避免陷入死循环。消除左递归例：消除直接左递归E→E+T|TT→T*F|FF→(E)|-F|id消除后E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|-F|id(2)间接左递归的消除例：S→Qc│cQ→Rb│bR→Sa│a按S,Q,R排列,或R,Q,S排列按S、Q、R排列,代入后按R、Q、S排列,代入后S→Qc│cR→Sa│aQ→Rb│bQ→Sab│ab│bR→Rbca│bca│ca│aS→Sabc│abc│bc│c消除R中的直接左递归消除S中的直接左递归R→bcaR’│caR’│aR’S→abcS’│bcS’│cS’R’→bcaR’│εS’→abcS’│ε提取左因子(回溯)文法3.2:递归下降程序:递归下降程序:#预测分析器(LL(1)分析法)构造预测分析表例：L→E;L|εE→TE’E’→+TE’|-TE’|εT→FT’T’→*FT’|/FT’|modFT’|εF→(E)|id|num非终结符的FIRST集FIRST(F)={(,id，num}FIRST(T’)={*,/,mod，ε}FIRST(T)=FIRST(F)={(,id，num}FIRST(E’)={+,-,ε}FIRST(E)=FIRST(T)={(,id，num}FIRST(L)={ε,(,id，num}1．FOLLOW集(1)定义：非终结符A的FOLLOW集合FOLLOW(A)＝{a|S…Aa…,a∈T},若S…A,则#∈FOLLOW(A),其中S为开始符号①#∈FOLLOW(S);②A→αBC:将FIRST(C)-{ε}加入FOLLOW(B);③A→αB或A→αBC且ε∈FIRST(C),则将FOLLOW(A)加入FOLLOW(B)。例：L→E;L|εE→TE’E’→+TE’|-TE’|εT→FT’T’→*FT’|/FT’|modFT’|εF→(E)|id|num非终结符的FOLLOW集FOLLOW(L)={#}FOLLOW(E)={;,)}FOLLOW(E’)={;,)}FOLLOW(T)={+,-,;