上下文无关文法产生的语言都可以用正则文法来描述_c语言结构体默认值

上下文无关文法产生的语言都可以用正则文法来描述_c语言结构体默认值对于文法G=(V,T,S,P),如果产生式的形式如下:A->xBA->x其中A,B属于V,x属于T*,则称为右线性文法;相似的,如果产生式的形式如下:A->BxA->x则称为左线性文法。右线性文法和左线性文法统称为正则文法。正则表达式的表达能力等价于正则文法,正则表达式的定义如下:字母表中的任意字母是正则表达式,空串和空集也是正则表达式;如果r,s…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

对于文法G=(V, T, S, P),如果产生式的形式如下:

A -> xB

A -> x

其中A, B属于V,x属于T*,则称为右线性文法;相似的,如果产生式的形式如下:

A -> Bx

A -> x

则称为左线性文法。右线性文法和左线性文法统称为正则文法。

正则表达式的表达能力等价于正则文法,正则表达式的定义如下:

字母表中的任意字母是正则表达式,空串和空集也是正则表达式;

如果r, s是正则表达式,那么r|s, rs, r*, (r)也是正则表达式。

正则表达式的扩展:

r+:一个或多个重复

.  :任意字符

[a-z]:字符范围

[^abc]:不在给定集合中的任意字符

r?:可选

正则表达式只能使用终结符(字母表中的字符),因而很容易变得复杂又难懂,实际中,经常使用正则描述,正则描述允许使用非终结符定义表达式,很像EBNF,但是它限制在未完全定义之前,不能使用非终结符,也就是说不允许递归或自嵌套。

像正则表达式的表达能力等价于正则文法一样,BNF范式的表达能力等价于上下文无关文法。BNF是“Backus Naur Form”的缩写。John Backus和Peter Naur首次引入一种形式化符号来描述给定语言的语法。

BNF的元符号:

::=表示“定义为”,有的书上用–>|表示“或者”< >尖括号用于括起非终结符。

BNF的扩展EBNF:

可选项被括在元符号“[”和“]”中

重复项(零个或者多个)被括在元符号“{”和“}”中

仅一个字符的终结符用引号(“)引起来,以和元符号区别开来

上述操作符不是严格限定的,有的人喜欢直接使用扩展正则表达式的操作符描述EBNF。除了方便表达以外,引入EBNF的另一个主要原因是为了更紧密地把文法映射到递归下降分析程序的真实代码。当需要手动构造归下降分析程序的时候,通常把上下文无关文法改写为EBNF是必需的。

如果一个上下文无关文法G不是自嵌套或自递归的,即不存在如下推导:

U =>* xUy

那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上,一个上下文无关文法是严格的,既不可能由正则文法产生,当且仅当该语言的一切文法都是自嵌套的。

如果一个上下文无关文法G不是自嵌套或自递归的,即不存在如下推导:

U =>* xUy

那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上,一个上下文无关文法是严格的,既不可能由正则文法产生,当且仅当该语言的一切文法都是自嵌套的。

BNF的扩展EBNF:

可选项被括在元符号“[”和“]”中

重复项(零个或者多个)被括在元符号“{”和“}”中

仅一个字符的终结符用引号(“)引起来,以和元符号区别开来

上述操作符不是严格限定的,有的人喜欢直接使用扩展正则表达式的操作符描述EBNF。除了方便表达以外,引入EBNF的另一个主要原因是为了更紧密地把文法映射到递归下降分析程序的真实代码。当需要手动构造归下降分析程序的时候,通常把上下文无关文法改写为EBNF是必需的。

如果一个上下文无关文法G不是自嵌套或自递归的,即不存在如下推导:

U =>* xUy

那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上,一个上下文无关文法是严格的,既不可能由正则文法产生,当且仅当该语言的一切文法都是自嵌套的。

如上所述,上下文无关文法的递归性,对其分析方法也有很大影响。首先,用作识别这些结构的算法必须使用递归调用或显式管理的分析栈。其次,用作表示语言语义结构的数据结构现在也必须是递归的(通常是一颗分析树),而不再是线性的(如同用于词法和记号中的一样)了。

在程序设计语言中,通常用正则表达式描述词法规则。但是正则表示式的表达能力有限,她无法表达括号配对等语法形式,因而,需要引入表达能力更强的上下文无关文法。编译程序中常用正则文法表示词法,用上下文无关文法表示语法。那么程序语言中那些属于词法哪些属于语法呢?一个简单的办法,把所有能用正则文法表示的规则成为词法,即我们用尽可能的使用正则文法表示更多的东西,那些无法用正则表示式表示的成为句法,如C语言中的{ statement; }语法形式。语言中有些规则使用上下文无关文法仍然无法描述,例如变量的定义在使用之前,类型匹配等等,这些通常称为(静态)语义,它们在编译程序的静态语义检查阶段进行检测。

如果一个上下文无关文法G不是自嵌套或自递归的,即不存在如下推导:

U =>* xUy

那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上,一个上下文无关文法是严格的,既不可能由正则文法产生,当且仅当该语言的一切文法都是自嵌套的。

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

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

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

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

(0)


相关推荐

  • 图像基础知识之YUV

    图像基础知识之YUV一、YUV常用格式YUV是编译true-color颜色空间(colorspace)的种类,Y'UV,YUV,YCbCr,YPbPr等专有名词都可以称为YUV,彼此有重叠。“Y”表示明亮

  • 使用Taro小程序框架开发一个学习、刷题、论坛、聊天交流的微信小程序

    使用Taro小程序框架开发一个学习、刷题、论坛、聊天交流的微信小程序项目介绍当代大学生上课缺少积极性,学习缺乏效率。同为大学生的我深有体会。所以特别开发出这样一款学习类的微信小程序帮助学生进行学习、巩固知识,同时增加对战PK模块来加强学生们的学习积极性。这是一个为学生提供在线学习课程、题库练习、考试答题、做题PK、上课签到、资料查阅、成绩分析等功能的微信小程序希望大佬们走过路过给个star~技术选型前端:Taro+微信小程序+Echarts后端:…

  • 详解 & 0xff 的意义及作用

    详解 & 0xff 的意义及作用首先我们要都知道,&表示按位与,只有两个位同时为1,才能得到1,0x代表16进制数,0xff表示的数二进制11111111占一个字节.和其进行&操作的数,最低8位,不会发生变化.下面着重来说说&0xff都有哪些应用:1.只是为了取得低八位通常配合移位操作符>>使用例如:javasocket通信中基于长度的成帧方法中,如果发送的信息长度小于65535字节,长度信息的字节定义为两个字节长度。这时候将两个字节长的长度信息,以Big-Endian的

  • mysql一主多从 读写分离_mysql读写分离原理

    mysql一主多从 读写分离_mysql读写分离原理简介:什么是主从复制,如何实现读写分离,看这篇你就懂了!思维导图文章已收录到我的Github精选,欢迎Star:https://github.com/yehongzhi/learningSummary前言在很多项目,特别是互联网项目,在使用MySQL时都会采用主从复制、读写分离的架构。为什么要采用主从复制读写分离的架构?如何实现?有什么缺点?让我们带着这些问题开始这段学习之旅吧!为什么使用主从复制、读写分离主从复制、读写分离一般是一起使用的。目的很简单,就是为了提高数据库的并发性能。你想,假设是单机,读

  • Ubuntu 18.04通过deb安装cuda 10.2

    Ubuntu 18.04通过deb安装cuda 10.2wgethttps://developer.download.nvidia.com/compute/cuda/repos/ubuntu1804/x86_64/cuda-ubuntu1804.pinsudomvcuda-ubuntu1804.pin/etc/apt/preferences.d/cuda-repository-pin-600wgethttps://developer.download.nvidia.com/compute/cuda/10.2/Prod/local_installer

  • top命令查看内存信息_ubuntu查看cpu信息

    top命令查看内存信息_ubuntu查看cpu信息top命令是Linux下常用的性能分析工具,能够实时显示系统中各个进程的资源占用状况,类似于Windows的任务管理器。top显示系统当前的进程和其他状况,是一个动态显示过程,即可以通过用户按键来不断刷新当前状态.如果在前台执行该命令,它将独占前台,直到用户终止该程序为止.比较准确的说,top命令提供了实时的对系统处理器的状态监视.它将显示系统中CPU最“敏感”的任务列表.该命令可以按CPU使…

发表回复

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

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