编译原理之文法

编译原理之文法编译原理之文法

大家好,又见面了,我是你们的朋友全栈君。

文法(Grammar)

 

G={VTVNSP}

 

VT是一个非空有限的符号集合,它的每个元素称为终结符号Terminal

 

VN是一个非空有限的符号集合,它的每个元素称为非终结符号(Non-Terminal

 

SVN,称为文法G开始符号

 

P是一个非空有限集合,它的元素称为产生式

 

VTVN=∅

产生式,其形式为αβα称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且αβ∈(VTVN) *αε,即αβ是由终结符和非终结符组成的符号串。

开始符S必须至少在某一产生式的左部出现一次。

另外可以对形式αβαγ的产生式缩写为αβ|γ,以方便书写。

 

解释:

(VTVN) *:也就是VTVNKleene闭包

αεα不等于空符号串

用小写字母代表终结符,如:abc……,不能被拆分

用大写字母代表非终结符,如:ASBX……,可以被拆分

    著名语言学家NoamChomsky(乔姆斯基)根据对产生式所施加的限制的不同,把文法分成四种类型,即0型、1型、2型和3型。


文法类型

产生式的限制

文法产生的语言

0型文法

αβ

其中αβ∈(VTVN) *,∣α∣≠0

0型语言

1型文法

αβ

其中αβ∈(VTVN) *,∣α∣≤∣β

1型语言,即上下文有关语言

2型文法

Aβ

其中AVNβ∈(VTVN) *

2型语言,即上下文无关语言

3型文法

A→α|αB(右线性)A→α|Bα(左线性)

其中,ABVNαVT{
ε}

3型语言,即正规语言,

又分为左线性语言和右线性语言

 

0型文法:α∈(VTVN) * 且至少含有一个非终结符,而β∈(VTVN) *

                       例:A→a,Aa→a,aA→a(左边至少有一个大写字母)


1型文法:有一特例:αε也满足1型文法。

         例:A→a,A→ab,Aa→BAc(左边至少有一个大写字母,且左边的长度小于等于右边的长度)


2型文法:每一个Aβ都有A非终结符

        例:A→a,A→ab,AB→BAc(在1型文法的前提下,左边必须都是大写字母)


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型方法的要求了。

例子:A→ab,A→aB,B→a,B→cB中的A→ab不符合3型文法的定义,如果把后面的ab,改成aB(即“一个非终结符+一个终结符”)就对了。

例子:A→a,A→Ba,B→a,B→cB中如果把B→cB改为B→Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。

 

如果所有终端结点都是与终结符关联的,每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型,则该字符串是文法G的一个句子,此时该推导树是完全推导树

如:文法G={a,b}{S,A},S,P,其中:SaAS|a,ASbA|SS|ba,句型aabAa相对应的构造树。

 

解释:

文法G={VTVNSP},即VT={a,b}VN={S,A}

SaAS|a,即SaASSa

ASbA|SS|ba,即ASbAASSAba

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/105720.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • MDK 生成BIN文件 最简单方式「建议收藏」

    MDK 生成BIN文件 最简单方式「建议收藏」如图中所示,一行命令就可以了。fromelf.exe–bin-o..\Output\@p.bin..\Output\@p.axf

    2022年10月20日
  • 详解RPN网络[通俗易懂]

    详解RPN网络[通俗易懂]引言RPN(RegionProposalNetwork)是Faster-RCNN网络用于提取预选框(也就是RCNN中使用selectivesearch算法进行RegionProposal的部分),我们知道RCNN及Fast-RCNN中一个性能瓶颈就是提取预选框的部分,而RPN很好地对这个部分进行了优化,原因在于它将卷积神经网络引入了进来,使用特征提取的形式生成出预选框的位置从而降低了selectivesearch算法带来的计算时间上的开销。RPN(RegionProposalNetwor

  • pycharm双击但是无法打开的情况_mac电脑上pycharm怎么安装

    pycharm双击但是无法打开的情况_mac电脑上pycharm怎么安装本来pycharm用的好好地,电脑重启之后,突然就打不开了,双击没反应,重新安装也解决不了,百度找不到结果,就去google了。https://intellij-support.jetbrains.com/hc/en-us/community/posts/115000120784-Can-t-open-IntelliJ-on-MacOs有兴趣的小伙伴可以看这个。主要意思就是,用命令行…

  • WPF数据采集与监控系统实战开发全记录【附源码 典藏版】[通俗易懂]

    WPF数据采集与监控系统实战开发全记录【附源码 典藏版】[通俗易懂]作为B站学习区非知名Up主,本人酷爱沉迷上位机无法自拔!人称”上位机大王“(滑稽)长期为大家提供各类WPF/上位机学习干货是我的信条!元旦在即,我又连肝一周,录制了一批WPF数据采集与监控系统项目开发实战!!录制内容,从上位机应用基础架构出发,全程代码实战,涉及内容包括串口通信、基础组件开发、用户控件动画、全局静态数据绑定等等。从无到有,完整实操,项目整体以MVVM思想模式设计开发,代码功能使用分层结构,逻辑与View解耦。认真看完全部视频,你可以了解到基本的串口通信方式,以及如何利用WPF的特性开发

  • 软件开发-快递来了-开发第一天「建议收藏」

    软件开发-快递来了-开发第一天「建议收藏」今天是“快递来了”软件开发的第一天,大家大体上分配了今明两天的计划,这几天主要以安装配置安卓开发环境,学习安卓特性组件为主。今天,安装调试了AndroidStudio,深刻体会到了集成开发环境的优

  • ACCESS打得开mdb,但打不开表,弹框提示未知错误。

    ACCESS打得开mdb,但打不开表,弹框提示未知错误。

    2021年11月17日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号