-
content
- 语言的定义
- 语法定义
- 语意定义
- 文法
- 语言设计
- 语言的定义
语言的定义
G=（N，T，P，S）
N：非终结式集合
T：终结式集合
文法
G=（Vt,Vn,S,P）
Vt是终结符集合
Vn是非终结符集合
一、文法
文法： 描述语言的语法结构的形式规则
学习文法主要是认识终结符和非终结符：其实这个特别简单，示例：
S->Ap
S->Bq
A->a
A->cA
B->b
B->dB
其中大写字母为非终结符，小写字母为终结符。两者组合可以构成一个式子。
二、文法的类型
文法定义的形式-四元组（Vn,Vt,P,S）: Vn为非终结符集，Vt 为终结符集，P为规则集，S为识别符|开始符，至少要在一个规则中作为左部出现，Vn ∩ Vt = ∅。根据对文法施加不同的限制，分成4种类型。
0型或短语文法：
产生式形如：α->β
其中：α、β属于字符串的闭包区间内且α至少包含有一个非终结符；解释：左边有非终结符，右边有终结符。举例：A->ab， A->Cb， A->b
0型文法是这几个文法中，限制最少的一个，一般见到的文法都可看做0型文法。0型文法的能力相当于图灵机（Turing）。
1型文法：又称为上下文有关文法：
产生式形如：α->β
其中：α->β均满足|α|<=|β|, 除了α->ε外；解释：式子左边可以有多个字符，但必须有一个非终结符；式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符且左边长度必须小于右边（例外）举例：A->B，A->Bba ，Bb->A，
2型文法：又称为上下文无关文法：
产生式形如： A ->β
解释：式子左边必须是非终结符，然而一个终结符一个非终结符的组合不是一个非终结符，如Ab不是一个非终结符，但是两个非终结符的组合就是一个非终结符了，如AB就是行了；式子右边可以有多个字符，可以是终结符，也可以是非终结符，但必须是有限个字符举例：AB->abc，B->ab
3型文法：又称为正规文法（正规文法又包括左线性文法和右线性文法）：
右线性文法：
产生式形如： A ->αB 或 A ->α
解释：式子左边只能有一个字符，而且必须是非终结符；式子右边最多有二个字符。如果有二个字符必须是（终结符+非终结符）的格式，如果是一个字符，那么必须是终结符。举例：B->aB
左线性文法：
产生式形如： A ->Bα 或 A ->α
解释：式子左边只能有一个字符，而且必须是非终结符；式子右边最多有二个字符。如果有二个字符必须是（非终结符+终结符）的格式，如果是一个字符，那么必须是终结符。举例：B->Ba
注意：式子右边的格式一定要一致。也就是说如果有一个是（终结符+非终结符）那么所有的式子都必须是（终结符+非终结符）， 如果有一个是（非终结符+终结符），那么所有的式子都必须是（非终结符+终结符）
四种类型文法描述能力比较：0型>1型>2型>3型文法
举例：判断 B−>Ab|a、 A−>ε|aB
属于那种文法。
1、我们分开来写，应该是：A->e A->aB B->Ab B->a
2、我们先来判断是否符合0型文法：0型文法规定左边必须有非终结符，那么这些都是符合的。
3、我们再来看是否符合1型文法：1型文法规定从小推到大。也符合。
4、我们再来看是否符合2型文法：2型文法规定左边必须是非终结符，也满足。
5、我们继续看是否符合3型文法：规定只能符合右线性或者左线性，那么前面一个应该是符合右线性的，后面一个是符合左线性的。所以综合起来就不符合3型文法了。得出结论：那么这个题目属于2型文法。
短语
-
一个句型的语法树中任一子树叶节点所组成的符号串都是该句型的短语。
![[Pasted image 20240409201203.png]]
直接短语
-
当子树不包含其他更小的子树时，该子树叶节点所组成的字符串就是该句型的直接短语。
-
短语包含直接短语，我们可以直接在短语中判断。
- 这里只有第五层的S和第三层的L不包含其他更下的子树，所以有a和S是直接短语。
- 其中(a)的父节点S包含L，S,(a)的父节点L包含L和S， (S,(a))的父节点S包含L
判断句柄
句柄是最左边的直接短语。
因为S处于最左边，所以S是直接短语。