《编译原理课件 第四章》由会员分享，可在线阅读，更多相关《编译原理课件 第四章（110页珍藏版）》请在金锄头文库上搜索。
1、四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码 生成器优化段源程序表格管理出错处理 目标代码生成器第四章 语法分析自上而下分析本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结 构进行描述。 采用正规式和有限自动机可以描述和识别语 言的单词符号； 用上下文无关文法来描述语法规则。上下文无关文法的定义义： 一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结终结 符集合(非空) VN：非终结终结 符集合(非空)，且VT VN= S：文法的开始符号，S VN P：产产生式集合(有限)，每个产产生式形式为为 P ， P VN， (VT VN
2、)* 开始符S至少必须须在某个产产生式的左部出现现一次。例，定义义只含+，*的算术术表达式的文法G=， 其中，P 由下列产产生式组组成： E i E E+E E E*E E (E)定义义：称 A 直接推出 ，即 A仅仅当A 是一个产产生式，且 ， (VT VN)* 。如果1 2 n，则则我们们称这这个序列是 从1到n的一个推导导。若存在一个从1到n的推导导，则则称1可以推导导出n 。例：对对文法(1) E (E) (E+E) (i+E) (i+i)通常，用 表示：从1出发发，经过经过 一步 或若干步，可以推出n。用 表示：从1出发，经过0步或 若干步，可以推出n。所以 ： 即 或q定义：假定G
3、是一个文法，S 是它的开始符号。 如果 ，则 称是一个句型。仅含终结符 号的句型是一个句子。文法G所产生的句子的全体 是一个语言，将它记为 L(G)。4.1 语法分析器的功能语语法分析的任务务是分析一个文法的句子结结构 。语语法分析器的功能：按照文法的产产生式(语语言 的语语法规则规则 )，识别输识别输 入符号串是否为为一个句 子(合式程序)。源程序单词符号取下一单词.语法分 析树词法分 析器语法分 析器符号表编译程序 后续部分语语法分析的方法： 自下而上分析法(Bottom-up)基本思想：从输输入串开始，逐步进进行“归归 约约”，直到文法的开始符号。即从树树末端开始， 构造语语法树树。所谓
4、归约谓归约 ，是指根据文法的产产生式 规则规则 ，把产产生式的右部替换换成左部符号。 算符优优先分析法：按照算符的优优先关系和 结结合性质进质进 行语语法分析。适合分析表达式。 LR分析法：规规范归约归约G(E)： E i| E+E | E-E | E*E | E/E | (E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE语语法分析的方法： 自下而上分析法(Bottom-up) 自上而下分析法(Top-down)基本思想：它从文法的开始符号出发发，反复使用各种产产生式，寻寻找“匹配“的推导导。递归递归 下降分析法：对对每一语语法变变量(非 终结终结 符)构造一个相应应的子程
5、序，每个子程序 识别识别 一定的语语法单单位，通过过子程序间间的信息反 馈馈和联联合作用实现对输实现对输 入串的识别识别 。预测预测 分析程序F优优点：直观观、简单简单 和宜于手工 实现实现 。4.2 自上而下分析面临的问题自上而下就是从文法的开始符号出发发，向下推 导导，推出句子。带带“回溯”的 不带带回溯的递归递归 子程序(递归递归 下降)分析方法。自上而下分析的主旨：对对任何输输入串，试图试图 用 一切可能的办办法，从文法开始符号(根结结点)出发发， 自上而下地为输为输 入串建立一棵语语法树树。或者说说 ，为输为输 入串寻寻找一个最左推导导。例3.4.1 假定有文法G(S):(1) Sx
6、Ay(2) A*|*分析输输入串x*y(记为记为 )。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*Sx*yIPAxy*当某个非终结终结 符有多个产产生式候选时选时 ，可能带带 来如下问题问题 : 1. 分析过过程中，当一个非终结终结 符用某一个候选选匹配 成功时时，这这种匹配可能是暂时暂时 的。出错错时时，不得不“ 回溯”。 2. 文法左递归问题递归问题 。一个文法是含有左递归递归 的， 如果存在非终结终结 符P 含有左递归的文法将使自上而下的分 析陷入无限循环。4.3 LL(1)分析法构造不带带回溯的自上而下分析算法要消除文法的
7、左递归递归 性克服回溯4.3.1 左递归 的消除直接消除见诸见诸 于产产生式中的左递归递归 ：假定关 于非终结终结 符P的规则为规则为PP | 其中 不以P开头头。我们们可以把P的规则规则 等价地改写为为如下的非直 接左递归递归 形式： P P P P |左递归变 右递归一般而言，假定P关于的全部产产生式是 PP1 | P2 | | Pm | 1 | 2|n 其中，每个 都不等于 ，每个 都不以P开头头那么，消除P的直接左递归递归 性就是把这这些规则规则 改 写成： P1P | 2P | | nP P 1P | 2P | | mP | 左递归变 右递归例 文法G(E): EET | T TT*
8、F | F F(E) | i经经消去直接左递归递归 后变变成：ETEE +TE | TFTT *FT | F(E) | i(4.2) PP1 | P2 | | Pm | 1 | 2|n P1P | 2P | | nP P 1P | 2P | | mP | 例如文法G(S): SQc|c QRb|b RSa|a (4.3) 虽虽没有直接左递归递归 ，但S、Q、R都是左递归递归 的 S Qc Rbc Sabc一个文法消除左递归的条件： F不含以 为右部的产生式 F不含回路。消除左递归递归 的算法: 1. 把文法G的所有非终结终结 符按任一种顺顺序排列成P1，P2 ，Pn；按此顺顺序执执行； 2.
9、FOR i:=1 TO n DOBEGINFOR j:=1 TO i-1 DO把形如PiPj 的规则规则 改写成Pi1 |2 |k ; (其中Pj1|2|k是关于Pj的所有规则规则 )消除关于Pi规则规则 的直接左递归递归 性END 3. 化简简由2所得的文法。去除那些从开始符号出发发永远远 无法到达的非终结终结 符的产产生规则规则 。例 考虑虑文法G(S) SQc|c QRb|b RSa|a令它的非终结终结 符的排序为为R、Q、S。对对于R，不存在直接左递归递归 。把R代入到Q的有关候选选后，把Q的规则变为规则变为 QSab | ab | b例 考虑虑文法G(S) SQc|c QRb|b R
10、Sa|a令它的非终结终结 符的排序为为R、Q、S。Q的规则变为规则变为 QSab | ab | b现现在的Q不含直接左递归递归 ，把它代入到S的有 关候选选后，S变变成 SSabc | abc | bc | c例 考虑虑文法G(S) SQc|c QRb|b RSa|aS变变成 SSabc | abc | bc | c消除S的直接左递归递归 后： SabcS | bcS | cS S abcS | QSab |ab | b RSa|a例 考虑虑文法G(S) SQc|c QRb|b RSa|a消除S的直接左递归递归 后： SabcS | bcS | cS S abcS | QSab |ab | b
11、 RSa|a关于Q和R的规则规则 已是多余的，化简为简为 ： SabcS | bcS | cS S abcS | (4.4)注意，由于对对非终结终结 符排序的不同，最后所 得的文法在形式上可能不一样样。但不难证难证 明， 它们们都是等价的。例如，若对对文法(4.3)的非终结终结 符排序选为选为 S 、Q、R，那么，最后所得的无左递归递归 文法是： SQc | c QRb | b RbcaR | caR |a R (4.5) R bca R | 文法(4.4)和(4.5)的等价性是显显然的。4.3.2 消除回溯、提左因子为为了消除回溯就必须须保证证：对对文法的任何非 终结终结 符，当要它去匹配输
12、输入串时时，能够够根据它 所面临临的输输入符号准确地指派它的一个候选选去 执执行任务务，并且此候选选的工作结结果应应是确信无 疑的。A1 | 2 | | n Sa.IPA令G是一个不含左递归递归 的文法，对对G的所有非 终结终结 符的每个候选选 定义义它的终结终结 首符集 FIRST( )为为：特别是，若 ，则规定 FIRST( )。如果非终结符A的所有候选首符集两两不相交， 即A的任何两个不同候选i和j FIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的 第一个输入符号a，准确地指派某一个候选前去 执行任务。这个候选就是那个终结首符集含a的 。提取公共左因子:假定关于
13、A的规则规则 是A1 | 2 | | n | 1 | 2 | | m(其中，每个不以 开头头)那么，可以把这这些规则规则 改写成 A A | 1 | 2 | | m A 1 | 2 | | n经过经过 反复提取左因子，就能够够把每个非终结终结 符 (包括新引进进者)的所有候选选首符集变变成为为两两不 相交。 ETEE +TE | TFTT *FT | F(E) | i i + i4.3.3 LL(1)分析条件i + i IPEnG(E):ETEE +TE | TFTT *FT | F(E) | ii + i IPETEnG(E):ETEE +TE | TFTT *FT | F(E) | ii + i IPETEFTnG(E):ETEE +TE | TFTT *FT | F(E) | ii + i IPETEFTinG(E):ETEE +TE | TFTT *FT | F(E) | ii + i IPETEFTinG(E):ETEE +TE | TFTT *FT | F(E) | ii + i IPETEFTinG(E):ETEE +TE | TFTT *FT | F(E) | ii + i IPETEFTi+TEnG(E):ETEE +TE | TFTT *FT | F
