第2章 语言分析基础(3)

1第二章语言分析基础2语言分析基础文法和语言概述字母表和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的说明3形式语言(Chomsky)：通过抽象，对语言进行形式化描述，用一组数学符号和规则来描述的语言称为形式语言。*的任何子集称作上的形式语言。L（G[S]）={α|α∈VT*,Sα}+由文法定义语言：2.4文法的类型文法G[S]=（VN，VT，P，S）VN：有穷非空的非终结符号集VT：有穷非空的终结符号集，且VN∩VT=ΦP：有穷非空产生式或规则的集合S：开始符号（识别符号）S∈VN，S至少要在一条规则中作为左部出现。4Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：–0型文法0型语言或短语结构语言–1型文法1型语言或上下文有关语言–2型文法2型语言或上下文无关语言–3型文法3型语言或正则(正规)语言2.4文法的类型50型语言：L00型文法称为无约束短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。0型文法，P：α::=β，其中：α∈V*且至少含有一个非终结符，β∈V*。2.4文法的类型60型文法，G[S]:S→ABS|ABAB→BAA→0B→1L(G[S])={x|x是由n个01或10组成的二进制数字串，n≥1}该文法产生的语言为2.4文法的类型7S→ACaBCa→aaCCB→DBaB→BaCB→EaD→DaAD→ACaE→EaAE→ε例：0型文法G[S]：2.4文法的类型81型文法，P：αAβ::=αγβ，其中A∈VN，α，β∈V*，γ∈V＋。1型语言：L1称为上下文敏感或上下文有关文法。也即只有在α、β这样的上下文中才能把A改写为γ。2.4文法的类型9S→aSBES→aBEBE→bEaB→abbB→bbbE→beeE→ee例：1型（上下文有关）文法[S]：2.4文法的类型102型文法，P：A::=β，其中A∈VN，β∈V*2型语言：L2称为上下文无关文法。也即把A改写为β时，不必考虑上下文。2.4文法的类型11例：2型（上下文无关）文法文法G[S]：S→ABA→BS|0B→SA|1S→ε2.4文法的类型12（右线性）P：A::=a或A::=aB其中A、B∈VNa∈VT3型语言：L3，又称正则语言。3型文法称为正则文法。它是对2型文法进行进一步限制。左线性和右线性文法是相互等价的（左线性）P：A::=a或A::=Ba其中A、B∈VNa∈VT3型文法：2.4文法的类型13G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|0G[I]：I→lTI→lT→lTT→dTT→lT→d例：3型文法2.4文法的类型140型文法可以产生L0、L1、L2、L3，但1型文法只能产生L1、L2、L3，不能产生L0，以此类推。L0L1L2L32型文法1型文法0型文法3型文法四种文法的关系2.4文法的类型152型文法（不确定的下推自动机）1型文法（不确定的界限自动机）0型文法（图灵机）3型文法（有限自动机）形式语言与自动机2.4文法的类型16(2)①S→aSBC②S→aBC③CB→DB④DB→DC⑤DC→BC⑥aB→ab⑦bB→bb⑧bC→bc(1)①S→ACaB②Ca→aaC③CB→DB④CB→E⑤aD→Da⑥AD→AC⑦aE→Ea⑧AE→ε⑨cC→cc(3)①S→Ac②S→Sc③A→ab④A→aAb⑤B→cB⑥B→c(4)①S→aS②S→aA③A→bA④A→bB试判断下列产生式集所对应的文法类型和产生的语言类型：2.4文法的类型0型文法1型文法2型文法3型文法17自然语言是上下文有关的。上下文无关文法有足够的能力描述现今程序设计语言的语法结构:算术表达式语句–赋值语句–条件语句–读语句–……基于正则文法讨论词法分析问题，基于上下文无关文法讨论语法分析问题。2.4文法的类型18算术表达式的上下文无关文法表示：文法G=({E},{+,*,i,(,)},P,E}P:E→iE→E+EE→E*EE→(E)条件语句的上下文无关文法表示：条件语句→if条件then语句|if条件then语句else语句2.4文法的类型192.5上下文无关文法及其语法树规范推导语法树文法的二义性20最左（最右）推导–在推导的任何一步αβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换。规范推导：即最右推导。规范句型：由规范推导所得的句型。1.规范推导2.5上下文无关文法及其语法树21最左、最右推导示例：表达式i+i*i的生成过程可表示为如下的：文法G[E]如下：E→E+EE→E*EE→(E)E→i每句子一定都存在规范推导。不是每个句型都一定存在规范推导。2.5上下文无关文法及其语法树最右推导过程：E=E+E=E+E*E=E+E*i=E+i*i=i+i*i最左推导过程：E=E+E=i+E=i+E*E=i+i*E=i+i*i例：i+i*E？22对文法G[S]=(VT,VN,S,P)，满足下列条件的树称为G[S]的语法树：(1)结点：终结符或非终结符；(2)根结点：文法开始符S；(3)内部结点(指非树叶结点)：非终结符如果某内部结点A有n个儿子，它的所有子结点从左至右依次标记为x1、x2、…、xn，则A→x1x2…xn一定是文法G[S]的一条产生式。2.语法树语法树的结果：从左到右读出叶子的标记而构成。2.5上下文无关文法及其语法树24语法树的构造过程：（1）从开始符号出发，向下画一个分枝，表示第一个直接推导；（2）从非终结符号往下画分枝，表示即将进行的直接推导；（3）重复步骤（2）直到全部推导都在树上表示出来。2.5上下文无关文法及其语法树27文法G[S]：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→dbbAdSaceABSaAcBeaAcdeaAbcdeabbcde（1）（4）（3）（2）语法树只表示推导的结果，不表示推导的过程。或者：表示了所有可能的推导(二义性文法除外)。2.5上下文无关文法及其语法树语法树构造示例28语法树只表示推导的结果，不表示推导的过程，或者说表示了一个句型的种种可能的推导(二义性文法除外)。【注意】语法树和推导之间的对应关系为：每一棵语法树至少存在一个推导与之对应，每一个推导都存在一棵语法树。【问题】（1）一个句型是否只对应唯一的一棵语法树？（2）一个句型是否只有唯一的一个最左（最右）推导？语法树和推导2.5上下文无关文法及其语法树29句子的二义性–文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。文法的二义性–一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。这里的二义性是指语法结构上的。3.文法二义性2.5上下文无关文法及其语法树二义语言-如果一个语言没有任何无二义的文法来描述，则这个语言是二义的---先天二义性语言。L={aibjck|i=j或j=k，i、j、k≥1}301、文法的二义性和语言的二义性是不同的概念。如果一个文法是二义性的，并不能说明其描述的语言也是二义性的。但如果语言是二义性的，则描述它的任何文法一定都是二义性的。2、只要不是二义语言，总可以找到无二义的文法来描述它。3、要进行确定的语法语义分析，要求文法必须是无二义的。2.5上下文无关文法及其语法树31练习：给出i+i*i的两种推导，并画出语法树。ｉＥ＋ｉＥＥ＊ｉＥＥiＥ＋iＥ＊iＥＥＥ最左推导过程（2）：E=E*E=E+E*E=i+E*E=i+i*E=i+i*i最左推导过程(1)：E=E+E=i+E=i+E*E=i+i*E=i+i*i2.5上下文无关文法及其语法树文法G[E]如下：E→E+EE→E*EE→(E)E→i32二义性的不确定性–二义性会给语法分析带来不确定性。如果一个句子具有二义性，那么对这个句子的结构可能有多种‘正确’的解释。所以，二义性一般是有害的。文法的二义性是不可判定的–即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法。–若要证明是二义性，只要举出一例。若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。2.5上下文无关文法及其语法树33文法二义性消除(1)不改变文法中原有的语法规则，仅加进一些语法的非形式规定。(2)构造一个等价的无二义性文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。2.5上下文无关文法及其语法树34文法二义性消除示例【例】对文法G[E]，不改变已有的四条规则，仅加进运算符的优先顺序和结合规则，即：（1）*优先于+（2）*、+都服从左结合这样，对文法G[E]中的句子i+i*i就只有如右图所示的惟一一棵语法树。iＥ＋iＥ＊iＥＥＥ2.5上下文无关文法及其语法树文法G[E]如下：E→E+EE→E*EE→(E)E→i35E＋ETFTFiiTFi*句子i+i*i的语法树2.5上下文无关文法及其语法树文法二义性消除示例【例】将文法G[E]改写为无二义性的文法如下：G'[E]:E→E+T∣TT→T*F∣FF→(E)∣i此时，句子i+i*i就只有如右图所示的惟一一棵语法树。36解：∵存在二义句子i∨i∧i。∴是二义文法。文法没有规定∧、∨、的优先级和结合性。按惯例规定∧、∨、的优先级和结合性，改写文法为无二义的文法：S→S∨A|AA→A∧B|BB→S|(S)|i判断文法：S→S∧S|S∨S|S|i是否二义文法？如果是，为它写一个等价的无二义文法。课堂练习37证明文法：S→SaS|ε为二义文法，并将其改写为无二义的文法。证明：∵存在句子aa对应两棵语法树∴该文法是二义文法。该文法产生的语言是若干个a(可以是0个)构成的符号串的集合。可以改写为无二义的文法:S→aS|εSSaSSaSεεεSSaSSaSεεε课堂练习38考虑以下的两个语言，给出其文法，并证明它们都是上下文无关的。L1={anb2ncm|n,m=0}L2={anbmc2m|n,m=0}L1:S→ABA→ε|aAbbB→ε|cBL2:S→ABA→ε|aAB→ε|bBcc课堂练习39作业2、试判断下述文法是否具有二义性：Ei（E）EAEA+-*/3、把下面的文法改写为无二义性的文法：SSS（S）（）教科书第39页：2、3、51、证明文法G=({E,O},{(,),+,*,v,d},P,E)是二义的，P:{E→EOE|(E)|v|d,O→+|*}