《形式语言的基础知识.ppt》由会员分享，可在线阅读，更多相关《形式语言的基础知识.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章章 形式语言的基础知识形式语言的基础知识内容提要内容提要n形式语言形式语言n文法和语言文法和语言n分析树分析树2.1 形式语言n符号和字符串符号和字符串n符号符号：抽象实体，不加以形式定义。就像：抽象实体，不加以形式定义。就像几何学中的几何学中的“点点”。或者叫原子概念，凭。或者叫原子概念，凭直觉去体会。直觉去体会。n字母表字母表：有限个符号的集合。字母表一般：有限个符号的集合。字母表一般用用 记。例如记。例如,英语的字母表英语的字母表=a,b,z,A,B,Z；汉语的字母表由汉；汉语的字母表由汉字构成。字构成。n字符串字符串：字母表中符号的有穷序列。：字母表中符号的有穷序列。n字符串的
2、长度字符串的长度：组成该字符串的符号的个：组成该字符串的符号的个数。字符串数。字符串 的长度记作的长度记作|。n例如字符串例如字符串banana的长度为的长度为6。空字符串。空字符串记作记作，由，由0个符号组成，故个符号组成，故|=0。n字符串的前缀字符串的前缀：该字符串领头的若干符号。：该字符串领头的若干符号。n字符串的后缀字符串的后缀：该字符串结尾的若干符号。：该字符串结尾的若干符号。n例如，字符串例如，字符串abc具有前缀具有前缀，a，ab和和abc；其后缀有；其后缀有，c，bc，abc。n若字符串的前缀（或后缀）不是字符串本若字符串的前缀（或后缀）不是字符串本身，则称之为真前缀（或真后
3、缀）。身，则称之为真前缀（或真后缀）。n字符串的子串字符串的子串：去掉字符串的一个前缀和：去掉字符串的一个前缀和后缀后得到的字符串。例如，后缀后得到的字符串。例如，nan是是banana的一个子串。的一个子串。n字符串的子序列字符串的子序列：从字符串中删除：从字符串中删除0个或个或多个符号后得到的串（这些被删除的符号多个符号后得到的串（这些被删除的符号可以不相邻）。例如，可以不相邻）。例如，baaa是是banana的子的子序列。序列。n字符串的运算字符串的运算n字符串的连接字符串的连接：如果：如果x和和y是字符串，那么是字符串，那么x和和y的连接的连接xy是把是把y接到接到x后面所形成的字后面
4、所形成的字符串。符串。n例如，如果例如，如果x=dog，y=house，则，则xy=doghouse。由。由 的定义，显然有的定义，显然有=。n字符串的方幂字符串的方幂：设：设x是字符串，把是字符串，把x自身连自身连接接n次得到字符串次得到字符串z，即，即z=xxxx，称为字，称为字符串符串x的的n次方幂，记作次方幂，记作z=xn。我们规定。我们规定x0=。n例如，设例如，设x=AB，则，则x0=，x1=AB，x2=ABAB，x3=ABABAB。对于，。对于，n0，有，有xn=xxn-1=xn-1x。n字符串集合的连接字符串集合的连接：两个字符串集合：两个字符串集合A和和B的连接的连接AB=x
5、y|x A，y B，即，即AB是满是满足足x属于属于A，y属于属于B的所有字符串的所有字符串xy所组成所组成的集合。的集合。n例如，若例如，若A=a,b，B=c,d，则，则AB=ac,ad,bc,bd。另外，我们有。另外，我们有 A=A=A。n对任意字符串集合对任意字符串集合A，An=AAAA，即，即n个个A相连。相连。A0定义为定义为。nKleene闭包闭包：一个固定的字母表：一个固定的字母表 上所有上所有的字符串的集合称为集合的字符串的集合称为集合 的的Kleene闭包，闭包，记作记作*。根据定义，我们有。根据定义，我们有*=012 n。n正闭包正闭包：+=123 n称为称为 的的正闭包。
6、显然有正闭包。显然有*=0+=*=*n形式语言形式语言语言语言：给定字母表上的任意一个字符串集合，：给定字母表上的任意一个字符串集合，即即*的子集（的子集（*本身也是自己的子集，所以本身也是自己的子集，所以*也是语言）也是语言）。空集。空集 和由空字符串组成的集合和由空字符串组成的集合 都是语言。都是语言。2.2 文法和语言文文法法是是程程序序语语言言的的生生成成系系统统，而而自自动动机机则则是是程程序序语语言言的的识识别别系系统统。用用文文法法可可以以精精确确地地定定义义一一个个语语言言，并并依依据据该该文文法法构构造造出出识识别别这这个个语语言言的的自自动动机机。因因此此，文文法法对对程程
7、序序语语言言和和编编译译程程序序的的构构造造具具有有重重要要意意义义，如如程程序序语语言言的的词词法法可可用用正正规规文文法法描描述述，语语法法可可用用上上下下文文无无关关文文法法描描述，而语义则要借助于上下文有关文法描述。述，而语义则要借助于上下文有关文法描述。基本概念基本概念n定义定义 文法文法文法表示成四元组文法表示成四元组G=(VT,VN,S,P)，其中：，其中：(1)VT为为终终结结符符号号(terminal)集集，是是一一个个非非空空有有限限集集，它的每个元素称为终结符号；它的每个元素称为终结符号；(2)VN为为非非终终结结符符(non-terminal)集集，也也是是一一个个非非
8、空空有有限集，其每个元素称为非终结符号。限集，其每个元素称为非终结符号。要求要求VT VN=；(3)S为为一一文文法法开开始始符符号号，也也称称作作识识别别符符号号，是是一一个个特特殊的非终结符号，即殊的非终结符号，即S VN；(4)P是是产产生生式式的的非非空空有有限限集集，其其中中每每个个产产生生式式(或称规则或称规则)是一序偶是一序偶(,)，通常写作，通常写作读读作作“是是”或或“定定义义为为”。在在此此，为为产产生生式式的的左左部部，而而 为为产产生生式式的的右右部部，、是是由由终终 结结 符符 和和 非非 终终 结结 符符 组组 成成 的的 符符 号号 串串，(VT VN)+且且 至
9、至 少少 有有 一一 个个 非非 终终 结结 符符，而而(VT VN)*。终终结结符符和和非非终终结结符符的的集集合合用用符符号号V表表示示，即即V=VT VN。终结符代表了语法的最小元素。终结符代表了语法的最小元素。非终结符号也称语法变量，它代表语法实体或非终结符号也称语法变量，它代表语法实体或语法范畴；非终结符代表一个一定的语法概念，语法范畴；非终结符代表一个一定的语法概念，因此，一个非终结符是一个类、一个集合。因此，一个非终结符是一个类、一个集合。例如，在程序语言中，可以把变量、常数、例如，在程序语言中，可以把变量、常数、“+”、“*”等看作是终结符，而像等看作是终结符，而像“算术表算术
10、表达式达式”这个非终结符则代表着一定算术表达式这个非终结符则代表着一定算术表达式组成的类，如组成的类，如i*(i+i)、i+i+i等；也即每个非终等；也即每个非终结符代表着由一些终结符和非终结符且满足一结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。定规则的符号串组成的集合。产产生生式式是是定定义义语语法法实实体体的的一一种种书书写写规规则则。一一个个语法实体的相关规则可能不止一个。语法实体的相关规则可能不止一个。P1，P2，Pn可可将将这这些些有有相相同同左左部部的的产产生生式式合合并并为为一一个个，即即缩写成缩写成P1 2 n其其中中，每每个个 i(i=1,2,n)称称为
11、为P的的一一个个候候选选式式，直直竖竖“”读读为为“或或”，它它与与“”一一样样是是用用来来描描述述文文法法的的元元语语言言符符号号(即即不不属属于于 的的字符字符)。n例例2.1 文法文法G=(VN,VT,P,S)，其中，其中VN=S，VT=0,1，P=S0S1,S01。n例例2.2 文法文法G=(VN,VT,P,S)，其中，其中VN=,，VT=a,z,0,9，P=a|z0|9S=n习惯上只将产生式写出。并有如下约定：习惯上只将产生式写出。并有如下约定：n第一条产生式的左部是开始符号第一条产生式的左部是开始符号n用尖括号括起的是非终结符，否则为终结用尖括号括起的是非终结符，否则为终结符。或者
12、大写字母表示非终结符，小写字符。或者大写字母表示非终结符，小写字母表示终结符母表示终结符nG可写成可写成GS，其中，其中S是开始符号是开始符号n定义定义 直接推导直接推导&直接规约直接规约设设文文法法G=(VT,VN,S,P)且且、(VT VN)*，如如果果存存在在产产生生式式A(VT VN)*)，则则称称 A 可可直直接接推推导导出出，或或者者说说是是 A 的的直接推导直接推导，记做，记做 A其其中中“”表表示示直直接接推推导导出出，是是应应用用产产生生规规则则进进行行推推导导的的记记号号。反反过过来来，则则称称可可直直接接规规约约到到 A，或者说，或者说 A 是是的的直接规约直接规约。注意
13、注意“”与与“”不同，不同，“”是产生式中是产生式中的定义记号。直接推导是对文法符号串的定义记号。直接推导是对文法符号串 A 中中的非终结符的非终结符A用相应的产生式用相应的产生式A的右部的右部 来来替换，从而得到替换，从而得到。例如，对例例如，对例2.1和例和例2.2的文法的文法G，可以给出一，可以给出一些直接推导的例子：些直接推导的例子：0S10011,S0S1,0S100S11S0S1,S01a|z0|9n定义定义 推导推导&规约的传递闭包规约的传递闭包如如果果存存在在一一个个自自 1至至 n的的直直接接推推导导序序列列：123n(n1)，则则我我们们称称 1可可推推导导出出 n，或或称
14、称 n规规约约到到 1，记记为为 1+n，它它表示从表示从 1出发经过一步或若干步可推导出出发经过一步或若干步可推导出 n。n定义定义 推导推导&规约的自反传递闭包规约的自反传递闭包如如果果有有 1+n或或 1=n，则则记记 1*n，表表示示从从 1出发，经过出发，经过0步或若干步可推导出步或若干步可推导出 n。例如，例如，对对例例2.1的的文文法法，0S100+001100，当当然然也可以是也可以是0S100*001100。对对2.2的的文文法法，+x1，当当然然也也可以是可以是*x1。S0S1,S01a|z0|9n定义定义 句型句型&句子句子设设GS是一文法，是一文法，S是它的开始符号，如
15、果是它的开始符号，如果S*，(VT VN)*，则称，则称 是文法是文法GS的一的一个句型；如果个句型；如果VT*，则称，则称 是文法是文法GS的一的一个句子。个句子。例如，例如，S，0S1，000111都是例都是例2.1的文法的文法G的句的句型，其中型，其中000111是是G的句子。的句子。，a1等都是例等都是例2.2的文法的文法G的的句型，其中句型，其中a1是是G的句子。的句子。S0S1,S01a|z0|9n 定义定义 文法的语言文法的语言文文法法GS产产生生的的句句子子的的全全体体称称为为由由文文法法GS产产生生的的语语言言，记记为为L(G)，即即有有L(G)=S*且且VT*。例例如如，例
16、例2.1的的文文法法产产生生的的语语言言的的句句子子具具有有0n1n的形式。的形式。n定义定义 文法等价文法等价若若L(G1)=L(G2)，则称文法，则称文法G1和和G2是等价的。是等价的。例例如如，文文法法GA:A0R，A01，RA1。和和例例2.1的文法等价。的文法等价。S0S1,S012.1.2 Chomsky谱系谱系语言学家语言学家Noam Chomsky于于1956年首先建立了年首先建立了形式语言的描述，定义了四类文法及相应的形形式语言的描述，定义了四类文法及相应的形式语言，并分别与相应的识别系统相联系，它式语言，并分别与相应的识别系统相联系，它对程序语言的设计、编译方法、计算复杂性
17、等对程序语言的设计、编译方法、计算复杂性等方面都产生了重大影响。方面都产生了重大影响。Chomsky把把文文法法分分成成四四种种类类型型，即即0型型、1型型、2型型和和3型型。这这几几类类文文法法的的差差别别在在于于对对产产生生式式施施加不同的限制。加不同的限制。n0型文法与型文法与0型语言型语言(对应图灵机对应图灵机)如果文法如果文法G的每一个产生式具有下列形式：的每一个产生式具有下列形式：其其中中，V*VNV*，即即 至至少少含含有有一一个个非非终终结结符符；V*；则则称称文文法法G为为0型型文文法法或或短短语语结结构构文文法法，记记为为PSG(Phrase Structure Gramm
18、ar)。0型型文文法法相相应应的的语语言言称称为为0型型语语言言或或称称递递归归可可枚枚举集，它的识别系统是图灵举集，它的识别系统是图灵(Turing)机。机。n1型文法与型文法与1型语言型语言(对应线性界限自动机对应线性界限自动机)文法文法G的产生式的产生式在在0型型文文法法的的基基础础上上增增加加了了字字符符长长度度上上满满足足|的的限限制制，则则称称文文法法G为为1型型文文法法或或上上下下文文有有关关文文法法，记记为为CSG(Context-Sensitive Grammar)。1型型文文法法相相应应的的语语言言称称为为1型型语语言言或或上上下下文文有有关关语语言言，它它的的识识别别系系
19、统统是是线线性性界界限限自动机。自动机。1型型文文法法的的另另一一种种定定义义方方法法是是文文法法G的的每每一一个个产生式具有下列形式：产生式具有下列形式：A其中，其中，AV*，A VN，V+；显然它满足；显然它满足前述定义的长度限制，但它更明确地表达了上前述定义的长度限制，但它更明确地表达了上下文有关的特性，即下文有关的特性，即A必须在必须在、的上下文环的上下文环境中才能被境中才能被 所替换。所替换。自然语言的语法应属于上下文有关文法。自然语言的语法应属于上下文有关文法。n2型文法与型文法与2型语言型语言(对应下推自动机对应下推自动机)文法文法G的每一个产生式具有下列形式：的每一个产生式具有
20、下列形式：A其其中中，A VN，V*，则则称称文文法法G为为2型型文文法法或或上上下下文文无无关关文文法法，记记为为CFG(Context-Free Grammar)。2型型文文法法相相应应的的语语言言称称为为2型型语语言言或或上上下下文文无无关关语语言言，它它的的识识别别系系统统是是下下推推自自动动机。机。程序设计语言的语法是上下文无关的。程序设计语言的语法是上下文无关的。n3型文法与型文法与3型语言型语言(对应有限自动机对应有限自动机)文法文法G的每个产生式具有下列形式：的每个产生式具有下列形式：A或或AB其中，其中，A、B VN，VT*，则文法，则文法G称为右称为右线性文法。若每个产生式
21、具有下列形式：线性文法。若每个产生式具有下列形式：A或或AB 则则文文法法G称称为为左左线线性性文文法法。右右线线性性和和左左线线性性文文法法都都称称为为3型型文文法法、正正规规文文法法，记记为为RG(Regular Grammar)。3型型文文法法相相应应的的语语言言为为3型型语语言言或或正正规规语语言言，它它的的识识别别系系统统是是有有限限自自动动机。机。n例例2.1和例和例2.2中的文法都是上下文无关的。中的文法都是上下文无关的。n例例2.3 设设G=(VN,VT,P,S)，VN=S,B,E，VT=a,b,e，P=SaSBE,SaBE,EBBE,aBab,bBbb,bEbe,eEee文法
22、文法G是上下文有关的，是上下文有关的，L(G)=anbnen|n 1S0S1,S01a|z0|9S aSBE (SaSBE)aaBEBE(SaBE)aabEBE(aBab)aabBEE(EBBE)aabbEE(bBbb)aabbeE(bEbe)aabbee(eEee)S aSBEaaSBEBEaaaBEBEBEn四类文法的联系与区别四类文法的联系与区别n联联系系：从从0型型文文法法到到3型型文文法法逐逐渐渐增增加加限限制制。13型型文文法法都都属属于于0型型文文法法，2、3型型文文法法均均属属于于1型型文文法法，3型文法属于型文法属于2型文法。型文法。n区区别别：(1)1型型文文法法中中不不允
23、允许许有有形形如如“A”的的产产生生式式存存在在，而而2、3型型文文法法则则允允许许形形如如“A”的的产产生生式式存存在在；(2)0、1型型文文法法的的产产生生式式左左部部存存在在含含有有终终结结符符号号的的符符号号串串或或两两个个以以上上的的非非终终结结符符，而而2型型和和3型型文文法法的的产产生生式式左左部部只只允允许许是是单单个个的的非非终终结结符号。符号。n文法的应用文法的应用n在在编编译译方方法法中中，通通常常用用3型型文文法法来来描描述述高高级级程程序序语语言言的的词词法法部部分分，然然后后用用有有限限自自动动机机FA来来识识别别高高级级语语言言的的单单词词；利利用用2型型文文法法
24、来来描描述述高高级级语语言言的的语语法法部部分分，然然后后用用下下推推自自动动机机PDA(Push-Down Automata)来来识识别别高高级语言的各种语法成分。级语言的各种语法成分。n贯穿词法分析和语法分析始终如一的思想贯穿词法分析和语法分析始终如一的思想是：语言的描述和语言的识别是表示一个是：语言的描述和语言的识别是表示一个语言的两个不同的侧面，二者缺一不可。语言的两个不同的侧面，二者缺一不可。用正规文法和上下文无关文法描述语言时用正规文法和上下文无关文法描述语言时的识别方法的识别方法(即自动机即自动机)不同。通常，正规不同。通常，正规文法适合于描述线性结构，如标识符、关文法适合于描述
25、线性结构，如标识符、关键字和注释等；而上下文无关文法则适合键字和注释等；而上下文无关文法则适合于描述具有嵌套于描述具有嵌套(层次层次)性质的非线性结构，性质的非线性结构，如不同结构的语句如不同结构的语句if-else、while等。等。2.2 推导与分析(语法)树上下文无关文法有足够的能力描述现今程上下文无关文法有足够的能力描述现今程序设计语言的语法结构，比如描述算术表达式序设计语言的语法结构，比如描述算术表达式和各种语句等。和各种语句等。n例例2.6 文法文法GE：EE+E E*E(E)i非非终终结结符符E表表示示一一类类算算术术表表达达式式。i表表示示程程序序设设计计语语言言中中的的变变量
26、量，该该文文法法定定义义了了由由变变量量、+、*、(和和)组成的算术表达式的语法结构。组成的算术表达式的语法结构。n分析树分析树对程序语言来说，有两个问题需要解决：对程序语言来说，有两个问题需要解决：其一是判别程序在语法上是否正确；其二是句其一是判别程序在语法上是否正确；其二是句子的识别或分析。在编译方法中，为了便于识子的识别或分析。在编译方法中，为了便于识别或分析句子而引入了分析树这一重要的辅助别或分析句子而引入了分析树这一重要的辅助工具。分析树以图示化的形式把句子分解成各工具。分析树以图示化的形式把句子分解成各个组成部分来描述或分析句子的语法结构，这个组成部分来描述或分析句子的语法结构，这
27、种图示化的表示与所定义的文法规则完全一致，种图示化的表示与所定义的文法规则完全一致，但更为直观和完整。但更为直观和完整。对对文文法法G=(VT,VN,S,P)，满满足足下下列列条条件件的的树树称为称为GS的句型的分析树：的句型的分析树：(1)结点用结点用GS的一个终结符或非终结符标记；的一个终结符或非终结符标记；(2)根结点用文法开始符根结点用文法开始符S标记；标记；(3)内内部部结结点点(指指非非叶叶结结点点)一一定定是是非非终终结结符符，如如果果某某内内部部结结点点A有有n个个分分支支，它它的的所所有有子子结结点点从从左左至至右右依依次次标标记记为为x1、x2、xn，则则Ax1x2xn一定
28、是文法一定是文法GS的一条产生式；的一条产生式；(4)如如果果某某结结点点标标记记为为，则则它它必必为为叶叶结结点点且且是是其父结点的唯一子结点。其父结点的唯一子结点。n例例2.7 例例2.6的文法的一棵分析树的文法的一棵分析树句子句子i+i*i的分析树的分析树EE+EE*E(E)in在一棵分析树生长过程中的任何时刻，所有那在一棵分析树生长过程中的任何时刻，所有那些没有后代的树叶结点自左至右排列起来就是些没有后代的树叶结点自左至右排列起来就是一个句型。一个句型。n分析树表示了在推导过程中施用了哪个产生式分析树表示了在推导过程中施用了哪个产生式和施用在哪个非终结符上，它并没有表明施用和施用在哪个
29、非终结符上，它并没有表明施用产生式的顺序。产生式的顺序。n例如，上面的分析树表示的句子例如，上面的分析树表示的句子i+i*i可以有不可以有不同的推导过程：同的推导过程：EE+Ei+Ei+E*Ei+i*Ei+i*iEE+EE+E*EE+E*iE+i*ii+i*in最左（最右）推导最左（最右）推导推导序列中的每一步推导都是对句型中的最左推导序列中的每一步推导都是对句型中的最左（最右）非终结符用相应产生式的右部进行替（最右）非终结符用相应产生式的右部进行替换，这样的推导称为换，这样的推导称为最左（最右）推导最左（最右）推导。最右。最右推导常被称为推导常被称为规范推导规范推导。由规范推导所得的句。由规
30、范推导所得的句型称为型称为规范句型规范句型。规范推导的逆过程便是。规范推导的逆过程便是规范规范规约规约。例如，前面的第一个推导就是最左推导，而第例如，前面的第一个推导就是最左推导，而第二个推导就是最右推导。二个推导就是最右推导。因此，一棵语法树表示了一个句型种种因此，一棵语法树表示了一个句型种种可能的不同推导过程，包括最左可能的不同推导过程，包括最左(最右最右)推导。如果我们坚持使用最左推导。如果我们坚持使用最左(或最右或最右)推导，那么一棵语法树就完全等价于一推导，那么一棵语法树就完全等价于一个最左个最左(或最右或最右)推导，这种等价性也包推导，这种等价性也包括语法树的每一步生长和推导的每一
31、步括语法树的每一步生长和推导的每一步展开的这种完全一致性。展开的这种完全一致性。n介词短语附着歧义介词短语附着歧义nHe saw a boy with a telescope.n他通过望远镜看到一个男孩。他通过望远镜看到一个男孩。n他看到一个带望远镜的男孩。他看到一个带望远镜的男孩。n文法的二义性文法的二义性一个句型是否只对应唯一的一棵语法树呢？一一个句型是否只对应唯一的一棵语法树呢？一个句型是否只有唯一的一个最左（最右）推导个句型是否只有唯一的一个最左（最右）推导呢？非也。呢？非也。n例如，例例如，例2.6的文法的文法G的句子的句子i+i*i就有两个不同就有两个不同的最左推导：的最左推导：E
32、E+Ei+Ei+E*Ei+i*Ei+i*iEE*EE+E*Ei+E*Ei+i*Ei+i*i对应有两棵不同的语法树：对应有两棵不同的语法树：EEEiEE+*iiEEEiEE*+ii文法文法GS的一个句子如果能找到两个不同的一个句子如果能找到两个不同的最左推导的最左推导(或最右推导或最右推导)，或者存在两棵不同，或者存在两棵不同的语法树，则称这个句子是二义性的。一个文的语法树，则称这个句子是二义性的。一个文法如果包含二义性的句子，则这个文法是二义法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。文法，否则是无二义文法。再如，条件语句的文法再如，条件语句的文法GS为：为：GS:Sif
33、B S Sif B S else S SA /*A指其它语句指其它语句*/其中，其中，VN=B,S,A，VT=if,else。句型句型if B if B S else S所对应的两棵不同语法树：所对应的两棵不同语法树：因此，文法因此，文法GS是二义性文法。是二义性文法。SifS(a)(b)BSifSelseBSBSifSelseifSBn注意注意：一个文法是二义性的，并不说明：一个文法是二义性的，并不说明该文法所描述的语言也是二义性的。也该文法所描述的语言也是二义性的。也即，对于一个二义性文法即，对于一个二义性文法GS，如果能，如果能找到一个非二义性文法找到一个非二义性文法GS，使得，使得L(
34、G)=L(G)，则该二义性文法的二义性，则该二义性文法的二义性是可以消除的。如果找不到这样的是可以消除的。如果找不到这样的GS，则二义性文法描述的语言为先天二义，则二义性文法描述的语言为先天二义性的。性的。n文法二义性消除的方法文法二义性消除的方法n不改变文法中原有的语法规则，仅加进一些语法不改变文法中原有的语法规则，仅加进一些语法的非形式规定。的非形式规定。如对例子如对例子2.6的文法，不改变已有的四条规则，仅的文法，不改变已有的四条规则，仅加进运算符的优先顺序和结合规则，即加进运算符的优先顺序和结合规则，即*优先于优先于+，且，且*、+都服从左结合。都服从左结合。n构造一个等价的无二义性文
35、法，即把排除二义性构造一个等价的无二义性文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。的规则合并到原有文法中，改写原有的文法。例例2.8 可以将例可以将例2.6的文法改写为无二义性的文法的文法改写为无二义性的文法GE如下：如下：EE+T TTT*F FF(E)iEE+EE*E(E)in注：注：n1）二义性会给语法分析带来不确定性。）二义性会给语法分析带来不确定性。n2）文法的二义性是不可判定的，即不存在算法，）文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义能够在有限步数内确切判定一个文法是否为二义文法。文法。n3）若要证明是二义性，只要举出一例
36、，即给出文）若要证明是二义性，只要举出一例，即给出文法的某个句子有两个不同的最左（最右）推导，法的某个句子有两个不同的最左（最右）推导，或两棵不同的语法树。或两棵不同的语法树。n4）若能控制文法的二义性，即加入人为的附加条）若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。件，则二义文法的存在并非坏事。n自顶向下的语法分析自顶向下的语法分析n例：文法例：文法G：ScAd Aab Aa识别输入串识别输入串 w=cabd是否该文法的句子是否该文法的句子推导过程：推导过程：S cAd cabdSScAdaScAdbn自底向上的语法分析自底向上的语法分析规约过程：规约过程：S cA
37、d cabdcab dcab dAcab dASn句法分析的有关问题句法分析的有关问题n1）如何选择使用哪个产生式进行推导？）如何选择使用哪个产生式进行推导？n假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是V，且有，且有n条规条规则：则：VA1|A2|An，那么如何确定用哪个右部去，那么如何确定用哪个右部去替代替代V？n2）如何识别可归约串？）如何识别可归约串？n在自底向上的分析方法中，在分析程序工作的每在自底向上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为到某个非终结符号，该子串
38、称为“可归约串可归约串”素短语和句柄。素短语和句柄。n短语短语n设设是文法是文法GS的一个句型，如果有：的一个句型，如果有：S*A 且且A+则称则称 是句型是句型关于非终结符关于非终结符A的一个的一个短语短语，或，或称称 是是的一个的一个短语短语。特别是有。特别是有A 产生式时，产生式时，称称 为句型为句型的一个的一个直接短语直接短语或或简单短语简单短语。n一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句柄句柄。注意，一个句型的直接短语可能不只一个，但最注意，一个句型的直接短语可能不只一个，但最左直接短语则是唯一的。左直接短语则是唯一的。n含有终结符的短语，如果它不存在也
39、具有同样性含有终结符的短语，如果它不存在也具有同样性质的真子串，则该短语为质的真子串，则该短语为素短语素短语。n子树和短语子树和短语n只含有单层分枝的子树称为只含有单层分枝的子树称为简单子树简单子树。n(1)短语：子树的叶子结点组成的符号串是相对短语：子树的叶子结点组成的符号串是相对于子树根的短语；于子树根的短语；n(2)直接短语：简单子树的叶子结点组成的符号直接短语：简单子树的叶子结点组成的符号串是相对于简单子树根的直接短语；串是相对于简单子树根的直接短语；n(3)句柄：最左简单子树的叶子结点组成的符号句柄：最左简单子树的叶子结点组成的符号串为句柄；串为句柄；n(4)素短语：子树的叶子结点组成的符号串含终素短语：子树的叶子结点组成的符号串含终结符，且在该子树中不再有包含有终结符的更小结符，且在该子树中不再有包含有终结符的更小子树。子树。n例例2.9 例例2.8的文法的句子的文法的句子i1+i2*i3n短语：短语：i1+i2*i3，i1，i2*i3，i2，i3n直接短语：直接短语：i1，i2，i3n句柄：句柄：i1n素短语：素短语：i1，i2，i3EE+TTTT*FFF(E)i