编译原理（清华大学出版社）-- 文法和语言

• 对Pascal程序来说，一个上下文无关文法，可以定义为符号串 A := BC
• 程序设计语义分为两类：静态语义和动态语义

文法的直观概念

推导或产生句子

例如，我是大学生

<句子> => <主语><谓语>

            => <代词><谓语>

            =>  我<谓语>

            =>  我<动词><直接宾语>

            =>  我是<直接宾语>

            =>  我是<名词>

            =>  我是大学生

• 符号 => 的含义是，使用一条规则，代替其左端的某个符号，产生其右端的符号串

符号和符号串

字母表

• 字母表的元素的非空有穷集合，字母表中的元素称为符号
• 因此字母表也称为符号集
• 不同语言可以有不同的字母表

符号串

• 由字母表中的符号组成的任何有穷序列称为符号串
• 例如，001110 是字母表{0, 1}的符号串；a，b，c，aaca是A={a,b,c}上的符号串
• 允许空符号串，不包含任何符号的符号串，用ε表示，其长度为0，即|ε|=0

符号串的运算

• 符号串的头尾，固有头和固有尾
• 如果 z=xy 是一符号串，那么 x 是z的头，y是z的尾，如果x是非空的，那么y是固有尾；如果y是非空的，那么x是固有头
• 设z=abc，那么z的头是ε，a，ab和abc；除abc外，其他都是固有头；z的尾是ε，c，bc和abc；z的固有尾是ε，c和bc
• 省略写法：z=x^...，z=^...x^...

符号串的连接

• 设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串
• 例如，设x=ST，y=abu，则它们的连接xy=STabu，看出|x|=2，|y|=3，|xy|=5，由于ε的含义，显然由 εx=xε=x

符号串的方幂

• 设x是符号串，把x自身连接n次得到符号串z，即z=xx^...xx，称为符号串x的方幂，写作z=xⁿ，即把符号串x相继地重复写n次
• x⁰=ε，x¹=ε，x²=xx，x³=xxx分别对应于n=0，1，2，3
• 对于n>0，有xⁿ=xx^n-1=x^n-1x

符号串集合

• 若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合
• 两个符号串集合A和B的乘积定义如下：AB={xy|x∈A且y∈B}，即AB是满足x属于A，y属于B的所有符号串xy所组成的集合
• 例如，若A={a，b}，B={c，d}，则集合AB={ac, ad, bc, bd}，对任意符号串x有εx=xε=x，所以有{ε}A=A{ε}=A
• 指定字母表∑之后，可以用∑^*表示∑上所有有穷长的串的集合，例如∑={0，1}，则∑^*={ε,0,1,00,01,10,11,000,001,010,...}，也可表示为字母表的方幂形式，∑^*称为集合∑的闭包
• 而∑⁺=∑¹∪∑²...∑ⁿ称为∑的正闭包，显然有 ∑^*=∑⁰∪∑⁺，∑⁺=∑∑^*=∑^*∑
• ∑^*具有可数的无穷数量的元素，若x是∑^*中的元素，则表示为x∈∑^*，否则x不属于∑^*，对于所有的∑，有ε∈∑^*

文法和语言的形式定义