例: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.单词的识别系统
3.1词法分析程序 源程序=>词法分析程序语法分析程序.(token:单词,句子,符 号) 词法分析的主要任务:1.扫描源程序 2.生成单词符号 3生成中间程序 其他任务:1滤掉空格,跳过注释,换行符 2追踪换行标志,复制出错源程序 3.宏E开 输出形式(单词种别,单词自身的值) 标识符输出表示(标识符,指向该标识符所指符号表中的位置)例 P48 词法分析独立的原因:1.简化设计 2.改进编译效率 3.增加编译系统的可移植性 3.2单词的描述工具 正则文法正则式正则集 例:ab*{ab,abb,abbb,.}
3.1 词法分析程序 源程序=>词法分析程序语法分析程序.(token:单词,句子,符 号) 词法分析的主要任务:1.扫描源程序 2.生成单词符号 3.生成中间程序 其他任务: 1.滤掉空格,跳过注释,换行符 2.追踪换行标志,复制出错源程序 3.宏 E 开. 输出形式(单词种别,单词自身的值) 标识符输出表示(标识符,指向该标识符所指符号表中的位置)例 P48 词法分析独立的原因: 1.简化设计 2.改进编译效率 3.增加编译系统的可移植性 3.2 单词的描述工具 正则文法正则式正则集 例: ab* {ab,abb,abbb,.}
1.正则表达式。定义P49 例:={a,b}正则式:a*,ba*,aba* 正则集:{e,a,aa,}.{b,ba,baa},{a}Uba*={a,b,ba,baa} 正则式:aalbblablba 正则集{aa,bb,ab,ba} 正则式正则集 (ab)*=>(alb)*=fe,a,b,aa,ab,abb,. (alb)*(aalbb)(alb)*=(alb)*(aa,bb)(a,b)*e a,b,aa,.aa/bb, e,a,b,aa,.} 即{以ab的任意串开头,中间相邻aa或bb,以a,b任 意串结尾 2.正规式=代数规律:P50 3.正规文法到正规式 规则1:A→xB,B一y A-xy 规则2:A→xAy A=x*y A→Axy A可yx* 规则3:A→x,A→y A=xly 例1.G[s,s→aA,A→abA,A→a 后两式:A→abAa根据规则2:A=(ab)*a→代入S;S=a(ab)*a 例2.P524.5Gs]S→aA,S→a,A→aA,A→dA,A→a,A→d 后四式:A→aAldAlald-→(ad)A(ad) 根据规则2:A=(ald)*(ad代入S:S=a(ald)*(ald)a 根据代数规则:a(ald*(alde)=a(ad)+|e)=a(ad)*
1.正则表达式。 定义 P49 例:Σ={a,b} 正则式:a*,ba*, a|ba* 正则集:{ε,a,aa,.}.{b,ba,baa,.},{a}Uba*={a,b,ba,baa,.} 正则式:aa|bb|ab|ba 正则集{aa,bb,ab,ba} 正则式 正则集 (a|b)* =>(a|b)*={ε,a,b,aa,ab,abb,.} (a|b)*(aa|bb) (a|b)* => (a|b)*(aa,bb)(a,b)* = { ε ,a,b,aa,.aa/bb, ε,a,b,aa,.} 即{以 ab 的任意串开头,中间相邻 aa 或 bb,以 a,b 任 意串结尾} 2.正规式=代数规律:P50 3.正规文法到正规式 规则 1:A→xB,B→y A=xy 规则 2:A→xA|y A=x*y A→Ax|y A=yx* 规则 3:A→x,A→y A=x|y 例 1. G[s],s→aA,A→abA,A→a 后两式:A→abA|a 根据规则 2:A=(ab)*a →代入 S; S=a(ab)*a 例 2. P52 4.5 G[s] S→aA,S→a,A→aA,A→dA,A→a,A→d 后四式:A→aA|dA|a|d→(a|d)A|(a|d) 根据规则 2:A=(a|d)*(a|d)代入 S: S=a(a|d)*(a|d)|a 根据代数规则:a((a|d)*(a|d)| ε)=a((a|d)+| ε)=a(a|d)*
或:化简(ad)*=(a,d)*={e,a,d,aa,. 则(ad)*(ad)={a,d}*(a,d)={e,a,d,aa,.}(a,d)=(ad) 代 入 a(ad)*a=faa,ad,aaa,.} (a)={a,aa,ad,.)=a(ald)* 例3.G[s]:S→aS,S→aB,B→bB,B→bC,C→cC,C-c 由后二式:C→cClc即C-c*c-c 代入B中B→bBbc即B=b*bc=bc 代入S中:S→aSaB s=a#abc=abc 4.由正规式到正规文法(即三个规则的递) 如:S=a(ab)*S→aAA→(ald)Ae 例L.S=ab(ab)*(aabb)形如A=x*y 所以G[slS→abAA→(ab)A(aabb)即A→aAlbAlaalbb 例2.S=a*blab*由规则2如A=x*yAyx* 所以G[ss→ABA→aAbB一→Bbla 例3.S=(ab(abl0l1)* GA]:A→A(ab0I1)l(ab)即A→AalAblA0A1ab 或G[s:S→aAbA,A→(ab0I1)Ae即A→aAbA0A1Ae 例4.S=(0l1)*000形如A=x*y 所以G[A]:A→(OI1)A000即A→0A1A000 例l:S→ABSAal e,A→a,B→SBBb求abbaa是否是句子 S=>ABS=ABAa=ABaa=>ASBBaa=ASBbaa=ASbbaa=A e bbaa=>abbaa
或:化简(a|d)*=(a,d)*={ ε,a,d,aa,.} 则(a|d)*(a|d)={a,d}*(a,d)={ ε,a,d,aa,.}(a,d)=(a|d) 代 入 a(a|d)*|a={aa,ad,aaa,.} υ {a}={a,aa,ad,.}=a(a|d)* 例 3. G[s]:S→aS,S→aB,B→bB,B→bC,C→cC,C→c 由后二式:C→cC|c 即 C=c*c=c 代入 B 中:B→bB|bc 即 B=b*bc=bc 代入 S 中:S→aS|aB s=a#abc=abc 4.由正规式到正规文法(即三个规则的递) 如:S=a(a|b)* S→aA A→(a|d)A|ε 例 1. S=ab(a|b)*(aa|bb)形如 A=x*y 所以 G[s]: S→abA A→(a|b)A|(aa|bb) 即 A→aA|bA|aa|bb 例 2. S=a*b|ab* 由规则 2 如 A=x*y A=yx* 所以 G[s]:s→A|B A→aA|b B→Bb|a 例 3. S=(a|b)(a|b|0|1)* G[A]: A→A(a|b|0|1)|(a|b) 即 A→Aa|Ab|A0|A1|a|b 或 G[s]: S→aA|bA , A→(a|b|0|1) A|ε 即 A→aA|bA|0A|1A|ε 例 4. S=(0|1)* 0 0 0 形如 A=x*y 所以 G[A]: A→(0|1)A|000 即 A→0A|1A|000 例 1:S→ABS|Aa|ε,A→a ,B→SBB|b 求 abbaa 是否是句子 S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>A ε bbaa=>abbaa
2.G[I]:I→II0 IalIclalblc.下列符号串不是该文法句子的有: ①ab0×②a0c0l√③aaa√④bl0√ 3.A→bAcc,. ①cc√②bcbe x③bcbcc x④bbbcc√ 3.3有穷自动机 1.状态转换图:是为了识别的符号串而设计的一种有限方向图 结点代表状态,用“0”表示:状态之间用“→”连接:“→”上符号 表示是射击结点状态下可能出现的输入符。 一层转换图只包含有限个状态,其中至少一个初态,并有若干个终态 “0” 后继状态:后继状态为自身 后继状态为一个 后继状态为若干个
2.G[I]:I→I|I0|Ia|Ic|a|b|c.下列符号串不是该文法句子的有: ①ab0 × ②a0c0| √ ③aaa √ ④ b|0 √ 3.A→bA|cc,. ①cc √ ② bcbc × ③bcbcc × ④bbbcc √ 3.3 有穷自动机 1.状态转换图:是为了识别的符号串而设计的一种有限方向图 结点代表状态,用“0”表示;状态之间用“→”连接;“→”上符号 表示是射击结点状态下可能出现的输入符。 一层转换图只包含有限个状态,其中至少一个初态,并有若干个终态 “o” 后继状态: 后继状态为自身 后继状态为一个 后继状态为若干个