我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:ds视讯 > 多义文法 >

应该如何理解「上下文无关文法」?

归档日期:06-27       文本归类:多义文法      文章编辑:爱尚语录

  学编译原理,词法分析阶段学的挺顺利。可是进入到语法分析后,一直涉及到一个概念就是上下文无关文法。搜了一些资料,全部都是数据公式解释的,看不明白。 有人可以通俗的解释下这个概念吗?

  这个文法有两个产生式,每个产生式左边只有一个非终结符S,这就是上下文无关文法,因为你只要找到符合产生式右边的串,就可以把它归约为对应的非终结符。

  这就是上下文相关文法,因为它的第一个产生式左边有不止一个符号,所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”,也就是左边的a和右边的b,所以叫上下文相关文法。

  题主的主要疑惑应该在于:什么是上下文,上下文在哪里?为什么说这个文法上下文无关?

  答案就是:在应用一个产生式进行推导时,前后已经推导出的部分结果就是上下文。上下文无关的意思的,只要文法的定义里有某个产生式,不管一个非终结符前后的串是什么,就可以应用相应的产生式进行推导。(从形式上来看,就是产生式的左边都是单独一个非终结符,即形如 S- ...,而不是非终结符左右还有别的东西,例如 aSb - ...)

  这个文法可以生成如下句子(共 2*2*4=16 种组合,懒得写全了,简单写 7 种意思意思):

  可以看到,其中有一些搭配在语义上是不恰当的,例如“天吃肉”。其(最左)推导过程为:

  但是上下文无关文法里,因为有“V - 吃 下”这样一条产生式,V 就永远都可以推出“吃”这个词,它并不在乎应用“V - 吃 下”这个产生式进行推导时 V 所在的上下文(在这个例子里,就是”天VO“中 V 左右两边的字符串”天“和”O“)。事实上,在 V 推出“吃”这一步,它的左边是“天”这个词,而”天“和”吃“不搭配,导致最后的句子读起来很奇怪。

  那上下文有关文法呢?产生式可以定义为(其中前两条产生式仍是上下文无关的,后四条则是上下文有关的):

  可以看到,这里对 V 的推导过程施加了约束:虽然 V 还是能推出”吃“和”下“两个词,但是仅仅当 V 左边是”人“时,才允许它推导出”吃“;而当 V 左边是”天“时,允许它推导出”下“。这样通过上下文的约束,就保证了主谓搭配的一致性。类似地,包含 O 的产生式也约束了动宾搭配的一致性。

  这样一来,这个语言包含的句子就只有{人吃饭,天下雨,人吃肉,天下雪}这四条,都是语义上合理的。

  其中第三步推导是这样的:非终结符 V 的上文是“人”,因此可以应用“人V - 人吃”这条产生式,得到“人VO - 人吃O”。第四步也类似。

  那么对于 ab 这个串,一种推倒方式是 S - S1 - ab,另一种是 S - S2 - AB - aB - ab。前一种要把 ab 合起来,后一种要分开,这只是说明该文法有歧义,而不能说这是一个上下文有关文法。事实上,还有一些上下文无关语言是固有歧义的(能产生该语言的每一种上下文无关文法都有歧义)。

  在我看来上下文无关的文法是指,文法中不存在aAc-B aAb -C这种情况,即在推导过程中A的产生式体选择不受A左右的文法符号串影响(即abc)

  抛砖引玉,试着用汉语来解释一下。比如这个帖子(用“本来”一词造句,看看谁造的比较有水平。)里面让大家用本来造句,结果有这样的句子:

  如果汉语是上下文无关文法的话,那我们任何时候看见“本来”两个字,都可以把它规约为一个词。可惜汉语不是上下文无关文法,所以“本来”能否归约为一个词,要看它的上下文是什么。上面的三个例子中,第一句里的“本来”可以规约为一个词:

  ((本来)(((这个)(进球))(就)(是)(违例的))),((但)((你)(不肯)(承认)(也)(没办法)))

  看到问题突然想到的思路,不一定对。可以进一步参考这个Context-free grammar,Context-sensitive grammar。总之,我觉得不从学编译的角度思考,而是从自然语言的角度思考更容易理解一些。

  大家分析得真好,其实百科说的很清楚了: V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文

  参见这个:The context sensitivity of Cs grammar

  我也一直纠结于“上下文无关”这个词的理解,总是想不明白到底是跟什么东西“无关”。忽然有一天醍醐灌顶。

  这种文法一般可以画作树形。这里的“上下文”应该指的是某一个节点的兄弟节点!就是说任何一个节点想往下推,只看它自己就行了,跟他的兄弟节点无关。

  比如英译汉!规定文法是friend-朋友,ship-船。那如果是上下文无关的无脑推方法的话,friendship-朋友船!船你MEI啊,友谊的小船吗?说翻就翻!

  PS:这里隐含了另一个例子:friend也不能推出“fri结束”!哈哈。

  PS2:突然感觉,某些翻译软件出的令人啼笑皆非的差错,是不是就是上下文无关无脑推了呢?

  PS3:暴漫熊猫中英文那套表情包,很多都是”上下文无关“无脑翻产生的笑果吧?(另一些可以说是多种情况选错了)【手动滑稽】

  ”无鸭梨“。这个要看的情况多了,甚至得看好长一段,考虑发言的环境是网络还是现实,才能确定是真的说没有鸭梨了,还是”无压力“。

本文链接:http://losmochileros.net/duoyiwenfa/352.html