第三章-文法和语言

①定义：语法是一组规则，用它可以形成和产生一个合适的程序 ②描述工具：文法 ③作用：定义什么样的符号序列是合法的，与符号的含义无关

①定义： 静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的 动态语义:表明程序要做什么 ②描述工具: 指称语义，操作语义等 ③作用：检查类型匹配，变量作用域等

文法是语言语法的描述工具，实现用有穷的规则把语言的无穷句子集描述出来

严格定义句子的结构，是判断句子结构合法与否的依据。用有穷的规则把无穷的句子集合描述出来

1.定义：元素的非空有穷集合（元素也称为符号），程序语言的字母表由字母数字和若干专用符号组成。

由字母表中的符号组成的任何有穷序列

①在符号串中，符号是有顺序的，顺序不同，代表不同的符号串，如ab和ba是不同的 ②不含任何符号的符号串称为空串，用ε表示，注意{ε}不等于{}（后者为空集） ③符号串长度：符号串中含有符号的个数

①符号串连接 ②符号串的方幂 把符号串a自身连接n次得到的字符串a^n=aa…aaa

①定义：若集合A中所有元素都是某字母表∑上的符号串，则称A为字母表∑上的符号串集合 ②符号串集合的乘积：符号串集合A和B的乘积

设A是符号串的集合，则称A^i为符号串集A的方幂，其中i是非负整数。

①定义：（ps：星闭包就叫闭包） ②正闭包（不包括空串）

产生式的一个有序对(α，β)，通常写作 α->β (或α::=β)

（一般不用这种）

（一般用这种）

       通常不用将文法的四元组表示出来，只写出产生式。

①例：v⇒w，称v直接推导到w，也称w直接规约到v ②定义： 直接推导就是用且只用一条产生式的右部替换产生式的左部的过程。 直接规约就是用且只用一条产生式的左部替换产生式的右部的过程

③ +与*

       上面的+是v推导出w（至少用了一次产生式），下面的*是包括了v直接等于w的情况（可以不用推导，直接等于） （*右部）是包括（+右部）的

①定义： （看例子就懂了） 设有文法G[S]，若符号串x是从开始符推导出来的，即S⇒x，则称x是文法G的句型。 若x仅由终结符组成，即S⇒x，且x∈VT *，则称x是文法G的句子。

句型是所有能推导出来的东西。 句子是只包含终结符的句型。

由文法G生成的语言记为L(G),它是文法G的一切句子的集合。

文法G生成的每个串都在L(G)中，L(G)中的每个串确实能被G生成。 (串里全是终结符)

④这个也是例子，看一眼就好了

#①定义： 若L(G1)=L(G2)，则称文法G1和G2是等价的。