文法与正规式

一个形式文法是一个有序四元组G=(V，T，S，P)，其中：

1）V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符。

2）T：终结符。是语言的组成部分，是最终结果。

3）S：起始符。是语言的开始符号。

4）P：产生式。用终结符替代非终结符的规则。形如α→β

文法的分类：

常见的程序设计语言一般是上下文无关文法

正规式

正规式是描述程序语言单词的表达式，对于字母∑，其上的正规式及其表示的正规集可以递归定义如下。

① ε是一个正规式，它表示集合L(ε)={ε}。

② 若a是∑上的字符，则a是一个正则式，它所表示的正规L(a)={a}。

③ 若正规式r和s分别表示正规集L®=L(s)，则

（a）r|s是正规式，表示集合L®∪L(s)；

（b）r·s是正规式，表示集合L®L(s)；

（c）r*是正规式，表示集合(L®)*；

（d）®是正规式，表示集合L®。

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。由此可见，正规式要么为空，要么由字母、或、连接、闭包运算符组成。其中闭包运算符“*”具有最高的优先级，连接运算具有次高优先级，或运算符“|”具有最低优先级。

**常见正规式的含义：
**