编译原理中四种文法语言的基本概念

青旅半醒 2022-06-15 07:46 189阅读 0赞

马上就要编译原理的考试了，看了看去年试卷，做几道题，发现自己对文法的概念都很模糊，下面整理了一下四种文法的基本概念：

那么什么是文法呢？乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。多数程序设计语言的单词的语法都能用正规文法或3型文法来描述。3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：A→aB或A→a其中A，B∈VN ，a∈VT\*，另一种形式是：A→Ba或A→a，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT\*上的正规集。四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。

从形式上文法是一个四元式（VN,VT,P,S）

VN为非终结符的集合 　　 如：动词

VT为终结符的集合　　　　如：动词->eat（eat不可分解，则为终结符）

P文法规则的集合

S开始符号

闭包的概念：

如果VN为\{主语，谓语\}

则VN的星闭包（就是普通闭包）为\{空串，主语谓语谓语主语，主语谓语，谓语主语....\}

VN里面各种各样的组合

正闭包则是除开空串的闭包。

小结：

**上下文有关文法就是1型文法**

**上下文无关文法就是2型文法**

**正规文法就是3型文法**

4类文法限制是逐渐增加的：

0型文法（短语文法或无限制文法），识别0语言的机器叫做图灵机

定义：P中产生式a-->b，其中a属于V正闭包且至少含有一个非终结符,b属于V星闭包

注：任何0型文法都是可递归可枚举的

对0型文法作某些限制，可以得到其他文法的定义

1型文法（上下文有关文法），线性界限自动机

增加的限制：除了S产生空串之外，产生式的右部长度要大于等于左部，S不能出现在右部，

非终结符不能产生空串。

例如：aAb-->ayb(在某种条件下A转换为y，所以称为上下文有关)

2型文法（上下文无关文法），下推自动机

增加的限制：P中只有A->b，而不是a->b，产生式左边只能有一个非终结符。

3型文法（正规文法），有限状态自动机

增加的限制：产生式的右边非终结符的位置要么在最左边要么在最右边而且最多只能有一个

在左端则称左线性文法，在右端则称右线性文法

对比：

四种文法之间的关系是随着型号的增加，对语言的限制条件就越来越大

条件如下：

0型文法　: 产生式左右两边都可以出现任意符号串

1型文法　: 产生式的左边可以有终结符的出现，产生式右边是任意符号串

2型文法　：产生式的左边是非终结符，产生式的右边是任意符号串

3型文法　：产生式的左边是非终结符，产生式的右边非终结符的位置要么在最左边要么在最右边而且最多只能有一个

如：A-->aB | d

A-->Ba | d

发表评论取消回复

表情：

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

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

相关阅读

相关编译原理（四）自顶向下语法分析方法、LL(1)文法的判别、非LL(1)文法转换为LL(1)文法

本文要点 1. 理解 “能使用自顶向下分析技术的文法必须是LL(1)文法” 2. LL(1)文法的充要条件 3. LL(1)文法的判别 4. 某些非LL(1)文

柔光的暖阳◎/ 2023年02月18日 14:29/ 0 赞/ 9 阅读

相关编译原理（二）文法和语言、符号和符号串、文法的类型、语法树

要点： 1. 符号和符号串的相关概念 2. 文法和语言的形式定义 3. 文法的类型 4. 上下文无关文法及其语法树 5. 上下文无关文法的句型分析 6. 有关文法

本是古典何须时尚/ 2023年02月18日 05:28/ 0 赞/ 42 阅读

相关 Elasticsearch 基本原理和概念（四）

今天和大家分析es基本原理和概念：从上面的例子中，我们看到了很多熟悉又陌生的概念，比如索引、文档等等。这些概念和我们平时看到的数据库里的比如索引有什么区别呢？举个例子

柔情只为你懂/ 2022年12月13日 04:59/ 0 赞/ 398 阅读

相关编译原理：结合例题彻底理解文法四元式与正则文法

这篇博客起源于一道很有趣的正则文法的题目。题目描述如下： > 已知L=\{x|x∈\{0,1\}\+，且x中含有1011子串\}。 > 构造接收语言L的正则文法。什么

小鱼儿/ 2022年12月08日 05:07/ 0 赞/ 162 阅读

相关编译原理教程_2 文法和语言

> 文章下载地址 > https://gitee.com/fakerlove/fundamentals-of-compiling 文章目录 2. 文法和语言

迈不过友情╰/ 2022年11月10日 03:47/ 0 赞/ 906 阅读

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

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

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

相关编译原理中四种文法语言的基本概念

马上就要编译原理的考试了，看了看去年试卷，做几道题，发现自己对文法的概念都很模糊，下面整理了一下四种文法的基本概念：那么什么是文法呢？乔姆斯基把文法分成四种类型，即0型、1

青旅半醒/ 2022年06月15日 07:46/ 0 赞/ 190 阅读

相关编译原理-文法复习

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

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

相关编译原理之词法分析（Pl/0语言文法）

文法： Pl/0语言文法的BNF表示：〈程序〉→〈分程序〉. 〈分程序〉→ \[<常量说明部分>\]\[<变量说明部分>\]\[<过程说明部分>\]〈语句〉 <常量

向右看齐/ 2022年04月17日 05:13/ 0 赞/ 343 阅读

相关《编译原理》文法 - 终结符和非终结符

《编译原理》文法 - 终结符和非终结符终结符和非终结符在编译原理的文法部分是出现得最多的概念，但由于在熟悉编译原理的人看来，这是个不值一提的简单概念，所以一般书上

灰太狼/ 2022年02月28日 01:40/ 0 赞/ 463 阅读