第二章文法和语言 21文法的基本概念 个程序设计语言是一个记号系统,如自然语言一样, 它的完整的定义应包括语法和语义两方面。所谓一个语言的语 法是指一组规则,用它可以形成和产生一个合适的程序,目前 在程序设计语言的识别中广泛使用的是上下文无关的文法。在 这理主要介绍文法和语言的概念
第二章 文法和语言 2.1 文法的基本概念 一个程序设计语言是一个记号系统，如自然语言一样， 它的完整的定义应包括语法和语义两方面。所谓一个语言的语 法是指一组规则，用它可以形成和产生一个合适的程序，目前 在程序设计语言的识别中广泛使用的是上下文无关的文法。在 这理主要介绍文法和语言的概念
例:设有文法: 主语> 冠词>he →big → ate caught 名词> mouse cat
例：设有文法： → → →the →big → →ate|caught → →mouse|cat
=>=>=> the big the big cat=> the big cat the big cat ate=> the big cat ate> e big cat ate the=> the big cat ate the mouse
则： =>=> =>the=> the big =>the big cat =>the big cat =>the big cat ate=>the big cat ate=>the big cat ate the =>the big cat ate the mouse
21.1符号和符号串 定义2.1 字母表是有穷非空集合。用表示。 例:无符号一进制数的字母表为{0,1 C语言的字母表为字母、数字和若于专用符号组成的符号集 定义2.2 、符号串是由字母表中的符号组成的有穷序列,又称字符 例: a.,b. c ba,bac,Cacb,等都是字母表{abC}上的符号串
2.1.1 符号和符号串 定义 2.1 字母表是有穷非空集合。用Σ表示。 例：无符号二进制数的字母表为{0，1} C语言的字母表为字母、数字和若干专用符号组成的符号集 定义 2.2 符号串是由字母表中的符号组成的有穷序列，又称字符 串、串。 例：a,b,c,ba,bbac,caacb,···等都是字母表{a,b,c}上的符号串
定义2.3 不包含任何字符串的空符号串用表示 定义2.4 符号串x的长度,即符号串x中的字符用表示(读作x的 长度 例:|abd=3|a=1|E|=0 定义2.5 设非空符号串u=Xy其中y字,则称为U的子串,若u 则称y为u的真子串
定义 2.3 不包含任何字符串的空符号串用ε表示 定义 2.4 符号串x的长度，即符号串x中的字符用|x|表示(读作x的 长度) 例：|abc|=3 |a|=1 |ε|=0 定义 2.5 设非空符号串u=xvy,其中v≠ε,则称v为u的子串,若|u|> |v|则称v为u的真子串
定义2 如果z=是一个符号串,则是z和头,而/是z的尾。如果 是非空的,那么γ是固有尾:同样如果/非空,那么x是固有头 例:设z=abC,那么的头是a,ab,abc除abC外,其它都 是固有头。Z的尾是EC,bC,abC:z的固有尾是EC,bC
定义 2.6 如果z=xy是一个符号串，则x是z和头，而y是z的尾。如果x 是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。 例：设z=abc，那么z的头是ε,a，ab，abc。除abc外，其它都 是固有头。z的尾是ε,c，bc，abc。z的固有尾是ε,c，bc
定义2.7 x、y是同一字母表上的两个符号串,把y的符号写在的 符号之后得到的符号串,称为的连接。记为y 例:=ab,y=Wabu贝 z=Xy=abywabu 显然:X1+y=|2 EX-XE=X
定义 2.7 设x、y 是同一字母表上的两个符号串，把y的符号写在X的 符号之后得到的符号串，称为的连接。记为xy 例：x=ab，y=wabu 则 z=xy=abywabu 显然：|x|+|y|=|z| εx=xε=x
定义2.8 设x是符号串,把自身连接门次得到符号串乙,即z=x…x(n 个x),称为符号串x的方幂,记为z=xn 例:×=8×=X×2=X××3=X 定义2.9 符号串集合若集合A中的一切元素都是其字母表上的符号 串,则称A为该字母表上的符号串集合。 注意:E、(B和(表示空集)的区别
定义 2.8 设x是符号串，把x自身连接n次得到符号串z,即z=xx···xx(n 个x)，称为符号串x的方幂,记为z=xn 例：x 0=ε x1=x x2=xx x3=xxx ··· 定义 2.9 符号串集合若集合A中的一切元素都是其字母表上的符号 串，则称A为该字母表上的符号串集合。 注意：ε、{ε}和Φ（表示空集）的区别
定义210 两个符号串集合A和B的乘积AB定义为: AB={xyx∈A且y∈B 例:设A={abC},B={b,cda则集合 AB=ab, ac ada, bcb, bcc, bcda j 注意:由于Ex=xE=x因此!E}A=At}=A,但A=A0=0 则: A={E} Al-A A2=AA An=An-IA=AAn-1(n>0)
定义 2.10 两个符号串集合A和B的乘积AB定义为： AB={xy|x∈A且y∈B} 例：设A={a,bc}，B=｛b,c,da｝则集合 AB={ab,ac,ada,bcb,bcc,bcda｝。 注意：由于εx=xε=x 因此{ε}A=A{ε}=A ，但ΦA=AΦ=Φ 则： A 0={ε} A 1=A A 2=AA A n=An-1A=AAn-1（n>0）
显然: ∑1是字母表中的所有单个字符组成的字符串 2是所有由字母表中二个的字符组成的字符串 是所有由字母表中长度为的子考符串 ∑是所有由字母表中三个的字符组成的字 定义2.11 A的闭包A*=A0UAUA2U A的正闭包A+≡AUA2UA3U 显然A≡AA*≡AAA半=A0UA+
显然： Σ 1是字母表中的所有单个字符组成的字符串 Σ 2是所有由字母表中二个的字符组成的字符串 Σ 3是所有由字母表中三个的字符组成的字符串 Σ n是所有由字母表中长度为n的字符串集合 定义 2.11 A的闭包 A*=A0∪A 1∪A 2∪··· A的正闭包 A += A1∪A 2∪A 3∪··· 显然A +=AA*=A*A A*=A0∪A +