第二章 形式语言基础(2)

※上节课主要内容回顾：2.文法是定义语言规则集合，I-ℓAA-ℓA|dA|1.形式语言是符号串集合。②标识符文法：G(I):3.简单语言的文法构造：G(N):N-dN|d③算术表达式文法：G(E):E-T|E+T|E-TT-F|T*F|T/FF-i|(E)字母表；规则集。①无符号整数文法：四元组：G(Z)=(VN,VT,Z,P)【内容提要】第2章形式语言基础（续）2.1语言是符号串集合2.2文法是定义语言的规则集2.3怎样用文法定义语言2.4主要语法成分的定义与求解…2.2.2文法的基本运算文法有两种基本运算：推导，归约。星推导():αβⅠ．直接推导(=):xAy=xy加推导算符加推导():β设x,y∈(VN+VT)*，A-∈P=*=*（当且仅当=1=2=…=β）（当且仅当=β或=1=2=…β)直接推导算符星推导算符=+=+即：指一步或一步以上的直接推导运算。即：指零步或零步以上的直接推导运算。即：指用产生式的右部符号串替换左部非终结符。※实用中最常见的两种运算：=.+=.+加归约():βⅡ．直接归约():xyxAy=.=.（当且仅当12…β）=.=.=.=.星归约()：β=.*=.*（当且仅当=β或12…β)=.=.=.=.=+ℓ=.+ℓ即：直接归约是直接推导的逆运算，用产生式的左部符号串替换右部非终结符。即：指零步或零步以上的直接归约运算。即：指一步或一步以上的直接归约运算。直接归约算符加归约算符星归约算符这是相应的算符•最左推导()—•最左归约()—每次推导皆最左非终结符优先；每次归约皆最左可归约串优先。2.3怎样用文法定义语言设有文法G(Z),L(G)为G所定义的语言；则有：一个文法所定义的语言，就是由该文法开始符号推导出的所有仅含终结符的符号串之集合。其中的每个符号串皆称为句子。L(G)={x|Zx,x∈VT*}=+〖2.1〗2.3.1什么是一个文法所定义的语言？G(N):N-dN|d【例2.11】无符号整数文法：Z=〉dN=ddN=…=dn,n≥1=+∴zdn,n≥0即：L(G)={dn|n≥1}∵通过文法运算，可以求解该文法所定义的语言及其各种语言成分。i+i*iT-F|T*F|T/FF-i|(E)G(E):E-T|E+T|E-T【例2.12】已知文法：=.=.=.=.=.=.=.=.2.最左归约(从符号串出发)过程：E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i∴E=+ℓi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE∴i*i+i=.+ℓE1.最左推导(从开始符号出发)过程：最左非终结符最左可归约串按指定的运算法则，证明符号串i+i*i是算数表达式：得：I=ℓ(ℓ|d)n,n≥0令：I=ℓA【例2.13】用标识符文法求解标识符集合：I-ℓAA-ℓA|dA|※迭代求解法：①先求解A:A=(ℓ|d)A,A=(ℓ|d)2A,…,A=(ℓ|d)nA代入A=得：A=(ℓ|d)n,n≥0②∵I=ℓA；代入A=(ℓ|d)n,n≥0正规方程式《标识符》：字母开头的字母、数字序列；A=（ℓ|d）A|※该文法所定义的语言，可通过构造正规方程式解之：(属正规文法类)由文法开始符号加推导出的任一符号串。2.4主要语法成分的定义与求解2.句子-由开始符号加推导出的任一终结符号串。1.句型-设有文法G(Z)=(VN,VT,Z,P)，则：3.语法树-句型(句子)生成规则的一种树结构表示；树根--开始符号；树叶—给定的句型(句子)。形式化：形式化：若有，则是句型；Z=+若有且∈VT*，则是句子；Z=+Ⅰ.句型、句子和语法树AX1X2…Xn【语法树的构造算法】：③重复步骤②，直到再没有推导产生式为止。①置树根为开始符号；②若采用了推导产生式：A-x1x2…xn，则※如此构造的语法树，其全体树叶（自左至右）恰好是给定的句型。有子树：E=T=T*F=F*F=(E)*F=(E+T)*F=(T+T)*F=(T/F+T)*F=(T/F+F)*F=(T/F+F)*i※句型、句子和语法树示例：【例2.14】算术表达式文法：⑴证明(T/F+F)*i是一个句型(表达式型)；⑵画出该句型的语法树。E-T|E+T|E-TT-F|T*F|T/FF-i|(E)【解1】即：E(T/F+F)*i=+证闭句型(T/F+F)*i的语法树构造：ETT*FF(E)E+TTT/FFiE-T|E+T|E-TT-F|T*F|T/FF-i|(E)【注】语法树的子树：【解2】或称为直接子树仅具有单层分支的子树。以任何具有分支的结点为根所形成的树，称为原树的子树。子树：简单子树：TSp(他)(哥哥)(非常)(喜欢)图2.2‘他哥哥非常喜欢鸟’的语法树(鸟)句子名短动短代词名词动短名词副词动词…为短语的名称！【例2.15】一个中文句子中的短语识别：短语–简单短语–句柄--部分文法：Ⅱ.短语、简单短语和句柄Sp-NPVPNP-rn-nVP-Vpn-dv-v…NpVprdvnnVp他哥哥非常喜欢鸟句子,他哥哥名短；非常喜欢鸟动短,非常喜欢动短；他哥哥，非常喜欢；他哥哥（最左边的简单短语)Ⅱ.短语、简单短语和句柄2⒊句柄是一个句型的最左简单短语。※设文法G(Z),A∈VN，xy是一个句型，其语法树则称是句型xy关于A的短语(A是的名字)；1.短语是一个句型任一子树的树叶全体。⒉简单短语是一个句型任一简单子树的树叶全体。则称是句型xy关于A的简单短语(A是的名字)；=+=+若有ZxAyxy即即=+若有ZxAy=xyZxAyxy的语法树【例2.16】图2.3为一个算术表达式(型)的语法树：•句型：E+F-T/F*i•短语:E+F-T/F*i，E+F，F，T/F*i，T/F，i•简单短语:F，T/F，i•句柄:FEE-TE+TT*FFT/Fi图2.3E+F-T/F*i的语法树※一类典型的综合例题：【例2.17】G(S):S-aAcBe;A-Ab|b;B-d※给定符号串：aAbcde⑴证明=aAbcde是一个句型；⑵画出句型的语法树；⑶指出中的短语、简单短语和句柄。【题解】⑴S=aAcBe=aAbcBe=aAbcde⑵语法树如右图：⑶短语、简单短语和句柄:SaAcBeAbd•短语:aAbcde,Ab,d•简单短语:Ab,d•句柄：Ab习题：【习题2.5】解释下列词语：①句型；句子；语法树。②短语；简单短语；句柄。⑴证明=aAbcde是一个句型；⑵画出句型的语法树；⑶指出句型的短语、简单短语和句柄。【习题2.7】P133_1;【习题2.6】G(S):S-aAcBe;A-Ab|b;B-d谢谢收看！再见ET|E+T|E-TTF|T*F|T/FFi|(E)P:基本图形库=.+ℓ=+ℓA=.+=+=*,=+,=.*,=.+,=l*,=l+,=.l+，=.l*=ℓ=.ℓ