第四章语法分析语法分析是编译程序的核心部分、语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序），自顶向下分析法也就是从文法的开始符号出发企图推导出与输入的单词串完全相匹配的句子，若输入串是给定文法的句子，则必能推出，反之必然出错。自顶向下分析法又可分为确定的和不确定的两种，确定的分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。不确定的方法即带回溯的分析方法(又称回溯法)，这种方法实际上是一种穷举的试探方法，因此效率低，代价高，因而极少使用。4.1自顶向下的语法分析4.1.1自顶向下的分析思想不确定的自顶向下分析思想主要是带回溯的自上而下的分析方法，所谓带回溯的自顶而下的分析方法是对任何输入串试图用一切可能的办法，从文法符号开始符号（根结点）出发，自上而下，从左到右地为输入串建立分析树。或者说，为输入串寻找一个最左推导。这种。这种过程本质上是一种试探过程，是反复使用不同的产生式谋求匹配输入串的过程。例：设有文法G[S]:S→aBCB→ib|bC→DE|FG|cD→dE→ehF→deG→t假定输入串为abdet显然上述分析法中不能有形如P→Pα的规则，也不能有对某一非终结符P存在P=+=>Pα,即不能有规则左递归和文法左递归。确定的自顶向下分析方法，首先要解决从文法的开始符号出发，如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符往下推导，或构造一棵相应的语法树，现举例说明：例：若有文法G1［S］：S→pAS→qBA→cAdA→a若输入串W=pccadd,自顶向下的推导过程为S=>pA=>pcAd=>pccAdd=>pccadd例：若有文法G2[S]为：S→ApS→BqA→aA→cAB→bB→dB当输入串W=ccap,那么试图推出输入串的推导过程为：S=>Ap=>cAp=>ccAp=>ccap例：若有文法G3[S]：S→aAS→dA→bASA→ε若输入串为W=abd,则试图推导出abd串的推导过程为：S=>aA=>abAS=>abS=>abd4.1.2左递归和回溯性1.左递归左递归在自顶向下的分析技术中是有害的，为此使用自顶向下的分析方法的文法中不能出现左递归,因此需要消去左递归。如果对于某非终结符A存在着推导A=+=>Aα，则称文法左递归或间接左递归；如果存在规则A→Aα，则称规则左递归或直接左递归。对于规则左递归是可以消除的，而对文法左递归只能对满足一定条的文法进行消去。(1)规则左递归的消除a.改写规则成右递归把E→E+T|T改写成E→T+E|T虽然在这里消去了左递归并不改变语言，但改变了结合性。b.引进新的文法符号把E→E+T|TT→T*F|FF→(E)|i改写成E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i一般地：A→Aα1|Aα2|Aα3|···|Aαm|β1|β2|β3|···|βn改写成：A→β1A’|β2A’|β3A’|···|βnA’A’→α1A’|α2A’|α3A’|···|αmA’|ε例：消去S→SS*|SS+|a中的左递归。解：S→aS’S’→S*S’|S+S’|ε(2)间接左递归的消除如果一个文法是无环的(即P=+=>P)和没有ε产生式，那么可用下列算法消除。a.以任意次序排列非终结符A1,A2,A3,···,Anb.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.除去那些从开始符号出发永远无法到达的非终结符的产生规则。例：消去下列文法的左递归：S→Aa|bA→Ac|Sd|ε解：设A1=SA2=A则S→Aa|bA→Ac|（Aa|b）d|εS→Aa|bA→A（c|ad）|bd|εS→Aa|bA→bdA’|A’A’→cA’|adA’|ε2.回溯性在自顶向下的语法分析中，当前面临非终结符P如存在规则P→α1|α2|α3|···|αn，当前输入符号为a时,究竟选用哪一个候选式，如采用回溯则效率太低，现如能改变文法使每个候选式没有相同的“头符号”，则就能根据当前输入符号a决定选用那一个产生式。例：S→ifEthenS|ifEthenSelseS|b改写成：S→ifEthenSS’|bS’→elseS|ε一般地A→δβ1|δβ2|δβ3|···|δβn|γ改写成：A→δA’|γA’→β1|β2|β3|···|βn例：消去文法G[S]:S→aBC