编译原理之词法分析.ppt

第四章 教学时数 教学目的与要求 教学重点 教学难点 本章主要阅读文献资料 教学学时 教学目的与要求 教学难点 本章主要阅读文献资料 Kenneth C.Louden 著：《Compiler Construction Principle and Pratice 》，机械工业出版社。 蒋立源著：《 编译原理》（第2版），西北工 业大学出版社。 陈火旺著：《程序设计语言编译程序》（第2 版），国 防工业出版社。 第四章　语法分析 教学目的与要求： 要求学生了解语法分析程序的构造，掌握自顶向下和自底向上的语法分析方法，能应用LL(1)文法和LR文法进行分析，能解决非LL(1)文法中的左递归和回溯问题，能利用LR（1）解决SLR（1）中出现移进归约冲突和归约归约冲突，能达到在LL(1)分析中用First集和Follow集构造分析表，能进行LR（0），SLR（1），LR（1），LALR(1)的分析。 教学重点 教学难点 通过算法分析和具体例题的讲解来理解像FITST集和FOLLOW集，LEADVT，LASTVT，LL（1）分析法，优先分析法及LR分析法。 4.1自顶向下分析 4.1.1 自顶向下分析思想 4.1.2 LL（1）文法 4.1.3 递归下降分析法 4.1.1 自顶向下分析思想 给定符号串S，若预测是某一语法成分， 那么可根据该语法成分的文法,设法为S构造一棵语法树. 若成功,则S最终被识别为某一语法成分,即 S?L(G[Z])其中G[Z]为某语言成分的文法. 若不成功,则 S?L(G[Z]) 1.自顶向下分析方法特点 2. 自顶向下分析存在的问题及解决方法 1） 左递归文法： 4.1.2 LL(1)分析法 1、LL分析程序构造及分析过程 4.1.2 LL（1）文法 LL(1)文法及LL(1)语言的性质 任何LL(1)文法都是无二义性的； 若一文法中的非终结符含有左递归，则它必然是非LL(1)文法； 非LL(1)语言是存在的； 存在一种算法，它能判定任一文法是否为LL(1)文法； 不存在这样的算法，它能判定上下文无关语言能否由LL(1)文法产生。 一个含有冲突的例子 设有文法G[S]： S?if E then S S?|a S??else S|? E?b FIRST(S)={if,a}，FIRST(S?)={else，?}，FIRST(E)={b} FOLLOW(S?)={else，#}，FOLLOW(E)={then} SELECT(S?if E then S S?)={if} SELECT(S?a)={a} SELECT(S??else S)={else} SELECT(S???)={else，#} SELECT(E?b)={b} 4.1.3 递归子程序法（递归下降分析法） 扩展的巴科斯范式(EBNF) EBNF是在BNF基础上扩展如下三组符号： “{ }”：表示花括号内的语法成分可以重复； “[ ]”：表示方括号内的成分是可选项； “( )”：表示括号内的成分优先。 用EBNF改写文法 对于非终结符A的一组形如A?x|y|?|z|Aa的规则，可表示成A?(x|y|?|z){a}。例如，对于规则E?E+T|T，可以写成E?T{+T}。 例 设有文法G[E]： E?E+T|E-T|T T?T*F|T/F|F F?P?F|P P?(E)|i 用EBNF表示消除左递归得到文法G?[E]： E?T{(+|-)T} T?F{(*|/)F}　　 F?P{?P} P?(E)|i 4.2 自底向上分析 4.2.1 移进-归约分析 (自底向上分析的一般过程) 4.2.2 简单优先分析法 4.2.3 算符优先分析法 4.2.4 LR分析法 4.2.1 移进—归约分析（Shift-reduce parsing) 要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是归约。 自下而上分析一般过程 　　例：文法G：S → cAd