|
这段时间学习编译原理我们知道一段程序是如何进行编译的，我们知道一段程序在成功运行之前要经过编译运行，那么编译原理就是解释一段程序如何进行扫描识别的，那么我们就看一下到底是如何分析的吧。 编译原理及技术从本质上来讲就是一个算法问题而已，当然由于这个问题十分复杂，其解决算法也相对复杂。 我们学的数据结构与算法分析也是讲算法的，不过讲的基础算法，换句话说讲的是算法导论，而编译原理这门课程讲的就是比较专注解决一种的算法了。 那么我们这次讲的四种类型的文法可以说就是编译中使用的文法就是算法，那么我们来看一下这四种文法吧！ 1.文法
文法G定义为四元组（VN ,VT ,P,S）
VN ：非终结符集，通常用大写字母表示
VT ： 终结符集，通常用小写字母表示
P ：产生式集合（规则集合）
S ：开始符号（识别符号） 提示：下面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符。
2. 0型文法（短语）
设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。
0型文法相当于图灵机。
3. 1型文法（上下文有关文法） 它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
1型文法相当于线性有界自动机。
例子：如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。
特例：α→ε也满足1型文法。
4. 2型文法（上下文无关文法）
2型文法是在1型文法的基础上,再满足：每一个α→β都有α是一个非终结符。如A->Ba,符合2型文法要求。
2型文法相当于下推自动机。
例子：Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。A->Bab就对啦
5. 3型文法（正规文法）
它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。
3型文法相当于有限状态自动机。
注意：3型文法中只能满足右线性，或只能满足左线性，不能两种同时都有
例子：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导
为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。
这次学习编译原理我们可以说学习了一些我们以前没有学习过的知识，加油吧！
|
