導覽
近期變更
隨機頁面
新手上路
新頁面
優質條目評選
繁體
不转换
简体
繁體
3.147.205.14
登入
工具
閱讀
檢視原始碼
特殊頁面
頁面資訊
求真百科歡迎當事人提供第一手真實資料,洗刷冤屈,終結網路霸凌。
檢視 上下文无关文法 的原始碼
←
上下文无关文法
前往:
導覽
、
搜尋
由於下列原因,您沒有權限進行 編輯此頁面 的動作:
您請求的操作只有這個群組的使用者能使用:
用戶
您可以檢視並複製此頁面的原始碼。
{| class="wikitable" align="right" |- | style="background: #008080" align= center| '''<big>上下文无关文法</big> ''' |- | [[File:20200413110701610.png|缩略图|居中|[https://img-blog.csdnimg.cn/20200413110701610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjIyMTY1Nw==,size_16,color_FFFFFF,t_70 原图链接][https://blog.csdn.net/weixin_42221657/article/details/105484144来自 搜狗 的图片]]] |- | style="background: #008080" align= center| |- | align= light| |} 上下文无关文法(英语:context-free grammar,缩写为CFG),在计算机科学中,若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式:V w,则谓之。其中 V∈N ,w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换,而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的,如果它是由上下文无关文法生成的(条目上下文无关语言)。 上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法;实际上,几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL [[分析器]]。 BNF(巴克斯-诺尔范式)经常用来表达上下文无关文法。 =='''目录'''== '''形式定义''' '''例子''' '''范式''' =='''形式定义'''== 上下文无关文法 G 是 4-元组: '''这里的''' 1. 是“非终结”符号或变量的有限集合。它们表示在句子中不同类型的短语或子句。 2. 是“终结符”的有限集合,无交集于 ,它们构成了句子的实际内容。 3. 是开始变量,用来表示整个句子(或程序)。它必须是 的元素。 4. 是从 到 的关系,使得 。 此外, 是有限集合。 的成员叫做文法的“规则”或“[[产生式]]”。星号表示Kleene星号运算。 '''补充定义 1''' 对于任何字符串 ,我们称 生成 ,写为 ,如果 使得 且 。因此 是应用规则 于 的结果。 补充定义 2 对于任何 (或 在某些教科书中),如果 使得 。 补充定义 3 文法 的语言是集合 补充定义 4 语言 被称为是上下文无关语言(CFL),如果存在一个 CFG 使得 。 例子 例子 1 一个简单的上下文无关文法的例子是:S aSb | ab 。这个文法产生了语言 {anbn : n ≥ 1} 。不难证明这个语言不是正则的。 例子 2 这个例子可以产生变量 x,y,z 的算术表达式: S T + S | T - S | T T T * T | T / T | ( S ) | x | y | z 例如字串 "( x + y ) * x - z * y / ( x + x )" 就可以用这个文法来产生。 例子 3 字母表 {a,b} 上 a 和 b 数目不相等的所有字串可以由下述文法产生: S U | V U TaU | TaT V TbV | TbT T aTbT | bTaT | ε 这里 T 可以产生 a 和 b 数目相等的所有字串,U 可以产生 a 的数目多于 b 的数目的所有字串, V 可以产生 a 的数目少于 b 的数目的所有字串。 推导与语法树 最左推导 如文法: S--->AB A--->a|t<ref>[https://www.docin.com/p-815144901.html 上下文无关文法],搜狗, 2017-02-13</ref> B---->+CD C--->a D---->a 那么最左推导为: S---->AB----->aB--->a+CD--->a+aD----->a+aa 3范式 每一个不生成空串的上下文无关文法都可以转化为等价的 Chomsky 范式或 Greibach 范式。这里两个文法等价的含义指它们生成相同的语言。 由于 Chomsky 范式在形式上非常简单,所以它在理论和实践上都有应用。比如,对每一个上下文无关语言,我们可以利用 Chomsky 范式构造一个多项式算法,用它来判断一个给定字串是否属于这个语言(CYK算法)。 =='''参考资料'''== {{Reflist}} [[Category:540 社會學總論]]
此頁面使用了以下模板:
Template:Main other
(
檢視原始碼
)
Template:Reflist
(
檢視原始碼
)
模块:Check for unknown parameters
(
檢視原始碼
)
返回「
上下文无关文法
」頁面