例算术表达式的文法G 考虑含有+、*的算术表达式组成的文法 nG=(i,+*,(),{E},F, 终结符 非终结符 开始符号 产生式巢合 集合Vr 集合VN P P:E→ E++EE 表达式3*4可由该文法定义 E E**EE E〉E米E E→ (EE)） =〉i米E E→ 直接推导 =>i米i 3 4 n简写G[E]:E+E+EE*E(E)i ☑D16138
例 算术表达式的文法 G 考虑含有+、*的算术表达式组成的文法 n G =({i，+，*，(，)}，{E}，E，P) P: E → E + E E → E * E E → ( E ) E → i 终结符 集合ＶT 非终结符 集合ＶN 开始符号 S n 简写 G[E]:E → E + E | E * E | ( E ) | i 表达式3*4可由该文法定义 E => E * E => i * E => i * i 3 4 直接推导 产生式集合 P 16/38
文法G的形式定义p22 G=(VT,VN2 S,P) G=({i,+,*,(,)},E},E,P) n Chomsky定义文法为一个四元式 nV非空有穷终结符集 nVN非空有穷非终结符集Vr∩VN=中 n S∈VN开始符号 uS至少在产生式左部出现一次 nP非空有穷产生式集合α→B ua∈(VrUV)*,且至少含有一个非终结符 uB∈(VrUV*, n令V=VT UVN 建·称V为文法符号，是文法G的字母表 ☒21738
文法G的形式定义 p22 Ｇ = (ＶT，ＶN，S，P) n Chomsky定义文法为一个四元式 n ＶT 非空有穷终结符集 n ＶN 非空有穷非终结符集 ＶT ∩ＶN = ф n Ｓ∈ＶN 开始符号 u S至少在产生式左部出现一次 n Ｐ非空有穷产生式集合 α→β u α∈(ＶT ∪ＶN) *，且至少含有一个非终结符 u β∈(ＶT ∪ＶN) * ， n 令Ｖ=ＶT ∪ＶN u 称Ｖ为文法符号，是文法G的字母表 G =({i，+，*，(，)}，{E}，E，P) 17/38