资源描述：
《语法分析——自顶向而下分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章语法分析——自顶向而下分析4.1语法分析的任务检查输入的单词符号序列是否符合该语言文法使用例检查表达式、语句、函数的格式扫描器分析器语义处理单词符号分析树分析器的输出分析树格式化的程序合法的表达式、语句、函数出错处理要求尽快发现错误，准确定位，可能时进行恢复处理，继续语法分析4.2上下文无关文法（２型文法）编程语言的语法大都可用２型文法来描述例4-1表达式的语法E→E+T
2、E-T
3、TT→T*F
4、T/F
5、FF→(E)
6、id
7、constＶN＝｛E，T,F｝ＶT＝｛id,const,+，-，*，/，(，)｝Ｓ＝E2型
8、文法的使用限制没有一种方法能够有效地分析所有上下文无关文法存在无法处理的２型文法每种方法能够处理一部分上下文无关文法每种方法都有适用范围常用文法LL文法和LR文法都是２型文法的子集对于同一语言的语法可用不同的文法来描述对于不同的文法，可用不同的分析方法ＬＬ文法──递归下降分析法ＬＲ文法──ＬＲ分析法LL文法多用于编译的手工实现LR文法多用于编译的自动生成4.2.1自顶向下分析基本方法为输入符号串寻找最左推导试图根据当前输入单词判断使用哪个产生式过程从根开始，按前序顺序，构造分析树例4-2：分析符号串id+id*id符
9、合表达式文法：E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜id按照最左推导过程，构造分析树推导过程ＥＴＥ’ＦＴ’Ｔ＋Ｅ’idεＦＴ’idεＦ＊Ｔ’idε生成语法分析树推导过程的分析输入：符号串(有序的)输出：结构化的符号串(树结构)产生式的选择根据当前符号（单词）分析树的表示：按照使用序列排列的产生式序列4.2.2FIRST和FOLLOW集定义：FIRST(α)={a｜α==*>a…，a∈ＶT}α的所有首符号（选择产生式的依据）且，若α==*>ε，则ε∈FIRST(α)定义：FOLLOW(A)
10、={a｜S==*>…Aa…，a∈ＶT}A的后续符号αa……S…Aa...FIRST(X)的计算法对所有语法符号X，重复进行以下计算1)若X∈ＶT，则FIRST(X)=X。2)若X∈ＶN，有产生式X→a…，则将a加入FIRST(X)；有产生式X→ε，则将ε加入FIRST(X)。3)若有产生式X→Y…，且Y∈ＶN，则FIRST(Y)的非ε元素∈FIRST(X)；若有产生式X→Y1…Yk，并对于某个i，使得Y1...Yi-1==*>ε，则将FIRST(Yi)的所有非ε元素加入到FIRST(X)中；若Y1...Yk==*>ε
11、，则将ε加入到FIRST(X)。例4-3：表达式文法的FIRST集FIRST(F)={‘(‘,id}FIRST(T)=FIRST(F)={‘(‘,id}FIRST(E)=FIRST(T)={‘(‘,id}FIRST(E')={‘+’，ε}FIRST(T')={‘*’,ε}FOLLOW(A)的计算法对于所有非终结符,重复进行以下计算1)将#加入到FOLLOW(S)句子的结束符2)若A→αBβ，则将FIRST(β)的非ε元素加入FOLLOW(B)3)如果A→αB或A→αBβ，且β==*>ε，A≠B，则将FOLLOW(A)
12、的所有元素加入FOLLOW(B)例4-4：表达式文法的FOLLOW集FOLLOW(E)={‘)’,#}FOLLOW(E')=FOLLOW(E)={‘)’,#}FOLLOW(T)={+,‘)’,#}FOLLOW(T')=FOLLOW(T)={+,‘)’,#}FOLLOW(F)={*,+,),#}4.2.3LL(1)文法第一个L表示从左向右扫描输入符号串第二个L表示生成最左推导1表示读入一个符号可确定下一步推导表示了自顶向下方法能够处理的文法文法Ｇ是LL(1)的充要条件:对于G的每个非终结符A的任何两个不同的产生式A→α
13、｜β1)FIRST(α)∩FIRST(β)=φ2)如果β==*>ε，则FISRT(α)∩FOLLOW(A)=φ表达式文法是LL(1)文法E→TE'E'→+TE'｜εT→FT'T'→*FT'｜εF→(E)｜id考察E’:+不在FOLLOW(E’)={),#}T’:*不在FOLLOW(T’)={+,),#}F:(和id不同非LL(1)文法的非确定性例4-5：对文法S→cAdA→ab｜a输入w=cad的分析非确定性的解决方法1)采用回朔算法过于复杂2）改写文法将非LL(1)文法改写为等价的LL(1)文法无法改写时：文法过于
14、复杂，无法用自顶向下方法处理4.3文法的编写为描述语法，编写文法；可能不存在分析方法；大都可以改写为可分析的文法LL文法、LR文法、算符优先文法例：自顶而下分析的使用要求符合LL文法无二义性、左递归、左因子4.3.1消除二义性例4-6：条件语句的二义性stmt→ifexprthenstmt｜ifexprthenstmtelsestmt｜{stm
