几个概念： 1.字母表 2.特号串 9符号串集合 3.符号串的长度 4.空符号串 10.符号串集合的和、积 5.待号串的前缀（头） 11.特号串集合的方累 符号串的后缀（尾） 符号串的真前缀（真后缀) 12.符号串集合的闭包 6.符号串的子串 7.符号串的连接 8.符号串的方暴
几个概念： 1. 字母表 2. 符号串 3. 符号串的长度 4. 空符号串 5. 符号串的前缀（头） 符号串的后缀（尾） 符号串的真前缀（真后缀） 6. 符号串的子串 7. 符号串的连接 8. 符号串的方幂 9.符号串集合 10.符号串集合的和、积 11.符号串集合的方幂 12.符号串集合的闭包
规则一重写规则、产生式或生成式。 是形如a一β或a:=β的（a,阝)有序对， 其中α是某字母表V的的正闭包V+的一个符号，阝是 V*的一个符号。 a称为规则的左部，B称为规则的右部。 →和：=含义相同，读作“生成
❖ 规则——重写规则、产生式或生成式。 是形如α→β或α ∷= β的（ α ， β ）有序对， 其中α是某字母表V的的正闭包V+的一个符号， β是 V*的一个符号。 α称为规则的左部， β称为规则的右部。 →和∷=含义相同，读作“生成
二、文法与语言 1、一个上下文无关文法G是一个四元式(V,VN,S,P), 其中： V:是非空有限集，它的每个元素是终结符号； VT:是非空有限集，它的每个元素是非终结符号； VnVN=Φ； VTUVN=V; S:SEVN,称为开始特号； P:产生式集合（有限），每个产生式形式是 {P>a|P∈VN,a∈VUV)*,S至少一次为P;
二、文法与语言 1、 一个上下文无关文法G是一个四元式（VT ,VN,S, P ）， 其中: VT：是非空有限集，它的每个元素是终结符号； VT：是非空有限集，它的每个元素是非终结符号； VT∩VN=Φ; VT∪VN=V; P ：产生式集合（有限），每个产生式形式是 { P->α| P∈VN，α∈(VT∪VN)*，S至少一次为P }； S：S∈VN，称为开始符号；
例1、考虑下面的算术表达式的文法及语言 VT: id+-*/↑() VN: 表达式、运算待 S: 表达式 P: 表达式->表达式运算符表达式 表达式->（表达式） 得到文法 E秦E川-E]d >id G1(E: 芝茅特A世
例1、考虑下面的算术表达式的文法及语言 VT： id + － * / ↑ ( ) VN： 表达式、运算符 S： 表达式 P： 表达式 ->表达式运算符 表达式 表达式 ->（表达式） 表达式 -> －表达式 表达式 -> id 运算符 -> +| －| * |/|↑ 得到 文法 G1(E): E ->EAE|( E )| －E |id A -> + |－|*|/|↑
由此可见，文法G1(E)所定义的语言是上述算术表达式， 如：id+id,id*(id+id等 它表达了简单算术表达式由id用A连接起来 该文法的： VN是出现P的左部所有符号集合 V是P的所有特号 ..V=VIVN S是该文法所定义的句子名字 写出了P,就能找出其它三元素
该文法的： VN是出现P的左部所有符号集合 V是P的所有符号 ∴VT = V \ VN S是该文法所定义的句子名字 ∴写出了P ，就能找出其它三元素 由此可见，文法G1(E)所定义的语言是上述算术表达式， 如：id+id，id*(id+id) 等 它表达了简单算术表达式由id用A连接起来