编译原理第五章 语法分析.ppt

《编译原理第五章 语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理第五章语法分析—自下而上分析1自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结点。是推导的逆过程。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约2G(E)：Ei

2、E+E

3、E-E

4、E*E

5、E/E

6、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE35.1.1归约采用“移进－归约

7、”思想进行自下而上分析。基本思想：从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功，称为“移进-归约”方法。5.1自下而上分析基本问题4例：设文法G(S)：(1)SaAcBe(2)Ab(3)AAb(4)Bd试对abbcde进行“移进－归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae56b

8、dbaceSABA自下而上分析过程：边输入单词符号，边归约。核心问题：识别可归约串75.1.2规范归约定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有且则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。8考虑文法G(E)：ET

9、E+TTF

10、T*FF(E)

11、i和句型i1*i2+i3：EE+TE+FE+i3T+i3T*F+i3T*i2+i3F*i2+i3i1*i2+i3短语：i1，i2，i3，

12、i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i19短语：在一个句型对应的语法树中,以某非终结符为根的一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。句柄：一个句型的分析树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。EFFTTTi1+*EFi3i2短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i110EE+TT+TF+Ta1+Ta1+T*Fa1+F*Fa1+a2*FE+TT

13、,T+TF,F+Ta1,a1+Ta1,T*F,a1+T*Fa1,F,F*F,a1+F*Fa1,a2,a1+a2*F,a2*Fa1,a2,a3,a2*a3a1+a2*a3EE+TTFa1T*FFa2a3a1+a2*a3短语11可用句柄来对句子进行归约句型归约规则abbcde(2)AbaAbcde(3)AAbaAcde(4)BdaAcBe(1)SaAcBeS12定义：假定是文法G的一个句子，我们称序列n，n-1，，0是的一个规范归约，如果此序列满足：1n=20为文法的开始符号，即0=S3对任何i，0in，i-

14、1是从i经把句柄替换成为相应产生式左部符号而得到的。13把上例倒过来写，则得到：SaAcBeaAcdeaAbcdeabbcde显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。14bdbaceSABAdbaceSABAdaceSABaceSABS利用修剪语法树的方法阐述自下而上分析法15移进-归约分析器使用了一个分析栈和一个输入缓冲区。1、句型表示a1a2a3#………X1X2X3#“移进-归约”分析程序输出栈(存放句型前缀)输入串即：分析栈内容+输入缓冲区内容＝#当前句型

15、#一般形式分析栈的内容剩余输入串初态：#输入串#终态：#S#2、分析器结构5.1.3符号栈的使用和分析树的表示栈是语法分析的一种基本数据结构。’#’作为栈底符号16３、“移进-归约”分析法的栈实现“移进–归约”分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为:栈        输入          ＃w＃工作过程：自左至右把串w的符号一一移进栈里，一旦栈顶形成可归约的串（如句柄）时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局：  栈   

16、     输入            ＃S＃17步骤符号栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#进2#F*i2+i3#归，用F→i3#T*i2+i3#归，用T→F4#T*