第三章-文法和语言

文章目录

（一）语言（后面一点的地方有更详细的）1.语法2.语义（二）文法（后面一点的地方有更详细的）1.定义：2.作用：（三）字母表（符号集）（四）符号串1.定义：2.特点：3.符号串运算4.符号串集合5.符号串集合的方幂：6.符号串集合的闭包7.一些字符串集合的例子（五）文法1.产生式：2.定义：3.注意：4.文法的简化表示5.推导与规约(六)语言1.句型和句子②例子：2.语言①定义：②例子：③文法和语言的关系：3.文法的等价②例子：（不同的文法可以表示同一种语言）

（一）语言（后面一点的地方有更详细的）

1.语法

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

2.语义

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

（二）文法（后面一点的地方有更详细的）

1.定义：

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

2.作用：

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

（三）字母表（符号集）

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

（四）符号串

1.定义：

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

2.特点：

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

3.符号串运算

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

4.符号串集合

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

5.符号串集合的方幂：

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

6.符号串集合的闭包

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

7.一些字符串集合的例子

（五）文法

1.产生式：

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

2.定义：

（一般不用这种）

3.注意：

4.文法的简化表示

（一般用这种）

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

5.推导与规约

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

③ +与*

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

(六)语言

1.句型和句子

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

②例子：

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

2.语言

①定义：

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

②例子：

③文法和语言的关系：

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

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

3.文法的等价

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

②例子：

（不同的文法可以表示同一种语言）

下一part是各种类型的文法.....