前言
在研究自然語言時，人們發(fā)現(xiàn)名詞、動詞辛蚊、介詞以及它們的短語之間存在著自然的遞歸關(guān)系，因此引入了 上下文無關(guān)文法(CFG) 來幫助整理和理解這種關(guān)系真仲。同時袋马，上下文無關(guān)文法在程序設(shè)計語言的規(guī)范化及編譯中有重要應用。設(shè)計人員在編寫程序設(shè)計語言的編譯器和解釋器時袒餐，通常需要先獲取該語言的文法飞蛹，因此在大多數(shù)的編譯器和解釋器中都包含了一個 語法分析器 上祈。與上下文無關(guān)文法相關(guān)的語言集合稱為 上下文無關(guān)語言(CFL)圃验。
上下文無關(guān)語法概述
給出一個上下文無關(guān)語法的示例予权，稱其為 :
一個文法是由一組 替換規(guī)則 或稱 產(chǎn)生式 組成过咬；每條規(guī)則占一行坊谁，由一個符號和一個字符串構(gòu)成蒿讥，中間用箭頭隔開柄粹；符號稱為 變元墙懂，字符串則由變元和另一種稱為 終結(jié)符 的符號構(gòu)成匕积，通常第一條規(guī)則的左邊的變元被指定為 起始變元 盈罐；則文法 有3條規(guī)則，
和
是變元闪唆，其中
是起始變元盅粪，
和
是終結(jié)符；
按照以下方法悄蕾，能夠根據(jù)文法生成其所描述的語言的每一個字符串：
- 寫下起始變元
- 取一個已寫下的變元票顾，并找到該變元開始的規(guī)則，把這個變元替換成規(guī)則右邊的字符串
- 重復步驟2帆调，直到寫下的字符串中沒有變元為止
例如奠骄，文法 生成的字符串
。獲取一個字符串的替換序列稱為 派生番刊；文法
生成字符串
的派生過程如下：
用上述方式生成的所有字符串構(gòu)成該 文法的語言含鳞；用 表示文法
的語言，可以得出
{
}芹务，該語言稱為 上下文無關(guān)語言 蝉绷；通常對于
和
可以合并為
上下文無關(guān)文法形式化定義
-
有窮 變元 集
-
有窮 終結(jié)符 集
-
有窮 規(guī)則 集 （形如
）
-
初始變元
設(shè) 和
是由變元及終結(jié)符構(gòu)成的字符串鸭廷，
是文法的一條規(guī)則，稱
生成
潜必，記作
靴姿。如果
沃但，或者存在序列
磁滚，使得
其中 ，則稱
派生
宵晚，記作
垂攘。該語言的文法是 {
}；
