编译原理第三讲讲义.ppt

1.文法的定义 例 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号 例 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={标识符→字母 标识符→标识符字母 标识符→标识符数字 字母→a,…, 字母→z 数字→0,…, 数字→9 } S=标识符 文法的写法 1 G：S→aAb A→ab A→aAb A→ε 2 G[S]： A→ab A→aAb A→ε S→aSb 3 G[S]： A→ab |aAb |ε S→aSb 例1 设∑={a,b}试设计文法描述语言 L={a2n |n ≥ 1 } 例2 设∑={a,b}试设计文法描述语言 L={a2n ,b2n |n ≥ 1 } 例3 设∑={a,b}试设计文法描述语言 L={abna |n ≥ 0 } 例4 写文法，是其语言是自然数的集合 例5 写文法，是其语言是奇数集合，但不允许有以0打头的奇数 例6 试设计一个表示所有标识符的文法 2.推导的定义 直接推导“?” α→β是文法G的产生式，若有v,w满足：v=γαδ,w= γβδ, 其中γ∈V*,δ∈V* 则称v直接推导到w,记作 v ? w 例：G： S→0S1， S→01 注意: ?和→的区别 推导的定义 推导“ ” 若存在v ?w0 ?w1 ?... ?wn=w,(n0) 则记为v w，v推导出w 广义推导“ ” 若有v w，或v=w， 则记为v w 例：G： S→0S1， S→01 S ?0S1 ?00S11 ?000S111 0S1 ?00S11 00S11 ?000S111 000S111 S S 000 S 111 S S 00S11 000S111 3.归约 直接归约: w ? v(当且仅当v ? w) 例:0S1 ?00S11 00S11 ? 0S1 归约: w v(当且仅当v w) 例: S S 广义归约: w v(当且仅当v w) 例: 00S11 00S11 00S11 00S11 例：G[E]： E→E+T|T T→T*F|F F→(E)|a构造a+a*a的推导和归约过程 4.句型、句子的定义 句型 有文法G，若S x，且x∈V*则称x是文法G的句型。 句子 有文法G，若S x，且x∈VT*，则称x是文法G的句子。 例：G： S→0S1， S→01 S ?0S1 ?00S11 ?000S111 G的句型S,0S1 ,00S11 ,000S111G的句 01 例：G[E]： E→E+T|T T→T*F|F F→(E)|aE?E+T ?T+T ?F+T ?a+T ?a+T*F ?a+F*F ?a+a*F ?a+a*a句子：用符号a，+，*，(和)构成的算术表达式 5.语言的定义 由文法G生成的语言记为L(G),它是文法G的一切句子的集合: L(G)={x|S =* x，其中S为文法的开始符号，且 x ∈VT*} 例1：G： S→0S1， S→01 L(G)={0n1n|n≥1} 例2 设有文法G[A] A →yB B → xB|x 求该文法所描述的语言 例3 设有文法G[S ] ： S?aSb? ab 求该文法所描述的语言 S?aSb ? aaSbb ? a3Sb3 ? …… ? an-1Sbn-1 ? anbn 例4 文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee L（G）={ anbnen | n≥1 } S ?a S BE