ch5-自顶向下语法分析方法

《ch5-自顶向下语法分析方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章自顶向下语法分析在上一章中用正规式描述了单词符号的结构，并研究了如何用有限自动机构造词法分析器的问题。由于正规式与正规文法是等价的，它们的描述能力有限，而高级语言的语法结构适合用上下文无关文法描述，因此，我们将上下文无关文法用作语法分析的基础。本章介绍编译程序构造中的一些典型的语法分析方法。1语法分析就是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序).语法分析常用的方法:自顶向下分析与自底向上分析.而自底向上分析又可分为:算符优先分析与LR分析.自顶向下分析也称面向目标的分析方法,也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子.自顶向下分析方法分为

2、:确定的和不确定的.确定的分析方法需要对文法有一定的限制;而不确定的方法是一种穷举的试探方法.25.1确定的自顶向下分析若有文法G1[s]：S->pA

3、qBA->cAd

4、aB->dB

5、b构造输入串W=pccadd的语法树。该文法的特点：1）每个产生式的右部都由终结符号开始；2）若两个产生式有相同的左部，则它们的右部由不同的终结符开始。确定的自顶向下分析方法是从文法的开始符号出发，如何根据当前的输入符号唯一确定选用哪个产生式替换相应非终结符往下推导，或构造一颗相应的语法树。这种文法完全可以根据当前的输入符号决定选择哪个产生式往下推导,因此分析过程是唯一确定的.3文法G2[S]为：S->ApS-

6、>BqA->aA->cAB->bB->dB给出输入串W=ccap的推导过程。该文法的特点：1）产生式的右部不全是由终结符开始；2）若两个产生式有相同的左部，则它们的右部是由不同的终结符或非终结符开始；3）文法中无空产生式。4文法G3[S]为：S->aAS->dA->bASA->给出W=abd的推导过程。5相关概念：FIRST集【定义】设G=(VN,VT,S,P)是上下文无关文法,又设是文法G的任一字符串，定义的首符集FIRST()={a

7、a…,a∈VT}若ε，ε∈FIRST()FIRST()是从可推导出的所有首终结符或可能的ε。**6相关概念：FOLLOW集【定义】假设

8、S是文法G的开始符号，对于G的任何非终结符A，定义非终结符A的后继符号的集合：FOLLOW(A)={a

9、S...Aa...，a∈VT}。特别是，若S...A，则规定#∈FOLLOW（A）。FOLLOW(A)是G的所有句型中紧接在A之后出现的终结符或#。这里#作为输入串的结束符。因此,当文法中含有形如:A->A->的产生式时,其中AVN,,V*,当和不同时推导出空时,则对非终结符A的替换仍可唯一地确定候选.**7相关概念：SELECT集【定义】假设A是文法G的任一规则，定义规则A的选择集合SELECT为：SELECT(A)=其中A∈VN，∈(VNVT)*，F

10、IRST()若(FIRST()-{})FOLLOW(A)若=>ε*/*8LL(1)文法这里的第一个L表示从左到右扫描字符串，第二个L表示最左推导，1表示每一步只需向前看一个符号。一个上下文无关文法G是LL(1)文法，当且仅当对G中每个非终结符A的任何两个不同的规则A→α

11、，满足:SELECT(A→α)SELECT(A→)=其中α、中至多只有一个能推导出串。95.2LL(1)文法的判别判断LL(1)文法的步骤:1.求出能够推出的非终结符1)初始化2)扫描文法的产生式a)删除所有右部含有终结符的产生式,若以某一非终结符为左部的所有产生式都被删除,则将数组中对应该非

12、终结符的标记修改为“否”;b)若某一非终结符的某一产生式右部为,则将数组中对应该非终结符的标志置为“是”,并从文法中删除该非终结符的所有产生式.10判别步骤(续)3)扫描产生式右部的每一符号a)若所扫描到的非终结符号在数组中的对应标志是“是”,则删去该非终结符,若这使得产生式右部为空,则对产生式左部的非终结符在数组中对应的标志改为“是”,并删去该非终结符为左部的所有产生式;b)若所扫描到的非终结符号在数组中的对应标志是“否‘,则删去该产生式,若这使得产生式左部非终结符的有关产生式都被删去,则将数组中该非终结符对应的标志改成”否“.4)重复3),直到扫描完一遍文法的产生式,数组中非终结符对应

13、的特征再没有改变为止.112.计算FIRST集1)计算每一文法符号X的FIRST集-----FIRST(X)(a)若XVT,则FIRST(X)={X};(b)若XVN且有产生式X->a….,aVT,则aFIRST(X);(c)若XVN且有产生式X->,则FIRST(X);(d)XVN且Y1,…,Yi都VN,而有产生式X->Y1…Yn.当Y1,…,Yi-1=>(其中1in),则FIRS