例文法G=(VN,V,P,S) V={标识符,字母,数字} Vr={abcr…xyrz,01…9} P={<标识符>→<字母> 标识符>→<标识符><字母> <标识符>→≤标识符><数字> <字母>→arm<字母>→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=<标识符>
文法的写法 1G:S→aAb A→ab A→aAb A→ 2G[S]:A→abA→aAbA→ S→aSb 3G[S] A→ab|aAb|e S→aSb
27 文法的写法 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
元符号 习惯表示 大写字母:终结符 小写字母:非终结符 S→>AB A->AXy B→>z
元符号: → ∷= | < > 习惯表示 大写字母：终结符 小写字母：非终结符 S –> AB A –> Ax | y B –> z
推导的定义 直接推导“→” a→β是文法G的产生式,若有ⅴ,w满足: v=γa8,w=yB8,其中γ∈V,δ∈V* 则称v直接推导到w,记作v→W 也称w直接归约到v 例:G:S→0s1,S→01 0s1→00S11 00s11→000s111 000s11→00001111 S→0S1
29 推导的定义 直接推导“” α→β是文法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 READ(<标识符>)END.→ VARA; BEGIN READ(<标识符>)END
30 <程序><分程序>. <分程序>. <变量说明部分> <语句>. VAR<标识符>;BEGIN READ(<标识符>)END. VAR A;BEGIN READ(<标识符> ) END