如何定义上下文无关文法?Context-free grammar是什么?怎样才叫上下文无关呢?

来源：学生作业帮助网 编辑：作业帮 时间：2024/11/15 15:13:15

如何定义上下文无关文法?Context-free grammar是什么?怎样才叫上下文无关呢?
如何定义上下文无关文法?
Context-free grammar是什么?
怎样才叫上下文无关呢?

如何定义上下文无关文法?Context-free grammar是什么?怎样才叫上下文无关呢?
上下文无关文法（Content-Free Grammar,CFG）
在计算机科学中,一个形式文法 G = (N,∑,P,S) 称之为上下文无关的,如果它的产生式规则都取如下的形式：V -> w ,这里 V∈N ,w∈(N∪∑)* .上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文.一个形式语言是上下文无关的,如果它是由上下文无关文法生成的（条目上下文无关语言）.
上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上,几乎所有程序设计语言都是通过上下文无关文法来定义的.另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的.例子可以参见 LR 分析器和 LL 分析器.
BNF （巴克斯-诺尔范式）经常用来表达上下文无关文法.
文法规则使用相似的表示法.名字用斜体表示（但它是一种不同的字体,所以可与正则表达式相区分）.竖线仍表示作为选择的元符号.并置也用作一种标准运算.但是这里没有重复的元符号（如正则表达式中的星号*）,稍后还会再讲到它.表示法中的另一个差别是现在用箭头符号“→”代替了等号来表示名字的定义.这是由于现在的名字不能简单地由其定义取代,而需要更为复杂的定义过程来表示,这是由定义的递归本质决定的.
同正则表达式类似,文法规则是定义在一个字母表或符号集之上.在正则表达式中,这些符号通常就是字符,而在文法规则中,符号通常是表示字符串的记号.我们利用C中的枚举类型定义了在扫描程序中的记号；为了避免涉及到特定实现语言（例如C）中表示记号的细节,就使用了正则表达式本身来表示记号.此时的记号就是一个固定的符号,如同在保留字 while 中或诸如+或:=这样的特殊符号一样,对于作为表示多于一个串的标识符和数的记号来说,代码字体为斜体,这就同假设这个记号是正则表达式的名字（这是它经常的表示）一样.

如何定义上下文无关文法?Context-free grammar是什么?怎样才叫上下文无关呢? 什么是概率上下文无关文法 给出下述语言的上下文无关文法 为什么说每一种上下文无关文法都是上下文有关的 为什么上下文无关文法,可以用下推自动机来识别?一直不太理解! 编译原理,构造上下文无关文法,｛a^nb^ma^mb^n|m,n大于等于0｝ 上下文无关文法适合描述什么规则.很急（编译原理的） 上下文无关文法的问题有一个简单的上下文无关文法：S → aSb | ab; 这个表达式为什么不是正则的?如果要使之满足正则的要求,应该如何修改?为什么?另有一个弱智问题，也望高手指教：如果 形式语言 上下文无关文法 去单一产生式组请问有谁能提供形式语言中的上下文无关文法中的 去单一产生式组的运算方法?将不胜感激. 关于“上下文无关文法”的问题程序语言的大多数语法现象可用上下文无关文法描述.对于一个上下文无关文法G=(N,T,P,S),其中N是非终结符号的集合,T是终结符号的集合,P是产生式集合,S是开始 请定义一个简单的不存在函数的语言,该语言能完成整数的四则运算,并有if、while语句、复合语句及赋值语句请画出该语言所对应的的语法图即可（或者给出改语言所对应的上下文无关文法）- 编译原理：构造产生此语言的上下文无关文法G有语言L(G)={adaR | a∈(a,b)*,aR 为a之逆},试构造产生此语言的上下文无关文法Gdos62可不可以来点注释哦? 编译原理 上下文无关文法1.画出一个最简的确定有限自动机,它接受所有大于101的二进制整数.2.写出与(1)中DFA等价的上下文无关文法第一题已经有答案,请解答第二题. context上下文作用写代码经常要获取上下文,请问上下文的作用是? context context android开发中的几种上下文有什么区别,他们是否相同比如context Activity.this ,getApplicationContext 这几种上下文分别的用法.还有为什么在new ProgressDialog(Context context)的时候,传的上下文不能用getApplica 2个文法定义了同一个一个语言,2个文法是什么关系