文法的定义 例文法G=(VN,Vr,P,S) vN={S}V={01 P={s→0s1,S→01} s为开始符号
6 文法的定义 例 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号
例文法G=(VA,Vr,P,S) VN={标识符,字母,数字 v={abcr…xyz,01…9} P={<标识符>→<字母> <标识符>→≤标识符><字母> <标识符>→≤标识符><数字> <字母>→a <字母>→z <数字>→0 <数字>→9 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 (2)G[S]:A→ab A→ab A→aAb A→aAb A A→ε S→aSb (3)G[S]:A→ab|aAb S→aSb
8 文法的写法 元符号: → ∷= | < > 习惯 大写字母表示非终结符 小写字母表示终结符 (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
推导的定义 直接推导“→” a→β是文法G的产生式,若有v,w满足: v=γa8,w=yβδ,其中γ∈V,δ∈V 则称v直接推导到w,记作ⅴ→W 也称w直接归约到v 例:G:S→0S1,S→01 0s1→00S1l 00s11→000S11l 000S11l→000011ll S→0S1
9 推导的定义 直接推导“” α→β是文法G的产生式，若有v,w满足： v=γαδ,w= γβδ, 其中γ∈V* ,δ∈V* 则称v直接推导到w,记作 v w 也称w直接归约到v 例：G： S→0S1， S→01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1
推导 <程序>→<分程序> (<程序>→<分程序>) <分程序>→<变量说明部分><语句> (<分程序>→<变量说明部分><语句>) VAR<标识符> BEGIN READI(<标识符>)END.→ VARA; BEGIN READ(<标识符>)END (标识符>→A) VARA; BEGIN READ(<标识符>)END VAR A; BEGIN READ(A) END. (<标识符>→A)
10 推导 <程序><分程序>. (<程序> <分程序>. ) <分程序>. <变量说明部分> <语句>. (<分程序> <变量说明部分> <语句>) VAR<标识符>;BEGIN READ(<标识符>)END. VAR A;BEGIN READ(<标识符> ) END. (<标识符> A) VAR A;BEGIN READ(<标识符> ) END. VAR A;BEGIN READ( A) END. (<标识符> A)