【软考总结】——编译原理之文法

末蓝、 2022-07-16 00:24 355阅读 0赞

学习编译原理的过程中发现文法是一个稍微难理解的知识点，于是小编利用一些时间整理了，如有不对之处还请各位大神给予斧正，不胜感激啊！

# 何为文法？ #

定义：描述语言语法结构的形式规则，通俗一点，制定了一些规则，来确定编译语言的语法，进而实现功能的编译。文法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型文法

#     #

# 正规式到正规文法转换 #

有三种基本转换方式，基本上能解决我们遇到的转换方式。

<table>  
 <span style="font-size:24px">正规式到正规文法转换</span>  
 <tbody> 
  <tr> 
   <td><span style="font-family:KaiTi_GB2312; font-size:24px">A—&gt;xB,B—&gt;y</span></td> 
   <td><span style="font-family:KaiTi_GB2312; font-size:24px">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; A=xy</span></td> 
  </tr> 
  <tr> 
   <td><span style="font-family:KaiTi_GB2312; font-size:24px">A—&gt;xA|y</span></td> 
   <td> <p><span style="font-family:KaiTi_GB2312; font-size:24px">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; A=x<sub></sub><sup>*</sup>y</span></p> <span style="font-family:KaiTi_GB2312; font-size:24px"><br> </span></td> 
  </tr> 
  <tr> 
   <td><span style="font-family:KaiTi_GB2312; font-size:24px">A—&gt;x,A—&gt;y<br> </span></td> 
   <td><span style="font-family:KaiTi_GB2312; font-size:24px">&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; A=x|y</span></td> 
  </tr> 
 </tbody> 
</table>

#     #

# 总结 #

**   **在文法这一部分的学习主要是对文法的一个分类了解的掌握，四种类型，有简单到复杂，依次从属，直到最后限定了文法的两种正规式。文法的学习目前自己只接触到这么多，关于更深层的内容还是需要后面的不断的学习，好好利用这次软考的机会，务实一下基本工，多学习一下基础知识，也是同时为以后做一个铺垫吧。

发表评论取消回复

表情：

评论列表（有 0 条评论，355人围观）

还没有评论，来说两句吧...

相关阅读

相关软考之路（五）---编译原理概念篇

从组成原理到编译原理，都是相互联系的，学习的知识都是在层层推进，顺利成章的，整个软考的所有的知识都可以从计算机的发展（组成原理）--->软件的开发（软件工程）--

╰半橙微兮°/ 2022年08月27日 03:22/ 0 赞/ 195 阅读

相关【软考路上】——编译原理

编译原理在软考中的考点大体上分为以下几点：文法、语法推倒树和算符优先 !

清疚/ 2022年08月07日 09:52/ 0 赞/ 185 阅读

相关【软考总结】——编译原理之文法

学习编译原理的过程中发现文法是一个稍微难理解的知识点，于是小编利用一些时间整理了，如有不对之处还请各位大神给予斧正，不胜感激啊！何为文法？

末蓝、/ 2022年07月16日 00:24/ 0 赞/ 356 阅读

相关软考总结

软考总结软考从开始准备到考试结束，历时两个多月，有整体的计划，我们小组有小组的计划，按着计划就这样准备了两个多月。在大学第一次为了准备这样的考试做了这么有条理的准备。考

逃离我推掉我的手/ 2022年07月15日 10:39/ 0 赞/ 245 阅读

相关编译原理-文法复习

文法的相关概念 > 文法是以有穷的集合刻画无穷的集合的一个工具。 > 语言：是句子组成的集合，是由一组符号所构成的集合 > 语法：是每个句子构成的规则 > 语

亦凉/ 2022年06月01日 11:42/ 0 赞/ 238 阅读

相关软考总结

准备了两个月的软考结束了，也意为着新的学习要开始了，在学习新的东西之前也应该总结一下考试的感慨，在准备软考的这两个月以来有很多的收获。通过考

古城微笑少年丶/ 2022年05月14日 23:13/ 0 赞/ 285 阅读

相关软考总结

软件设计师中级考试，历时差不错两个半月（中间有自学考试学习），说实话，感觉自己并没有太努力，尤其是最后一周，总是打不起精神来。而且这半年，陷入了一个魔咒：每个月必生一病。前前个

小灰灰/ 2022年04月17日 06:21/ 0 赞/ 291 阅读

相关软考总结

软考总结这次算是第几次经历软考呢？上次软考，没有报名，但是一起参与了设计模式的学习。这次是报名参加了，并且几乎参与了所有的一起讨论题目，最大的感触有以下以下两点：一、一

绝地灬酷狼/ 2022年04月17日 02:11/ 0 赞/ 302 阅读

相关软考总结

前言两个多月的软考准备时间终于告一段落，同样的来一篇总结送给过去两个月的自己。正文从去年开始了解软考，知道的就是软考涉及的内容很多，大部分都是自考的内容，认

缺乏、安全感/ 2022年04月17日 02:08/ 0 赞/ 267 阅读

相关软考总结

已经记不清是什么时候开始的软考了，反正这三个月来，一眨眼就过去了，软考还是那个软考，我们已经不是三个月前的我们！准确的来说，我们都变强了，从“小菜”变成了“小鸟”，以后也将

深碍√TFBOYSˉ_/ 2022年04月17日 01:55/ 0 赞/ 326 阅读