例：G[S]:S→AS-A,G2[SAA-S,A都有→ablc。都可推导出 a-b-c。间G1=?G2. G1:S=>S-A=>S-C=>S-A-C=>S-b-c=>A-b-c=>a-b-c G2 S=>A-S=>A-A-S=>A-A-A=>A-A-C=>A-b-c=>a-b-c=>a-A-S=>a-b-A= >a-b-c :文法等价，但语义不等价（顺序不同） 2.4.文法和语言的分类 1.0型文法，0型语言(Lo):u→v(u∈v,v∈v),u中至少有一个非 终结符可由图机接收。即0型文法只是要求元素都在V中即可，每 个式子可以随便写。 2.1型文法，1型语言(CSL)(L1):xUy→xuy,x、yeV,U∈ VN,u∈V,u≥U,可由空间线性界限图灵机接收。 例：G[S]:S→aSBE,S→aBE,EB-→BE,aB→ab,bB-→bb,bE→be,eF→ee GS:S→CD,C→aCA,C→bCB,AD→aD,BD→bD,Aa→bD,Ab→bA Ba→aB,Bb-bB,C-E,D→E 3.2型文法（上下文无关文法）2型语言(CFL):U→u,U∈V,u∈ V常见形式。由不确定的下推自动机接收 例：G[S]:S→aBbA,A→alaSbAA,B→b|bSaBB GS]S→0A1B0,A→0A1B0S.B→1Bl1I0 GfS]s→aSa,S-→bsb,S-a。 证：W∈(a,b),当W∈a,b空串时，S∈a
例：G1[S]：S→A|S-A，G2[S]: A|A-S，A 都有→a|b|c。都可推导出 a-b-c。问 G1=?G2。 G1：S=>S-A=>S-C=>S-A-C=>S-b-c=>A-b-c=>a-b-c G2 ： S=>A-S=>A-A-S=>A-A-A=>A-A-C=>A-b-c=>a-b-c=>a-A-S=>a-b-A= >a-b-c ∵文法等价，但语义不等价（顺序不同） 2.4.文法和语言的分类 1. 0 型文法，0 型语言（L0）：u→v(u∈v + ,v∈v ※ )，u 中至少有一个非 终结符可由图机接收。即 0 型文法只是要求元素都在 V 中即可，每 个式子可以随便写。 2. 1 型文法，1 型语言（CSL）（L1）：xUy→xuy, x、y∈V ※，U∈ VN，u∈V+，|u|≥|U|，可由空间线性界限图灵机接收。 例：G[S]: S→aSBE,S→aBE, EB→BE, aB→ab, bB→bb, bE→be, eF→ee G[S]: S→CD, C→aCA, C→bCB, AD→aD, BD→bD, Aa→bD, Ab→bA, Ba→aB, Bb→bB, C→E，D→E 3. 2 型文法（上下文无关文法）2 型语言（CFL）：U→u，U∈VN,u∈ V ※ -常见形式。由不确定的下推自动机接收 例：G[S]:S→aB|bA, A→a|aS|bAA, B→b|bS|aBB G[S]:S→0A|1B|0, A→0A|1B|0S. B→1B|1|0 G[S]:S→aSa, S→bSb, S→α。 证：W∈（a，b） ※，当 W∈a,b 空串时，S∈α
当W∈(a,b)+时，S→abSba→. 4.3型文法（正规则文法）(RG)。3型语言(RL).L),由有穷 状态自动机接收。 例：G)I→m,I→l,T→lr,T→dT,T→l,T→d 判断：符号就是字符×，可以是一串字符构成一个符号 结论：0型文法可以产生L0,L1,L2,L,但2型文法只能产生L2,不 能产生L1。 2.5上下文无关文法及其语法树 一、1上下文无关文法有足够能力描述现今程序设计语言的语法结构 例：算术表达式，语句（赋值、条件）P7 2.语法树：句型结构的图示表示法，它是一种有向图，由结论和有 向边组成结论：符号：根结点：识别符号；中间节点：非终结符： 叶节点：终或非终：有向边：表示结点间的派生关系 3.短语。简单短语，句柄 短语：GS]:S=>xUy=>xuy,S,U∈VN,xy,ueV 则u为句型xuy相对于U的短语 例：G[S]:S→AB.A一Aa.A→bB.B→a,B→Sb.求句型baSb的短语 最左①S=>AB=>bBB=>baB=>baSb则S=>baB=>baSb, ∴.sb是baSb相对于B的短语 简单短语：S=>xUy=>xuy.则u是句型xuy相对于U的简单短语 句柄：最左简单短语： 例1：上例：S=>AB=>ASb->bBSb->baSb
当 W∈（a，b）+时，S→abSba→. 4. 3 型文法（正规则文法）（RG）。3 型语言（RL）.(L3), 由有穷 状态自动机接收。 例：G(I):I→lT, I→l, T→lT, T→dT, T→l,T→d 判断：符号就是字符 ×， 可以是一串字符构成一个符号 结论：0 型文法可以产生 L0,L1,L2,L3, 但 2 型文法只能产生 L2，不 能产生 L1。 2.5 上下文无关文法及其语法树 一、1.上下文无关文法有足够能力描述现今程序设计语言的语法结构 例：算术表达式，语句（赋值、条件.）P37 2. 语法树：句型结构的图示表示法，它是一种有向图，由结论和有 向边组成-结论：符号；根结点：识别符号；中间节点：非终结符； 叶节点：终或非终；有向边：表示结点间的派生关系 3. 短语。简单短语，句柄 短语：G[S]:S=>xUy=>xuy,S,U∈VN，x,y,u∈V ※ 则 u 为句型 xuy 相对于 U 的短语 例：G[S]:S→AB. A→Aa. A→bB. B→a, B→Sb. 求句型 baSb 的短语 最左 ①S=>AB=>bBB=>baB=>baSb 则 S=>baB=>baSb， ∴sb 是 baSb 相对于 B 的短语 简单短语：S=>xUy=>xuy. 则 u 是句型 xuy 相对于 U 的简单短语 句柄：最左简单短语； 例 1：上例：S=>AB=>ASb=>bBSb=>baSb
短语：baSb(S),ba(A),a(B),Sb(B) 简单短语：a(B),Sb(B) 句柄：a(B)。 例2.Baabaab是不是上例G[S]文法的句子，找出短语，简单短语和句 柄 S=>AB=>ASb=>AABb=>AAab=>AbBab=>Abaab=>Aabaab=>bBabaa b=>baabaab 短语：baabaab(S),baa(A),ba(A),ba2a3(S),ba2a(B),ba2(A)。 句柄：a(B)。 简单短语：a2(B),a(B)。 例3.GE]E→TE+TE-T,T→FT*FTE,F→(E)i,判断(F+i)-T*(E-T) 和(T+i)*i-F是否是句型，求短，简短，句柄。 E=>E-T=>E-F=>T-F=>T*F-F=>T*i-F=>F*i-F=>(E)*i-F=>(E+T)*i-F=> (E+F)*i-F=>(E+i)*i-F=>(T+i)*i-F 短语：(T+i)*i-F(E),(T+i)*i(E)(T),(T+i)(T)(F),(T+i)(E), 句柄：i(F)(T) F(T) T(E) P(F) 句型推导过程<=>句型语法树的生长过程 ①由推导构造语法树：从识别时开始，自作向右建立推到序列 自根节点开始，自上而下建立语法树
短语：baSb（S），ba（A），a（B），Sb（B） 简单短语：a（B），Sb（B） 句柄：a（B）。 例 2. Baabaab 是不是上例 G[S]文法的句子，找出短语，简单短语和句 柄 S=>AB=>ASb=>AABb=>AAab=>AbBab=>Abaab=>Aabaab=>bBabaa b=>baabaab 短语：baabaab(S), ba、 a(A), ba、 (A), ba 2a 3(S), ba 2a 3(B), ba 2(A)。 句柄：a、 (B)。 简单短语： a 2(B), a 3(B)。 例 3. G[E]:E→T|E+T|E-T, T→F|T*F|T/F, F→(E)|i，判断（F+i）-T*(E-T) 和（T+i）*i-F 是否是句型，求短，简短，句柄。 E=>E-T=>E-F=>T-F=>T*F-F=>T*i-F=>F*i-F=>(E)*i-F=>(E+T)*i-F=> (E+F)*i-F=>(E+i)*i-F=>(T+i)*i-F 短语：(T+i)*i-F（E），(T+i)*i（E）（T），（T+i）（T）（F），（T+i）（E）， 句柄：i、（F）（T） F（T） T（E） I 2(F) 句型推导过程<=>句型语法树的生长过程 ①由推导构造语法树：从识别时开始，自作向右建立推到序列 自根节点开始，自上而下建立语法树
②由语法树构造推导：自下而上修剪子树的末端结点，直至把整棵树 留根，每剪一次对应一次归纳，从可型开始，自右向左逐步归纳，建 立推导序列。 二、文法的二义性。（歧义性） 例：GE:E一E+EE-EE*EE/EE)i,即所有四则运算。 DE=>E+E=>i+E*E=>i+i*E=>i+i*i ②E=>E*E=>E+E*E=>i+E*E=>1计i*1 若对于一个文法的某个句子存在两颗不同的语法树，则该文法是 二义性，否则是无二义，换言之，无二义性文法的句子只有一棵语法 树，尽管推导过程可以不同 若一个文法的某句子存在两个不同的规范推导，则该文法是二义 的，否则是无二义性的-自顶向下 若一个文法的某规范可型的句柄不唯一，则该文法是二义性的， 否则是无二义性的一一一自底向上 例：上例中规范可型E+E*i 句柄分别是i和E+E 欲证明某文法是二义性的，需找到一句子可以画出两棵语法树 2.6可型的分析 1.可型分析：是识别一个符号串是否为某文法的句型，是某个推导的 构造过程。 2分析算法：自上而下分析算法：从文法的开始符出发，反复使用 各种产生式，寻找与输入符相匹配的推导：
②由语法树构造推导：自下而上修剪子树的末端结点，直至把整棵树 留根，每剪一次对应一次归纳，从可型开始，自右向左逐步归纳，建 立推导序列。 二、文法的二义性。（歧义性） 例：G[E]:E→E+E|E-E|E*E|E/E|(E)|i，即所有四则运算。 ①E=>E+E=>i+E*E=>i+i*E=>i+i*i ②E=>E*E=>E+E*E=>i+E*E=>i+i*i 若对于一个文法的某个句子存在两颗不同的语法树，则该文法是 二义性，否则是无二义，换言之，无二义性文法的句子只有一棵语法 树，尽管推导过程可以不同 若一个文法的某句子存在两个不同的规范推导，则该文法是二义 的，否则是无二义性的-自顶向下 若一个文法的某规范可型的句柄不唯一，则该文法是二义性的， 否则是无二义性的———自底向上 例：上例中规范可型 E+E*i 句柄分别是 i 和 E+E 欲证明某文法是二义性的，需找到一句子可以画出两棵语法树 2.6 可型的分析 1.可型分析：是识别一个符号串是否为某文法的句型，是某个推导的 构造过程。 2.分析算法： 自上而下分析算法：从文法的开始符出发，反复使用 各种产生式，寻找与输入符相匹配的推导；
自下而上分析法：从输入符号串开始，逐步进行归纳， 知道归纳到文法开始符。 3.句型分析的有关问题 ①.如何选用哪个产生方式进行推导？回溯第五章讲到假定要 被代换的最左非终结符是V,且有n条规则；V→AAA.如何选 定左P ②.如何识别可归纳串？规范归纳串中科规约串称为“句柄” 2.7有关文法实用中的一些说明 1有关文法的实用限制。 有害规则：形如U→U的产生式，会引起文法的二义性。 多余规则：文法中某些非终结符不在任何规则的右P出现，该终结符 称为不可到达：文法中某些非终结符由它才能退出终结符号串，称为 不可终止的。 指文法中任何句子的推导都不完全用到规则 2.上下文无关文法中的E规则 3.直撑左递归的消除。P81. 第三章词法分析 目的：1设计词法分析程序 2.单词的描述工具 3单词的识别系统
自下而上分析法：从输入符号串开始，逐步进行归纳， 知道归纳到文法开始符。 3.句型分析的有关问题 ①．如何选用哪个产生方式进行推导？ 回溯 第五章讲到 假定要 被代换的最左非终结符是 V，且有 n 条规则；V→A1|A2|.|An. 如何选 定左 P ②．如何识别可归纳串？ 规范归纳串中科规约串称为“句柄” 2.7 有关文法实用中的一些说明 1.有关文法的实用限制。 有害规则：形如 U→U 的产生式，会引起文法的二义性。 多余规则：文法中某些非终结符不在任何规则的右 P 出现，该终结符 称为不可到达；文法中某些非终结符由它才能退出终结符号串，称为 不可终止的。 指文法中任何句子的推导都不完全用到规则 2.上下文无关文法中的 E 规则 3.直撑左递归的消除。 P81。第三章.词法分析 目的：1.设计词法分析程序 2.单词的描述工具 3.单词的识别系统