本文主要是介绍第3章 文法和语言（三），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
五、文法的类型
（1）0型文法(短语文法)：对任一产生式α→β，都有α∈(VN∪VT)+， β∈(VN∪VT)*
（2）1型文法(上下文有关文法)：
对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外。即α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)
（3）2型文法（上下文无关文法）：
对任一产生式α→β，都有α∈VN ， β∈(VN∪VT)*
即A→β(A在VN中，β在V*中，)
（4）3型文法（正规文法）：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT
- 例：1型（上下文有关）文法
S→aBE
EB→BE
aB→ab
bB→bb
bE→be
eE→ee
- 例：2型（上下文无关）文法
文法G[S]： S→aB|bA
A→a|aS|bAA
B→b|bS|aBB
文法G[S]： S→0A|1B|0
A→0A|1B|0S
B→1B|1|0
- 例：定义标识符的3型（正规）文法
I → l
T → lT
T → dT
T → l
T → d
文法和语言
- 0型文法产生的语言称为0型语言
- 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）
- 2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CFL ）
- 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言或正则（正规）语言（ RL ）
六 上下文无关文法及其语法树
- 上下文无关文法有足够的能力描述现今程序设计语言的语法结构。
- 算术表达式
- 语句
- 赋值语句
- 条件语句
- 循环语句
- ……
1、语法树与推导
- 用于描述上下文无关文法的句型推导的直观方法
例: G[S]:
S→aAS
A→SbA
A→SS
S→a
A→ba
S→aAS
A→SbA
A→SS
S→a
A→ba
- 叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。
3、二义文法
- 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。
- 产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。
排除文法二义性的两种方法：
（1）在语义上加些限制（如优先顺序和结合律）。
（2）重构无二义性的文法。
（1）在语义上加些限制（如优先顺序和结合律）。
（2）重构无二义性的文法。
- 练习：有文法G[N]：
S →SD|D
E →0|2|4|6|8|10
D →0|1|2|3|4|5|6|7|8|9
（1）证明此文法有二义性
（2）此文法描述的语言是什么？
（3）试写出另一文法，其产生的语言和G[N]产生的语言等价且是无二义性的。
这篇关于第3章 文法和语言（三）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
