永发信息网

正规文法产生的语言都可以用上下文无关文法来描述

答案:2  悬赏:0  手机版
解决时间 2021-03-22 02:25
正规文法产生的语言都可以用上下文无关文法来描述
最佳答案
是对的吧~
全部回答
对于文法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)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上,一个上下文无关文法是严格的,既不可能由正则文法产生,当且仅当该语言的一切文法都是自嵌套的。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
职业资格证书,全国信息化专业技能证书,特种
请问谁知道这个字“贡"是什么字?什么意思?
小学三年级下期评语,小学三年级的家长意见怎
pads2005 里 如何画腰孔
丝尚美业地址在什么地方,想过去办事
我有张99年的100人民币尾数666888价值多少钱
可否评价一下基德的nba历史地位及职业生涯
Camp Xtreme is the biggest adventure camp
想全面了解世界历史,应该买哪本历史书
AMD Phenom(羿龙) 9150e 四核装w7怎么样
虚心求教:公路工程试验检测员具体在什么样的
绿泽园地址在什么地方,想过去办事
推荐四川自贡知名律师是谁?急急急!
大众速腾汽车娱乐导航系统1.11版本好刷机吗?
爱与教育标语,爱的教育中100句优美语句
推荐资讯
北京中医药大学博士生入学考试科目
跟摩天轮有关的句子,关于摩天轮有关的绝美爱
古代打仗治不好的伤兵是否就地掩埋
忽儿什么忽儿什么忽儿什么 写排比句
金猴专卖在哪里啊,我有事要去这个地方
今天晚上同房,需要吃避孕药吗?
君子兰养多少年开花
diong是什么?
关于山间的古诗词,描写早晨的山中的段落
钡餐检查多少钱,说不能检查,我要做全消化道
凯乐湘园东门(人行门)在什么地方啊,我要过去
单选题方仲永自幼智力超群,5岁时就能作出超
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?