程序设计语言|文法

从产生语言的角度出发，给出文法和语言的定义。

所谓产生语言，是指制定出有限个规则，借助他们就能产生此语言的全部句子。

1.文法的定义

描述语言语法结构的规则称为文法。文法是一个四元组G=(Vn,Vt,P,S)。

Vn是一个非空有限集，其每个元素称为非终结符；

Vt是一个非空有限集，其每个元素称为一个终结符；

Vn∩Vt=∅，Vn和Vt不含公共元素；V=Vn∪Vt，称V是文法G的词汇表，V中的符号称为文法符号。

P是产生式的有限集合，每个产生式形式为“α→β”的规则，α是产生式的左部，α∈V+且α中至少含有一个非终结符，β是产生式的右部，β∈V*，β是α的一个候选式。

S∈Vn，称为开始符号，它至少要在一个产生式中作为左部出现。

2.文法的分类

文法有4种类型：0型、1型、2型、3型。这4类文法之间的差别在于对产生式要施加不同的限制。

0型文法：G的任何产生式α→β，均有α∈(Vn∪Vt)+且α中至少含有一个非终结符，β∈(Vn∪Vt)*；

（对0型文法的每条产生式分别施加以下限制，则可得以下文法。）

1型文法：G的任何产生式α→β（S→ε除外）均满足|α|≤|β|（|x|表示x中文法符号的个数，ε是空串）；

2型文法：G的任何产生式形如A→β，其中A∈Vn，β∈(Vn∪Vt)*；

3型文法：G的任何产生式形如A→a或者A→aB（或者A→Ba），其中A，B∈Vn，a属于Vt；

0型文法是短语文法，其功能相当于图灵机，任何0型语言都是递归可枚举的。

1型文法是上下文有关文法，对非终结符的替换必须考虑上下文，且不允许替换成空串ε。

2型文法是上下文无关文法，非终结符的替换无须考虑上下文。

3型文法等价于正规式，因此也被称为正规文法或线性文法。

词法分析的词法规则一般用3型文法；

语法分析的语法规则一般用2型文法；语法分析方法有很多种，根据产生语法树的方向，可分为自底向上和自顶向下两类。

有区别，语法是指一个语句的格式是否正确，错误的语法写的程序是错误的，往往是不能运行或者运行后得到的是错误的结果。文法是指的我们在编程是书写的格式，它往往不会导致程序的错误，但不规范的文法会增加程序员解读程序的困难，所以我们要规范自己的文法，这样才能成为一个合格的编程人员。

这是编译原理里的问题

文法 可以通俗的说是一个东西产生所遵循的规则，如语言中的主谓宾，就是语言的文法

G[S] 这是文法G ：S->0S0 S->1 这就是他里面的规则

S->0 S 0 或S->1

N 表示一个数遵循文法G

n->0s0->00s00->00100

或者说他永远遵循文法G中S->0s0规则那么只可能为0

若遵循文法S->0 S 0 或S->1则大于0

---