【软考总结】——编译原理之文法
学习编译原理的过程中发现文法是一个稍微难理解的知识点，于是小编利用一些时间整理了，如有不对之处还请各位大神给予斧正，不胜感激啊！
何为文法？
定义：描述语言语法结构的形式规则，通俗一点，制定了一些规则，来确定编译语言的语法，进而实现功能的编译。文法G是一个四元组，可以表示为G=（VN，VT，P，S）。
基本概念
非终结符：非终结符一般是大写字母，例如A，B，C之类的，定义VN是一个非空的有限集，其中每一个元素都是非终结符。
终结符：终结符一般都是小写字母，例如 a，b，c之类，定义VT是一个非空有限集，其中每一个元素都是终结符。
P是推导式的一个集合，产生式的有限集合，每个产生式是形如“α—>β”的规则，其中α称为产生式的左部，β称为产生式的右部。
**S**是开始符。
文法的表示方式：
A —> a，B —> Ac，adB—>d，A—>adb类似的格式
文法的分类
乔姆斯基把文法分成4种类型，即0型，1型，2型，3型。
0型文法
这是最简单的一个文法，它比较宽容，没有那么多限制条件，要求左边α必须至少含有一个非终结符，右边可以是任意字符。
1型文法（上下文有关文法）
在满足0型文法的基础上，G的任何产生式α—>β（S—>ε除外），均满足|α|≤|β|，其中|x|表示中文符号的个数，说白了，1型文法就是比较左右部的长度。
2型文法（上下文无关文法）
在满足1型文法的基础上，α中只能有非终结符。
3型文法（正规文法）对应有限自动机
在满足2型文法的基础上，G的任何产生式如A—>a|aB（右线性）或A—>a|Ba（左线性）。
根据上面的定义，直接可以推出3型文法⊆2型文法⊆1型文法⊆0型文法
#
正规式到正规文法转换
有三种基本转换方式，基本上能解决我们遇到的转换方式。
正规式到正规文法转换
| A—>xB,B—>y | A=xy |
| A—>xA|y | A=x*y |
| A—>x,A—>y | A=x|y |
#
总结
在文法这一部分的学习主要是对文法的一个分类了解的掌握，四种类型，有简单到复杂，依次从属，直到最后限定了文法的两种正规式。文法的学习目前自己只接触到这么多，关于更深层的内容还是需要后面的不断的学习，好好利用这次软考的机会，务实一下基本工，多学习一下基础知识，也是同时为以后做一个铺垫吧。
╰半橙微兮°
亦凉
小灰灰
还没有评论，来说两句吧...