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

※上节课主要内容回顾:,I->ℓAA->ℓA|dA|。②标识符文法:G(I)::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章形式语言基础(续)…:推导,归约。星推导():αβⅠ.直接推导(=>):xAy=>xy加推导算符加推导():β设x,y∈(VN+VT)*,A->∈P=>*=>*(当且仅当=>1=>2=>…=>β)(当且仅当=β或=>1=>2=>…β)直接推导算符星推导算符=>+=>+即:指一步或一步以上的直接推导运算。即:指零步或零步以上的直接推导运算。即:指用产生式的右部符号串替换左部非终结符。※实用中最常见的两种运算:=>.+=>.+加归约():βⅡ.直接归约():xyxAy=>.=>.(当且仅当12…β)=>.=>.=>.=>.星归约():β=>.*=>.*(当且仅当=β或12…β)=>.=>.=>.=>.=>+ℓ=>.+ℓ即:直接归约是直接推导的逆运算,用产生式的左部符号串替换右部非终结符。即:指零步或零步以上的直接归约运算。即:指一步或一步以上的直接归约运算。直接归约算符加归约算符星归约算符这是相应的算符最左推导()—最左归约()—每次推导皆最左非终结符优先;每次归约皆最左可归约串优先。(Z),L(G)为G所定义的语言;则有:一个文法所定义的语言,就是由该文法开始符号推导出的所有仅含终结符的符号串之集合。其中的每个符号串皆称为句子。L(G)={x|Zx,x∈VT*}=>+〖〗?G(N):N->dN|d【】无符号整数文法: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【】已知文法:=>.=>.=>.=>.=>.=>.=>.=>.最左归约(从符号串出发)过程: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=>.+(从开始符号出发)过程:最左非终结符最左可归约串按指定的运算法则,证明符号串i+i*i是算数表达式:得:I=ℓ(ℓ|d)n,n≥0令:I=ℓA【】用标识符文法求解标识符集合: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|※该文法所定义的语言,可通过构造正规方程式解之:(属正规文法类)由文法开始符号加推导出的任一符号串。-由开始符号加推导出的任一终结符号串。-设有文法G(Z)=(VN,VT,Z,P),则:-句型(句子)生成规则的一种树结构表示;树根--开始符号;树叶—给定的句型(句子)。形式化:形式化:若有,则是句型;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※句型、句子和语法树示例:【】算术表达式文法:⑴证明(T/F+F)*i是一个句型(表达式型);⑵画出该句型的语法树。E->T|E+T|E-TT->F|T*F|T/FF->i|(E)【解1】即:E(T/F+F)*i=>+证闭