《编译原理课件.ppt

CompilerPrinciples 第三讲 语法分析 语法分析概述 自上而下语法分析 自下而上语法分析 §1.语法分析概述 一、语法分析器的功能 1.语法分析器在编译程序中的地位： 2.功能：在单词符号的基础上，分析给定语言的句子（程序）的语法结构，看其是否符合语法规则。 二、分析方法 1.针对程序的单词符号串构造语法树——依据程序语言的语法规则，即文法描述。 ☉若能构造出一棵语法树则正确，否则程 序有错 2.根据语法树的建立方法，分为两种： ●自上而下分析法：从文法开始符号出 发，自上而下地构造语法树； ●自下而上分析法：从单词符号串形式的 源程序开始，自下而上地构造语法树； §2.自上而下的语法分析 一、方法、问题及其解决 1.方法概述：对输入的任意单词符号串，试图用一切可能的办法，从文法开始符号（树根）出发，自上而下、自左而右地建立起一棵语法分析树，使得该树的叶结点自左而右地排列起来，刚好就是所给的输入串。 ☉显然，这种建立语法树的过程应该与最左推导相对应，即自左向右进行匹配。 例 G[S]: S→aAb 输入串 a*b A→**∣* 2.问题： 自左向右建立子树—左递归文法会造成死循环。 这是一种自上而下的试探法，有时免不了要走回头路—回溯。 新建、撤销 很难报告错误的准确位置 这实际上是一种穷举法，效率低，只有理论意义。 3.解决办法： (1)左递归问题：改写产生式，变左递归为右递归。 ①直接左递归：直接见诸于产生式的左递归，如 P→Pα,P∈VN, α∈(VT∪VN)* 这种直接左递归可以通过直接扫描产生式发现，也容易解决——改写产生式即可。 如： P→Pα1∣Pα2∣…∣Pαm∣β1∣β2∣…∣βn 其中P∈VN,αi,βj ∈(VT∪VN)* 且α≠?, β不以P开头 改写成 P→β1 P ∣β2 P ∣…∣βn P P →α1 P ∣α2 P ∣…∣αm P∣ε 例：文法G[E]: E →E+T∣T 改写成 E→TE E→+TE∣ε T →T*F ∣ F 改写成 T→FT T→*FT∣ε ②消除左递归：通过改写产生式我们可以消除直接左递归，但不能完全消除左递归，因为还存在着间接左递归的问题。 例如文法G[P]: P→Qc∣c Q→Rb∣b R→Pa∣a 表面上并看不出它的左递归性，但是仔细观察时不难发现P,Q,R都是左递归的，因为 P? Qc? Rbc? Pabc，即P ?+Pabc； Q ?+Qcab,R ?+Rbca亦然。 对这种左递归的消除就稍微麻烦一些。首先，从产生式中找这种形式的左递归。其思想也就是通过推导来寻找左递归、并进一步修改产生式。为此，我们设计以下算法： 消除左递归算法： Ⅰ.按任一顺序把文法G的所有非终结符排序成P1,P2,…Pn，按此顺序执行： Ⅱ.FOR i=1 TO n DO BEGIN FOR j=1 TO i-1 DO 把形如Pi→Pjγ的产生式改写成 Pi→δ1γ∣δ2γ∣…∣δkγ，其中 Pj →δ1∣δ2∣…∣δk是关于Pj的所 有产生式； 消除关于Pi的直接左递归性 END Ⅲ.化简由Ⅱ所得的文法——去除无用的非终结符。 例如上述文法G[P]： P→Qc∣c Q→Rb∣b R→Pa∣a Ⅰ.排序：R,Q,P Ⅱ. R无直接左递归。将R代入Q的候选式中得Q→Pab∣ab∣b，也无直接左递归；Q代入P得P→Pabc∣abc∣bc∣c，出现左递归了！消除P的直接左递归后得P→abcP‘∣bcP’ ∣cP‘, P’→abcP‘∣ε 。 如此可得文法为：  P→abcP∣bcP∣cP, P →abcP∣ε ，Q→Pab∣ab∣b, R→Pa∣a Ⅲ.显然，Q,R为多余的非终极符，因由P出发导不出含Q,R的句型，故应去掉。最终得到的文法是： P→abcP ∣bcP ∣cP, P →abcP ∣ε 该文法是无左递归的。当然排序不同，最终的产生式集可能不尽相同，但是文法是