ch3new文法和语言.ppt

符号串的头尾：如果z＝xy是一符号串，那么x是z的头，y是z的尾。 如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有头。 符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。 2 、文法定义 文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P: 规则的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如?→?或? ∷=?的(? ，?)有序对，其中?是字母表V的正闭包V+中的一个符号，?是V*中的一个符号。 ? 称为规则的左部， ? 称作规则的右部。 例 文法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 推导的定义 直接推导“?” α→β是文法G的产生式，若有v,w满足：v=γαδ,w= γβδ, 其中γ∈V*,δ∈V* 则称v直接推导到w,记作 v ? w 也称w直接归约到v 例：G： S→0S1， S→01 0S1 ?00S11 00S11 ?000S111 000S111 S ?0S1 推导 程序?分程序. (程序 ? 分程序. ) 分程序. ? 变量说明部分 语句. (分程序 ? 变量说明部分 语句) VAR标识符;BEGIN READ(标识符)END. ? VAR A;BEGIN READ(标识符 ) END. (标识符 ?A) VAR A;BEGIN READ(标识符 ) END. ? VAR A;BEGIN READ( A) END. (标识符 ?A) 推导的定义 若存在v =w0 ?w1 ?... ?wn=w,(n0) 则记为v w，称作v推导出w，或w归约到v 若有v w 或 v=w， 则记为v w 例：G： S→0S1， S→01 0S1 ?00S11 00S11 ?000S111 000S111 S ?0S1 ?00S11 ?000S111 S S S 00S11 00S11 句型、句子的定义 句型 有文法G，若S =* x，则称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，+，*，(