软了个考——但是研究起来总跟吃了炫迈一样，哎~
上次一不小心作死向地研究了一下下文法，顺手画了个图，这次本来想着完善图之后再写博客的，后来发现实在是对编译原理这一块的理解太少了，翻了师哥师姐的博客也只限于视频的大概说明。由于没有这几天没网，软考书和视频中讲的不太详细，一直也没怎么理解到底这东西是干嘛的。
借了本专业课的书来看终于是又搞懂了一点点。
咱们上回书说道，文法是分0123型的，文法是编译原理的基础，计算机就是根据这些事先写好的文法来判断我们输入的语句结构时候合法。举个例子来说，我们定义一个string类型的变量的时候，要输入“string strExample”对吧？那么因为vs或是Eclipse等软件事先设置好了一句文法“string->字符串”这个意思就是在某某语法中通过string这几个字母，能推出字符串这个类型来。而我们的资料基本上都挺抽象的，“A->a”，简直反人类。
总结一下，文法就是一个规则。可能写成那样大家不熟悉吧，那么变一下，f(A)=a，这样应该都认识了吧。
好了，那么我们继续。有时候看着一大堆的文法是不是很难受？这时候有人发明了一个叫做语法推导树的东西，一般我们画这个推导树是根据上下文无关文法，也就是2型文法画的。至于有关无关的区别，也很简单，一会说，先接着来推导树。
树表示结构，那么语法推导树表示的就是语法结构，画法也就是根据文法一条一条的去执行就行了。比如有一个S->aAB|a。那么分解一下就是S->aAB，S->a。那么就这么画。
文章图片
文章图片
不许吐槽画的难看- -。
那么A、B都是大写，上次说这个是非终结符，也就是说推到这里是不行的，因为计算机还不知道输入的A、B到底代表什么，那么我们做题来说后面肯定有其他的文法，A->aSB，B->ab。
然后就是这么个样子。
文章图片
文章图片
而这个文法的推到结果就是aaaabab，是不是比单纯的文法清晰多了？
那么刚才说了这个是上下文无关文法，即2型文法，上次说了，2型文法左边全是大写，所以遇到大写的可以随便推，不用管上下文是什么，而有关的文法呢？aA->abc这样就是有关的，只有aA在一起才能推abc，所以要关注上下文是否是符合文法的才能推。
那么我们再进一步，当需要描述3型文法的时候用到的是另一种规范，叫正规式。这个我猜是因为在3型文法是会出现A->aA这种情况的，所以这就是个循环，画图就画不出了。正规式其实也简单，一共就三个规则。
文章图片
文章图片
细节就不去追究了，大概就是这个样子吧。
后面是有穷自动机的简单说明。我们写好了文法，当然是要计算机去识别，有穷自动机就是一种能识别的装置，他能准确的识别正规式集合。
【软了个考——但是研究起来总跟吃了炫迈一样，哎~】有穷自动机有确定不确定之分，而区别仅仅是初态是一个还是多个，一个就是确定有穷自动机，这里我只说一下由文法画有穷自动机。
首先在自动机中加入一个终态Z，表示整个自动机的终结。然后每一个大写的字母就是一个结点，小写字母可以看做是路径。
例如S->aA，就可以画成这样。
文章图片
文章图片
而A->bA这种能推出自身的就是这样。
文章图片
文章图片
还有一种情况，是直接到终态Z的，比如B->ε。那就直接画到终态就好了。
文章图片
文章图片
一大堆文法的话就按照大写是结点，小写是路径这样画就行了。当然有时候会有01什么的情况，当做终结符处理就行了，也当路径一样画，最后画的顺眼就行了。
我就说这是走迷宫吧。。。
行了，写的差不多了，再来个不确定有穷自动机转化确定有穷自动机实在是看不动了。总的来说仅仅看这些定义还挺复杂的，再加上那些作者们总喜欢把很容易理解的东西写的很难很难，就造成了有人说看不懂，其实还是老师讲过的那个道理，一上来就认为自己看不懂，那就肯定看不懂了。写完这篇博客还剩下好多问题，一些定义是看懂了，做题还够呛，看来还是理解的不够，需要做做题加深理解了。
以上
推荐阅读
- 急于表达——往往欲速则不达
- 慢慢的美丽
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量
- 2019-02-13——今天谈梦想（）
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- Ⅴ爱阅读，亲子互动——打卡第178天
- 低头思故乡——只是因为睡不着
- 取名——兰
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 广角叙述|广角叙述 展众生群像——试析鲁迅《示众》的展示艺术