第10讲语法分析——自下而上分析.PPTVIP

算符文法概念 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： …QR… 则我们称该文法为算符文法。 约定： a、b代表任意终结符； P、Q、R代表任意非终结符； ‘…’代表由终结符和非终结符组成的任意序列，包括空字。 优先关系的确定 假定G是一个不含?-产生式的算符文法。对于任何一对终结符a、b，我们说： 1. a=b 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式； 2. ab 当且仅当G中含有形如P→…aR…的产生式， 而R b…或R Qb…； 3. ab 当且仅当G中含有形如P→…Rb…的产生式，而 R …a或R …aQ。 . . . a Q b P 语法树表示三种关系 b R P a a. a=b . R b S a b. ab . c. ab . 算符优先文法概念 前提：G是一个不含?-产生式算符文法 定义：如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一： a=b，ab， ab 则称G是一个算符优先文法。 . . . 注：大多数程序设计语言的表达式都是算符优先文法 . 例:考虑下面的文法G(E)： (1) E→E+T | T (2) T→T*F | F (3) F→P ? F | P (4) P→(E) | i 由第(4)条规则，有 ‘(’=‘)’； 由规则E→E＋T和T?T*F， 有 ＋*； 由(2) T→T*F 和(3) F→P ? F ，可得*↑； 由(1)E→E＋T和E ? E+T，可得++； 由(3)F→P?F和F ? P?F，可得↑↑。 由(4)P→(E)和 E?E+T?T+T?T*F+T?F*F+T ?P↑F*F+T?i↑F*F+T 有 (+、(*、(↑和(i。 . . . . . . . . . . . + 优先关系表 + * ↑ i ( ) # + * - i ( ) #                                            根据概念求的表 作业与实验 作业 P133—1，2 实验 实验二 第11讲 语法分析——自下而上分析（1） 李元金 计算机与信息工程学院 E-mail: liyuanjin10@126.com 内容与目标 内容 a.复习 b.自下而上分析基本问题 c.算符优先分析 目标 a.理解自下而上分析基本问题 b.掌握算符优先分析 复习 递归下降分析程序构造 预测分析程序 语法分析的方法： 自上而下分析法(Top-down) 基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找“匹配”的推导。 递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。 预测分析程序 优点：直观、简单和宜于手工实现。 语法分析的方法： 自下而上分析法(Bottom-up) 基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。 算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。 LR分析法：规范归约 G(E)： E ? i| E+E | E-E | E*E | E/E | (E) i*i+i E*i+i E*E+i E+i E+E E i + * E i i E E E E 5.1.1 归约 采用“移进－归约”思想进行自下而上分析。 基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。 自下而上分析过程：边输入单词符号，边归约。 例：设文法G(S)： (1) S ? aAcBe (2) A ? b (3) A ? Ab (4) B ? d 试对abbcde进行“移进－归约”分析。 a bbcde b a bcde A a bcde b A a cde A a cde c A a de d c A a e abbcde e B c A a S B c A a