例文法G=(VN,VT,P,S) VN={标识符，字母，数字 V-={a,b,C…xyz,0,1…9 P={<标识符>→<字母> <标识符>·<标识符><字母> <标识符>→<标识符><数字> <字母>→ay<字母>→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→e 2G[S]:A→ab A→aAb A→e S→aSb 3G[S]: A→ab aAb|e S→aSb 27
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
元符号： = 1 <> 习惯表示 大写字母：终结符 小写字母：非终结符 S->AB A->Ax|y B->Z
元符号: → ∷= | < > 习惯表示 大写字母：终结符 小写字母：非终结符 S –> AB A –> Ax | y B –> z
推导的定义 直接推导“→” a→B是文法G的产生式，若有v,w满足： v=Yaδ，w=YBδ，其中Y∈V*,6∈V* 则称v直接推导到w,记作v→w 也称w直接归约到v 例：G:S→0S1,S→01 0S1→00S11 00S11→>000S111 000S111→00001111 S→0S1 29
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
30 <程序><分程序>. <分程序>. <变量说明部分> <语句>. VAR<标识符>;BEGIN READ(<标识符>)END. VAR A;BEGIN READ(<标识符> ) END