编译原理 第二章上: 字母表和符号串 文法概述

2.1 字母表和符号串

2.1.1 字母表

元素的非空有限集合，字母表中的每个元素称为==符号==，字母表也称为符号表。

例：∑={a,b,c},∑={0,1}

2.1.2 符号串

由字母表中的0个或多个符号组成的任何有穷序列。

例：∑={a,b,c} ε，aaa, abc,abcc等都是∑上等符号串。

1.符号串的长度：|abc|=3 |abcc|=4

2.符号串的相等：依次相等（有序），符号串x和符号串y相等，记作x=y

3.符号串的前缀和后缀

前缀，从后删除。后缀，从前删除。

删除0个或多个符号。

设z=abc，前缀是abc，ab，a，ε。后缀是：abc，bc，c，ε

4.子串

前缀+后缀，去掉重复的

5.字符串的连接：按序连接

6.字符串集合A与B的乘积：依次排序，不重不漏。

7.符号串的幂运算：即把x重复写n次，记作z=x^n^

8.集合的幂运算：跟符号串的幂运算相对比，注意，集合得排列，符号串不需要。

例：A={a,b} A^2^={aa, ab,ba,bb}

9.字符串集合的正闭包：正闭包要求字符串长度大于1，记作A^+^，A^+^=A^1^∪A^2^......

∑={0,1},∑^+^={0,1,00,01,11,000,....}

10.字符串集合的闭包（星闭包）：星闭包和正闭包相比就字符串长度就可以是0了,记作A^*^

∑={0,1},∑^*^={ε,0,1,00,01,11,000,....}

<font color=#0033FF>正闭包，最低1，星闭包，最低0 </font>

符号串及其运算的作用：

字母表(A)，

单词：按一定的规则构成的字符串(B)，B属于星闭包A。

句子：按一定规则由单词构成的集合(C),C属于星闭包B。

程序：部分句子的集合（D），则D属于C

2.2 文法

1.什么是文法？

文法是对语言结构的定义与描述，即从形式上描述和规定语言结构，也称为语法。

2.语法规则：

通过建立一组规则(产生式）,来描述语言中句子的语法结构，规定用“::=”表示“由...组成”或"定义为..."

3.由产生式推导句子

推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条产生式去进行推导。

例：给定一组语法规则，考察一个句子“我是大学生”的推导过程。

4.语法树

语法树能更直观的理解文法

结点分为非终结符号和终结符号，如<动词>就是非终结符号，我就是终结符号

2.2.1 文法形式定义

定义：文法G定义为一个四元组，G=（V~n~，V~t~,P,Z)

V~n~: 非终结符号集

V~t~:终结符号集

P:产生式或规则的集合

Z:开始符号（识别符号），S属于非终结符号集

非终结符号：

终结符号

产生式：产生式是一个有序对（a，b）,通常写为a→b，读作定义为。

2型文法：上下文无关文法，产生式的左部都是非终结符号，右部是终结符和非终结符组成的有穷符号串。约定将左部符合为识别符号规则作为规则集合的第一条规则。

意味着，词法分析是二型文法。

2.2.2 文法的EBNF表示

先说文法的BNF（巴克斯-诺尔范式），下面是一个BNF的例子

EBNF为扩充的BNF表示，采用一些元符号来提高文法规则的表法能力。

1. 元符号｜,如：<数字>→0|1|2|3|4|5|6|7|8|9
2. 元符号< >,表示多个非终结符或多个字母组成的符号，如：<数字>
3. 元符号{ },表示可重复连接，{t}^m^~n~，表示符号串t可连接n-m次，而{t}表示符号串t可连接0到无穷次。
4. [],[]里表示可有可无 5.（）,()括号内成分优先，可以提取公因式