第四章语法分析 语法分析是编译程序的核心部分、语法分析的作用是识别 由词法分析给出的单词符号序列是否是给定文法的正确句子 (程序), 自顶向下分析法也就是从文法的开始符号出发企图推导 出与输入的单词串完全相匹配的句子,若输入串是给定文法 的句子,则必能推出,反之必然出错。自顶向下分析法又可 分为确定的和不确定的两种,确定的分析方法需对文法有 定的限制,但由于实现方法简单、直观,便于手工构造或自 动生成语法分析器,因而仍是目前常用的方法之一。不确定 的方法即带回溯的分析方法(又称回溯法),这种方法实际上 是一种穷举的试探方法,因此效率低,代价高,因而极少使 用
第四章 语法分析 语法分析是编译程序的核心部分、语法分析的作用是识别 由词法分析给出的单词符号序列是否是给定文法的正确句子 （程序）， 自顶向下分析法也就是从文法的开始符号出发企图推导 出与输入的单词串完全相匹配的句子，若输入串是给定文法 的句子，则必能推出，反之必然出错。自顶向下分析法又可 分为确定的和不确定的两种，确定的分析方法需对文法有一 定的限制，但由于实现方法简单、直观，便于手工构造或自 动生成语法分析器，因而仍是目前常用的方法之一。不确定 的方法即带回溯的分析方法(又称回溯法)，这种方法实际上 是一种穷举的试探方法，因此效率低，代价高，因而极少使 用
4.1自顶向下的语法分析 4.1.1自顶向下的分析思想 不确定的自顶向下分析思想主要是带回溯的自上而下的分析 方法,所谓带回溯的自顶而下的分析方法是对任何输入串试 图用一切可能的办法,从文法符号开始符号(根结点)出发, 自上而下,从左到右地为输入串建立分析树。或者说,为输 入串寻找一个最左推导。这种。这种过程本质上是一种试探 过程,是反复使用不同的产生式谋求匹配输入串的过程。 例:设有文法G[S] s→aBCB-bbC→ DE FGc D→)dE→ehF→deGt 假定输入串为 abdet
4.1 自顶向下的语法分析 4.1.1自顶向下的分析思想 不确定的自顶向下分析思想主要是带回溯的自上而下的分析 方法，所谓带回溯的自顶而下的分析方法是对任何输入串试 图用一切可能的办法，从文法符号开始符号（根结点）出发， 自上而下，从左到右地为输入串建立分析树。或者说，为输 入串寻找一个最左推导。这种。这种过程本质上是一种试探 过程，是反复使用不同的产生式谋求匹配输入串的过程。 例：设有文法G[S]: S→aBC B→ib|b C→DE|FG|c D→d E→eh F→de G→t 假定输入串为 abdet
B B S|B|b B B d
显然上述分析法中不能有形如P→Pα的规则,也不能有 对某一非终结符P存在P=+=>Pa,即不能有规则左递归和文法 左递归。 确定的自顶向下分析方法,首先要解决从文法的开始符 号出发,如何根据当前的输入符号(单词符号)唯一地确定 选用哪个产生式替换相应非终结符往下推导,或构造一棵相 应的语法树,现举例说明: 例:若有文法G1[S] s→pAs→qBA→cAdA->a 若输入串W= pccadd,自顶向下的推导过程为 S=>pA=>pcAd=>pccAdd=>pccadd
显然上述分析法中不能有形如P→Pα的规则，也不能有 对某一非终结符P存在P=+=>Pα,即不能有规则左递归和文法 左递归。 确定的自顶向下分析方法，首先要解决从文法的开始符 号出发，如何根据当前的输入符号（单词符号）唯一地确定 选用哪个产生式替换相应非终结符往下推导，或构造一棵相 应的语法树，现举例说明： 例：若有文法G1［S］： S→pA S→qB A→cAd A→a 若输入串W=pccadd,自顶向下的推导过程为 S =>pA=>pcAd=>pccAdd=>pccadd
p A-pA=P=p A c a d ca d ca d cad ca d (d)
例:若有文法G2S]为: s→ApS→BqA→aA→cAB→bB-→dB 当输入串W=coap,那么试图推出输入串的推导过程为: S=>Ap=>CAp=>CCAp=>ccap A PAPA p A A a a) (b) (c) (d)
例：若有文法G2 [S]为： S→Ap S→Bq A→a A→cA B→b B→dB 当输入串W=ccap,那么试图推出输入串的推导过程为： S=>Ap=>cAp=>ccAp=>ccap
例:若有文法G3[S] S→aAS→dA→bAsA 若输入串为W=abd,则试图推导出abd串的推导过程为: S=>aA=>abAs=>abs=>abd A=aA=a b As b A s b A E
例：若有文法G3 [S]： S→aA S→d A→bAS A→ε 若输入串为W=abd,则试图推导出abd串的推导过程为： S=>aA=>abAS=>abS=>abd
4.1.2左递归和回溯性 1.左递归 左递归在自顶向下的分析技术中是有害的,为此使用 自顶向下的芬析方法的文法中不能出现左递归,因此需要消 去左递归。如果对于某非终结符A存在着推导A=+=>Aα,则 称文法左递归或间接左递归;如果存在规则A→Aα,则称 规则左递归或直接左递归。对于规则左递归是可以消除的, 而对文法左递归只能对满足一定条的文法进行消去。 (1)规则左递归的消除 a改写规则成右递归 把E→E+TT改写成E→T+ET 虽然在这里消去了左递归并不改变语言,但改变了结合性 b引进新的文法符号把E→E+TTT→TFF→(E改写 成 E→忙E+T→F节*TεF→(E)i
4.1.2 左递归和回溯性 1.左递归 左递归在自顶向下的分析技术中是有害的，为此使用 自顶向下的分析方法的文法中不能出现左递归,因此需要消 去左递归。如果对于某非终结符A存在着推导A=+=>Aα，则 称文法左递归或间接左递归；如果存在规则A→Aα，则称 规则左递归或直接左递归。对于规则左递归是可以消除的， 而对文法左递归只能对满足一定条的文法进行消去。 (1)规则左递归的消除 a.改写规则成右递归 把 E→E+T|T 改写成 E→T+E|T 虽然在这里消去了左递归并不改变语言，但改变了结合性。 b.引进新的文法符号把E→E+T|T T→T*F|F F→(E)|i 改写 成 E→TE’ E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i
般地: A→>Aa1Aa2|Aa3|…|Aanmβ1B2|3…|3n 改写成: A→B1A|B2AB3A…|BnA A→a1A|a2Aas3A…|mAlE 例:消去S→SSSS+|a中的左递归。 解:S→aS S’→S*SlS+S|E
一般地： A→Aα1 |Aα2 |Aα3 |···|Aαm|β1 |β2 |β3 |···|βn 改写成： A→β1 A’|β2 A’|β3 A’|···|βnA’ A’→ α1 A’|α2 A’|α3 A’|···|αm A’|ε 例：消去S→SS*|SS+|a中的左递归。 解：S→aS’ S’→ S*S’| S+S’|ε
(2)间接左递归的消除 如果一个文法是无环的(即P=+=>P)和没有E产生式,那么 可用下列算法消除 a以任意次序排列非终结符A1A2A3,…An b.for(i=1;<=n;i++) for(j=1; j<=1-1: j ++) 用产生式A61V|6263…|6k代替每个形式为 A→AY的产生式其中A→6162636是所有当前 生式; 消去A产生式中的直接左递归 C.除去那些从开始符号出发永远无法到达的非终结符的产生规 贝
(2)间接左递归的消除 如果一个文法是无环的(即P=+=>P)和没有ε产生式，那么 可用下列算法消除。 a.以任意次序排列非终结符A1 ,A2 ,A3 ,···,An b.for(i=1;i<=n;i++) { for(j=1;j<=i-1;j++) 用产生式Ai→δ1γ|δ2γ|δ3γ|···|δkγ代替每个形式为 Ai→Ajγ的产生式其中Aj→δ1 |δ2 |δ3 |···|δk是所有当前 Aj 产生式； 消去Ai产生式中的直接左递归 } c.除去那些从开始符号出发永远无法到达的非终结符的产生规 则