第2章文法和语言

第2章文法和语言

随着高级语言的出现和使用，必然面临编译理论的研究和编译程序的设计。编译过程是一个十分复杂的信息加工过程，其加工对象是用高级语言编写的程序。1.为了顺利完成编译工作，要解决的问题是：

如何确切地描述或定义一种程序设计语言？如何识别和分析这些语言？2.在20世纪50年代，N.choumsky首先对语言的描述进行探讨。提出了用来描述语言的数学系统；定义了四类性质不同的文法和语言（0型文法、1型文法、2型文法和3型文法）。主要内容§

2.1语言和文法的直观概念§

2.2符号和符号串§

2.3文法和语言的形式定义§

2.4文法的类型§

2.5上下文无关文法及其语法树§

2.6句型的分析§

2.7有关文法中的一些说明§2.1语言和文法的直观概念程序设计语言的定义 语言是一个记号系统。汉语--符合汉语语法的句子的全体英语--符合英语语法的句子的全体程序设计语言--该语言的程序的全体

程序设计语言由语法和语义定义：语法(syntax)定义:是一组规则，用它可以形成和产生一个合适的程序描述工具:文法作用:定义什么样的符号序列是合法的，与符号的含义无关。语义(semantics)分类:静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的动态语义：表明程序要做什么描述工具:指称语义,操作语义等作用:检查类型匹配，变量作用域等文法的直观概念如何来描述一种语言？文法是描述语言的语法（形式）结构的形式规则。如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。有两个途经：生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。§2.2符号和符号串字母表定义:元素的非空有穷集合例：∑={0‚1}Α={a‚b,c}元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用符号组成。符号串定义:由字母表中的符号组成的任何有穷序列例：

0,00,10是字母表∑={0，1}上的符号串

a,ab,aaca是Α={a，b，c}上的符号串在符号串中，符号是有顺序的，顺序不同,代表不同的符号串，如:ab和ba不同不含任何符号的符号串称为空串，用ε表示

注意:{ε}并不等于空集合{}符号串长度:符号串中含有符号的个数 如: |abc|=3 |ε|=0子符号串设有非空符号串u=xvy，其中符号串则称v为符号串u的子符号串。V≠ε例如符号串x=a+b*(c+d)，则a，a+b*，与(c+d)等都是x的子符号串，且其长度分别|a|=1，|a+b*|=4，|(c+d)|=5符号串的头与尾如果z=xy是一个符号串，则x是z的头，而y是z的尾。如果y非空，则x是z的固有头；如果x非空，则y是z的固有尾。例如：字母表A={a,b,c}上的符号串x=abc,则x的头：ε,a,ab,abc,尾:ε,c,bc,abc固有头:ε,a,ab,固有尾:ε,c,bc符号串的运算符号串的连接：设x、y是符号串,它们的连接是把y的符号写在x的符号之后得到的符号串xy

例如x="ST"，y="abu"，则xy="STabu" 显然εx=xε=x符号串的方幂：把符号串a自身连接n次得到的符号串an=

aa…aa

例如a1=aa2=aaa0=ε符号串集合：定义:若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。符号串集合的乘积：符号串集合A和B的乘积定义为: AB={xy|x∈A且y∈B}，即AB是由A中的串x 和B中的串y连接而成的串xy组成的集合。 若集合A=ab,cdeB=0,1

则AB=ab0,ab1,cde0,cde1 显然{ε}A=A{ε}=A符号串集合的方幂:设A是符号串的集合，则称Ai为符号串集A的方幂，其中i是非负整数。具体定义如下:A0={ε}A1=A,A2=AAAK=AA......A(k个)集合的闭包闭包 集合Σ的闭包Σ*定义如下： Σ*=Σ0∪Σ1∪Σ2∪Σ3∪… 例：设有字母表Σ={0，1} 则Σ*=Σ0∪Σ1∪Σ2∪… ={ε,0,1,00,01,10,11,000,…} 即Σ*表示Σ上所有有穷长的串的集合。正闭包Σ+=Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。

+表示上的除ε外的所有用穷长串的集合Σ*=Σ0∪Σ+ Σ+=ΣΣ*=Σ*Σ 字母表上的一个语言是上符合某种规则的一些符号 串的集合，是*的一个子集。 例如：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}1.集合{ab,aabb,aaabbb,…,anbn,…}或 {w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。集合{a,aa,aaa,…}或{w|w∈Σ*且w=an,n≥1}为字母表上的一个语言。ε是一个语言。小结1符号与字母表2符号串3符号串的运算4符号串集合5集合的闭包6字母表的闭包§2.3文法和语言的形式定义1．文法的定义2．文法形式上的约定3．推导与归约4．句型、句子、语言的定义5．文法的等价

1．文法的定义

“我是大学生”是汉语的一个句子

用::=表示的汉语句子的构成规则：

〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉｜〈名词〉 〈代词〉∷=我｜你｜他 〈名词〉∷=王明｜大学生｜工人｜英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷=是｜学习 〈直接宾语〉∷=〈代词〉｜〈名词〉句子“我是大学生”的推导过程如下：从句子出发，反复把规则中的”::=”左边的成分替换成右边的成分。〈句子〉

〈主语〉〈谓语〉

〈代词〉〈谓语〉

我〈谓语〉 我〈动词〉〈直接宾语〉

我是〈直接宾语〉

我是〈名词〉

我是大学生关键思路从文法的开始符号出发，反复使用产生式，对非终结符进行替换（展开），直到整个字符串中不在包含非终结符。这时，得到了这个文法的一个句子（一个程序）这个过程称为推导文法的定义包括四个组成部分：一组终结符号（不能被替换的符号，单词符号）一组非终结符号（能够被替换为终结符号或非终结符号，语法单位）一个开始符号（从这个符号开始替换，最大语法单位-程序）一组产生式（替换规则，把左边的字符串替换为右边的字符串）文法的形式定义产生式（规则） 产生式是一个有序对(α,β)，通常写作 α→β（或α::=β）文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN(Nonternimal)：非终结符集 VT(Terminal)：终结符集 P(Production)：产生式（规则）集合 S：开始符号或识别符号说明:V=VN∪VT，V称为文法G的字母表P中产生式形如：α→β,其中α∈V+且至少含一个非终结符，β∈V*VN,VT和P是非空有穷集VN∩VT=φS是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分，如<赋值语句>，它是构成程序的一个语法成分，这个符号本身不会在程序中出现，而终结符是组成程序的具体的符号。2.文法形式定义上的约定文法习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号,或用G[S]表示S是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，S是开始符号希腊字母代表由终结符号和非终结符号组成的符号串α、β、γ左部相同的产生式A→α,A→β可以记为A→α|β， 其中“|”是“或”的意思，α,β分别称为侯选式如：对于文法G：S→0S1可写成G[S]：S→0S1S→01S→01例：文法G=(VN,VT,P,S) 其中：VN={S}，VT={0，1}，P={S→0S1,S→01} 开始符为S例：文法G=(VN,VT,P,S)

VN={标识符，字母，数字}， VT={a,b,c,…x,y,z,0,1,…,9}， P={<标识符>→<字母>， <标识符>→<标识符><字母> <标识符>→<标识符><数字>， <字母>→a,…,<字母>→z，

<数字>→0,…,<数字>→9}， S=<标识符>例如: 文法G[S]：

S→A|SA|SD A→a|b|…|z D→0|1|…|93.推导(Derivation)与归约(Reduction)直接推导和直接归约： α→β是文法G的产生式，若有v，w满足： v=γαδ,w=γβδ,其中γ,δ∈V* 则称v直接推导出w,也称w直接归约到v, 记作vw直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程例文法G：S→0S1，S→01有直接推导： S0S1 （S→0S1） 0S100S11 （S→0S1） 00S11000S111 （S→0S1） 000S11100001111（S→01）

推导例题1文法G1：S->bA,A->aA|a定义了一个什么样的语言？S=>bA=>baS=>bA=>baA=>baaS=>bA=>baA=>baaA=>baaa……S=>bA=>baA=>…=>ba…aL(G1)={ban|n>=1}L(G1)={以b开头后跟一个或多个a的串}推导例题2e.g.文法产生的语言文法G4对句子aaabb的推导：S=>AB SAB

=>aAB AaA

=>aaAB AaA

=>aaaB Aa

=>aaabB BbB

=>aaabb BbA=>aB=>abA=>Ab=>abe.g.文法产生的语言文法G5对句子aaaabbbb的推导：S=>aSb SaSb =>aaSbb SaSb =>aaaSbbb SaSb =>aaaabbbb Sab直接推导序列和广义推导直接推导序列：

或+若存在v=u0u1...un=w,(n>0)则称v+w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。广义推导：或*

若有v+w或v=w，则记为v*w，v广义推导出w，w广义规约到v（可以包含0步推导）+*三种推导的比较直接推导（）的长度为1直接推导序列（+）的长度n≥1广义推导（*）的长度≥0规范推导和规范归约对于一文法而言，从开始符到某句型的推导过程可能不唯一。例如，文法G[E]中从E到i+i*i的推导有：(1)EE+TE+T*FT+T*FT+T*iF+T*ii+T*ii+F*ii+i*i(2)EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*Fi+i*i(3)EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i(4)……规范推导为了让计算机自动地进行推导，通常我们只考虑最左或最右推导。最左（右）推导：在推导序列的每一步直接推导中，被替换的总是当前句型中最左（右）的非终结符。例如，上页中的（2）、（3）分别是最左、最右推导。形式上，从符号串到符号串的推导序列 *xUy

xuy*总有xVT*(yVT*) 时，称为最左（右）推导定义：最左（右）推导所得句型称为左（右）句型；最右推导称为规范推导；右句型称为规范句型。

举例例1:文法G[S]:S→ABA→A0|1BB→0|S1请给出句子101001的最左和最右推导。最左推导：SAB1BB10B

10S1

10AB1

101BB1

1010B1

101001最右推导：SAB

AS1AAB1

AA01

A1B01

A1001

1B1001

101001例2文法G： E→E+T|T T→T×F|F F→（E）|i句子i+i×i的推导过程如下：最左推导：

E=>E+T=>T+T=>F+T=>i+T=>i+T×F=>i+F×F =>i+i×F=>i+i×i最右推导：

E=>E+T=>E+T×F=>E+T×i=>E+F×i=>E+i×i =>T+i×i=>F+i×i=>i+i×i递归规则借助于自身来定义的规则，称为递归规则。如<数字序列>::=<数字序列><数字>递归规则的存在，使得能用有穷个规则来定义无穷的语言。如果一个规则形如U::=…U…（或U→xUy），则该规则是递归的；如果规则形如U::=U…（或U→Uy），则称左递归的；如果规则形如U::=…U（或U→xU），则称右递归的。例：<标识符表>::=<标识符表>,<标识符>（左递归规则）<因式>::=!<因式>（右递归规则）文法的递归性定义：对于某文法，存在U∈VN，如果U+…U...，则称该文法递归于U；如果U+U…，则称该文法左递归于U；如果U+…U，则称该文法右递归于U。例1：C语言中：<语句>+…<语句>(文法右递归于<语句>)例2：U→VxV→Uy|z（都不递归）有U+Uxy，所以该文法是左递归的。注：描述程序设计语言的文法必定都是递归的。递归文法文法G[E]：

EE+T|T TT*F|F F(E)|i显然，G1，G2都是递归定义的。所谓递归定义，指在定义一个语法成分时，直接或间接地使用了语法成分自身。递归文法例如，文法G1，含有递归非终结符<标识符>，文法G2中的E、T是直接递归的，F是间接递归的：

F(E)(T)(F)注意，文法与语言之间无一一对应的关系。一文法可唯一地确定一语言，但对一语言而言，产生它的文法不止一个。4．句型、句子、语言的定义句型和句子 设有文法G[S]，若符号串α是从开始符推导出来的,即S=>*α，则称α是文法G的句型。若α仅由终结符组成,即S=>*

α，且α∈VT*，则称α是文法G的句子。例文法G[S]：S→0S1，S→01 因为S0S100S11000S11100001111 所以S,0S1,00S11,000S111,00001111都是G的句型00001111是G的句子

由规范推导所得的句型称为规范句型语言的定义

由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)={x|S=>*x，且x∈VT*} 例文法G：S→0S1，S→01 S0S100S1103S13…0n-1S1n-1

0n1n L(G)={0n1n|n≥1}文法和语言的关系： 文法G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成根据文法，可以通过推导得到该文法相应的语言；例：G[E]：E→E+T|T T→T×F|F F→(E)|aE

E+TT+TF+Ta+Ta+T×Fa+F×Fa+a×Fa+a×a 表示一切能用符号a，+，×，(，)构成的算术表达式有了语言的要求，也可以为该语言设计文法例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为：

A→0B|1C

B→1|1A|0BB

C→0|0A|1CC5.文法的等价若L(G1)=L(G2)，则称文法G1和G2是等价的。

例如文法 G1[A]：A→0RA→01R→A1 G2[S]：S→0S1S→01 所定义的语言都是0n1n 两文法等价§§2.4文法的类型

Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：0型文法（PSG）0型语言或短语结构语言1型文法（CSG）1型语言或上下文有关语言2型文法（CFG）2型语言或上下文无关语言3型文法（RG）3型语言或正则（正规）语言文法的四元组表示是由N.Chomsky于1956年描述形式语言时给出的。他还对产生式的形式给予不同的限制而定义了四类基本文法。0型文法:若P中任一产生式都有一般形式V+V*且对，不加任何限制，则称G为0型文法（短语结构文法，记为PSG:PhraseStructureGrammar)。由0型文法生成（或者说：定义）的语言称为0型（递归可枚举）语言。它可由图灵（Turing）机识别。例如：SACaBCaaaCCBDBCBEaDDaADACaEEaAE就是一个0型文法，它所产生的语言为对于程序设计语言来，0型文法有很大的随意性，还须加以限制1型文法和语言若一0型文法所有产生式具有形式1A2

12其中，1,2V*V+AVN,则称G为1型(前后文有关)文法，记为CSG(ContextSensitiveGrammar)。1型文法产生的语言称为前后文有关语言CSL，它可由线性限界自动机识别。命名的由来：只有当非终结符A的前后分别为1,2时，才能将A替换为。1型文法还有另一种定义形式：G的每个产生式形为且满足： ||||,V+则G是1型文法上述两种定义形式是等价的。即任一种形式定义的文法所产生的语言都可由另一种形式定义的文法产生注：根据定义，含有产生式的文法不是1型文法。由于实际需要，我们将-产生式作为1型文法的特例而接受之。例文法G：S|AAaABCAabCCBBCbBbbbCbccCcc因G含有-产生式，所以它不是一个严格意义下的1型文法。它所产生的语言为2型文法和语言若一1型文法G中所有产生式具有形式: A

V+ AVN

则称G为2型(前后文无关)文法，记为CFG(ContextFreeGrammar)。2型文法产生的语言称为前后文无关语言CFL，它可由下推自动机识别。若允许-产生式存在，则CFG产生式形式为 A V* AVN例：G[S]=({S},{a,b},{SaSbSab},S)产生的语言为3型文法和语言若一2型文法G中仅含有形如 AaBAa的产生式，其中A,B

VN,aVT则称G为右线性文法。类似地，若G中仅含有形如

ABaAa的产生式，则称G为左线性文法。通常，把左线性文法和右线性文法都称为3型文法（正规文法）3型文法产生的语言称为3型（正规）语言，它可由有限自动机识别。正规语言可用正规表达式表示。注：若一文法即含左线性又含右线性产生式，则它不一定是3型文法！3型文法还可拓广定义为ABA（

VT+）四类语言之间的关系由各类文法的定义可知，3型语言一定是2型语言，而反之不一定成立；同理，2型语言是1型的也是0型的，反之不真。若把各类语言视为语言族LK

，K=0,1,2,3则它们之间有真包含关系：四种文法之间的逐级“包含”关系2型文法1型文法3型文法0型文法§2.5上下文无关文法及其语法树1．上下文无关文法(Context-FreeGrammar)

自然语言是上下文有关的。上下文无关文法有足够的能力描述现今程序设计语言的语法结构例：算术表达式：E→i|E+E|E*E|（E） <赋值语句>→i:=E <条件语句>→if<条件>then<语句> |if<条件>then<语句>else<语句>我们更关心上下文无关文法产生的句子的分析2.语法树(推导树ParseTree)作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树语法树的概念定义：语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。语法树的相关概念结点：每个树的结点对应于一个符号。结点的名字就是该符号。边：两个结点之间的连线。根结点：没有边进入的结点。分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）子树：语法树的某个结点和它向下射出的部分末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。语法树的特征给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：1、根结点的标记是开始符号S；2、每个结点的标记都是V中的一个符号；3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么A::=A1A2..AR一定是P中的一条规则；4、若一标记为A的结点至少有一个除它以外的子孙，则A∈VN5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。从推导构造语法树方法：把识别符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。例如：推导SABAcBdAccddabccddSBBdbaAcdc语法树的构造过程SABAcBdAccddabccddSSBASBBdAc（1）（2）（3）SBBdAcdcSBBdbaAcdc（5）（4）例：文法G：E→E+T|T T→T×F|F F→（E）|i 句型T+T×F的推导过程与语法树TFT×E=>E+TEET+EET+TFT×E=>E+T=>E+T×F=>T+T×F=>T+T=>T+T×F从语法树中看不出句型中的符号被替代的顺序从左到右读出叶子结点得到的符号串，为文法的句型。也把该语法树称为该句型的语法树。从语法树构造推导方法：从分支建立直接推导，然后从语法树中剪去之这个分支，直到无分支可剪。语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没有表明使用规则的顺序。一棵语法树可能对应不止一种推导。从语法树构造推导的过程例如文法G[S]：S::=ABA::=aAb|abB::=cBd|cd存在下面的推导可能：SABAcBd

(4)(3)Accddabccdd(2)(1)SAB

abBabcBd

abccdd（从后往前看）SBBdbaAcdc(1)(2)(3)(4)文法G：E→E+E|E×E|（E）|i句子i×i+i两个不同的最左推导：推导1：E

E+EE×E+Ei×E+Ei×i+Ei×i+i推导2：EE×Ei×Ei×E+Ei×i+Ei×i+i3.文法的二义性(Ambiguity)文法的二义性存在这样的文法G，其某个句子wL(G),可对应结构不同的语法树，即w对应了多个不同的最左（右）推导，这类文法称为二义性文法。例如，G3[E]：EE+E|E*E|(E)|i的句型i+i*i及文法CifBthenC|ifBthenCelseC CS

的句型：ifB1

then

ifB2

thenS1

elseS2上面两个句型均有两个不同的语法推导树（见下页），所以，它们是二义性文法EEEEE+*iiiEEEEE+*iii

S1 S2ifB1thenCelse CifB2

thenCCCifB1

thenCS1S2ifB1thenCelseC二义性语法的例子关于二义性文法应指出，二义性是一种常见的语法现象，然而，对于编译程序而言，二义性文法是有害的。为解决二义性文法带来的不确定性问题，通常的方法一是修改文法。二是利用附加条件。例如，i+i*i的归约过程中，若规定*比+优先级高，则可强制性地让系统先按E*E进行归约，而不是先按E+E进行归约；又比如，若强制规定else只能和距其最近的尚未被匹配的then进行匹配，就可解决else悬空的问题。关于二义性文法应指出，任一前后文无关文法是否是二义性的是不可判定的。对于某个具体的文法而言，其二义性还是可判定的。存在一些判定文法是否二义性的充分条件：若一文法含有既是左递归又是右递归的文法符号，即有 A+AvAvV* 或 A+A 或 A+A及AA

则G必定是二义性的。并非所有的文法可消除二义性。即存在这样的CFL，定义它的一切文法都是二义性的。这样的语言称为先天二义性语言。例如，为一先天二义性语言。CFL的先天二义性也是不可判定的。为什么要避免文法产生二义性？二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。如何消除文法的二义性？方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。如文法G[E]:E→iE→E+EE→E*EE→(E)将运算符的优先顺序和结合规则加到原有文法中，则可构造无二义性的文法G’[E]:E→T|E+TT→F|T*FF→（E）|i二义性文法的改造注意：文法的二义性性与语言二义性的区别因为可能有两个不同的文法G1和G2，其中有一个是二义性的，但却有L(G1)=L(G2)。如果产生某上下文无关语言的每个文法都是二义性的，则说明该语言是先天二义性的，即该语言是二义性的。§2.6 句型的分析任务:句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。它是一种推导或语法树的构造过程。对于一个给定的符号串，试图按照文法的规则构造其对应的推导，或语法树。句型的分析算法分类自顶向下的语法分析(Top-Downparsing)自底向上的语法分析(Bottom-Upparsing)§2.6.1自顶向下的分析方法定义:

对于给定的符号串w，采用自顶向下的分析来判断w是否为L(G[S])的句子的常见方法是：试图建立从开始符S到w最左推导: S*w

显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是带回溯的。

为提高效率，就应尽量避免回溯

语法树的构造：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。

例文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子S推导过程：cAdab=>cabdS=>cAd自上而下方法的主要问题对输入串cabd自上而下构造语法树的另一过程不成功，不成功的原因是选错产生式A→a自上而下分析的主要问题是选择产生式:假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ScAda~就是从已给的符号串w出发，试图以相反的方向为w建立一个规范推导，最终得到文法的开始符。推导的逆过程称作归约，它是把当前的符号串中的构成文法某个产生式A右部的子串替换成产生式的左部符号A，得到一个新的符号串A。这样的一步动作，称为进行了一步归约。例如，符号串F+i*i中的F可按产生式TF归约为T，从而得到新的符号串T+i*i。若从给定的符号串w出发，一步步地将其归约，最终得到文法的开始符号，则说明w是该文法定义的一个句子。归约成功，否则，归约失败。若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是规范归约（即最左归约）。规范归约是规范推导的逆过程。关于最左（右）归约、直接归约、归约等的形式定义不再赘述。2.6.2自底向上的语法分析例符号串i+i*i的归约过程由上表可以看出，归约过程是最左归约，它恰好是规范推导的逆过程。这正是把最左归约定义为规范归约的原因。例文法G：S→cAd

A→ab

A→a

识别输入串w=cabd是否为该文法的句子cabd归约过程：用“|-”表示归约，下划线部分为被归约符号cabd|-cAd|-SAS关于归约的一点说明注意，前面例子中归约的第五步中，当前的符号串为E+T*i，除了可将i归约成F外，还可将E+T或T归约成E，分别得到符号串E*i和E+E*i。但是，若真按这两个方案进行归约，则当我们把其归约成E*E或E+E*E时，就再也归约不下去了。这就告诉我们在第五步时，唯一正确的归约是将i归约为F，也就是说，i是唯一可被归约的最左子串。对输入串cabd的两种归约过程 （1）cabd|-cAd|-S归约到开始符 （2）cabd|-cAbd不能归约到开始符那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的最左子串呢？短语和句柄问题:在自底向上(简记为)的语法分析中,对于每一步直接归约,应如何正确地确定当前句型中应被归约的最左子串?考虑文法G2[E]的句型=E+T*F+i,从开始符E推导出的语法树见右图该树中含有若干子树,如T(2)为根的子树对应的叶结点为T(3)*F(3),由于它是一直接子树,文法中必有产生式T->T*F;因此,称T*F是句型相对于产生式T->T*F的直接短语.同理,F(1)对应的直接短语为i.以E(1)为根的子树相应的叶结点为E(2)+T(3)*F(3),所以,称为句型相对于非终结符E的短语.同理,i是相对于T(1)的短语EE(1) +T(1)E(2)+T(2)T(3)*F(3)F(1)i短语、直接短语及句柄的定义定义: 设αβδ是文法G[S]中的一个句型，如果有S=>*αAδ且A=>+β，则称β是句型αβδ相对于非终结符A的短语 特别的如有A=>β，则称β是句型αβδ相对于规则A→β的(直接短语)简单短语。 一个句型的最左简单短语称为该句型的句柄(Handle)。句柄就是“可归约串”例如，对句型=E+T*F+i，由定义，有：(1)E*E+T+i(=E+,A=T,=+i)及TT*F(=),故T*F是相对于产生式T->T*F的直接短语;(2)E*E+T*F+FFi,i是相对于产生式F->i的直接短语;(3)E*E+i与E+E+T*F,E+T*F是相对于非终结符E的短语;(4)E*E及E*E+T*F+i(=),是相对于E的短语注:由定义可知,直接短语也是短语,但短语不一定是直接短语.归约时被替换子串的选择从句型=E+T*F+i的语法树可知,E+T绝不是它的一个直接短语,因为虽然E->E+T是G2的一个产生式,但不存在从E到E*F+i的推导,所以,当判断一符串是否为某一句型的短语时,须检查定义的两个条件是否同时满足.采用分析时,每步归约就是将一个产生式右部替换其左部,也就是把该句型的语法树中的一棵直接子树的末端结点剪去.即每次归约的符号串必是当前句型的一个直接短语.但是,对一句型而言,其直接短语可能不唯一.为了让分析能够机械地进行,我们只考虑规范归约(最左归约),即归约过程替换的是归左直接短语.我们以L(G2)的句子i+i*i+i为例,给出其最右推导(规范归约的逆过程),来说明每次规范归约的子符号串用语法树求短语、句柄短语：（子）树的末端结点形成的符号串是相对于(子)树根的短语。简单短语（直接短语）：简单子树的末端结点形成的符号串是相对于简单子树根的简单短语。句柄：最左简单子树的末端结点形成的符号串是句柄。例：对于文法G[S]：S::=ABA::=Aa|bBB::=a|Sb

求句型baSb的全部短语、直接短语和句柄？baSb为句型baSb的相对于S的短语；ba为句型baSb的相对于A的短语；a为句型baSb的相对于B的短语,且为直接短语和句柄；Sb为句型baSb的相对于B的短语,且为直接短语。SSABbabSB例：文法G[E]:E→E+T|T T→T×F|F F→（E）|i的一个句型是T×F+i，相应的语法树见右图：EET+TTF×Fi

.因为E=>*T+i且T=>T×F，所以T×F

是句型相对于T的短语，且是相对 于T→T×F的直接短语.因为E=>*T×F+F且F=>i，所以i是句 型相对于F的短语，且是相对于F→i 的直接短语.因为E=>*E且E=>+T×F+i，所以 T×F+i是句型相对于E的短语

.T×F是最左直接短语，即句柄

文法G[E]: E→E+T|T T→T×F|F F→（E）|i的一个句型是T×F+iEET+TTF×Fi虽然F+i是句型T×F+i的一部分，但不是短语，因为尽管有E=>+F+i，但是不存在从文法开始符E=>*T×E的推导短语与语法树 从句型的语法树上很容易找出句型的短语语法树中每棵子树的末端结点构成相对于子树根的短语 例：文法G[E]的句型T×F+i语法树：EET+TTF×Fi五棵子树对应三个短语T×F，i，T×F+i两层子树的末端结点构成直接短语两棵两层子树对应两个直接短语： T×F，i位于最左边的两层子树的末端结点构成句柄： T×FEE+TE+FE+iE+T+iE+T*F+iE+T*i+iE+F*i+iE+i*i+iT+i*i+iF+i*i+ii+i*i+iEE+TE+TT*FTFiFFiii1234567891011§2.7有关文法实用中的一些说明有关文法的实用限制有害规则和多余规则有害规则：U→U,无用且引起文法的二义多余规则：所有句子推导都用不到的规则，表现形式：不可到达：不在任何句型中出现的非终结符的规则，即除了开始符号外，U不出现在该文法的任何其他的规则的右部。不可终止：不可推出终结符号串的非终结符的规则，若在推导中使用该规则，则在也不能推出终结符号串。文法的化简与改造1无用符号和无用产生式的删除设G=(VN,VT,P,S)是一文法,XVNVT,X称为是有用的,若X至少出现在一个句子的推导过程中,即X满足:(1)存在,V*,有S*X (2.12)(2)存在wVT*,使 X*w (2.13)否则,称X是无用的.若一产生式含有无用符号,则此产生式称为无用产生式.无用产生式给语法分析带来了许多麻烦,应予以删除.消除无用产生式的算法算法2.1将文法G=(VN,VT,P,S),改造为G1=(V’N,VT,P’,S),使得对于每个XV’N,存在wVT*,满足X*w.(1)置V’N,P’为空;(2)对于P中每个产生式A,若(V’NVT)*,则将A加入V’N中;(