基本介紹
- 中文名:上下文無關文法
- 外文名:context-free grammar
- 縮寫:CFG
上下文無關文法(英語:context-free grammar,縮寫為CFG),在計算機科學中,若一個形式文法G = (N, Σ, P, S) 的產生式規則都取如下的形式:V->w,則謂之。...
隨機上下文無關文法(英語:Stochastic context-free grammar),即在上下文無關文法中,為每一個產生式規則賦予一個機率,標示套用一個產生式規則的可能性。...
上下文有關文法的概念是諾姆·喬姆斯基在1950年代作為描述自然語言的語法的一種方式介入的,在自然語言中一個單詞是否可以出現在特定位置上要依賴於上下文。可以被上下文...
在形式文法理論中,確定上下文無關文法(DCFG)是上下文無關文法的真子集。...... 確定上下文無關文法是確定下推自動機可識別的文法。確定上下文無關語言是確定上下文...
上下文無關語言是可以用上下文無關文法定義的形式語言。所有上下文無關語言的集契約一於下推自動機所接受的語言的集合。...
上下文無關解析就是對無關上下文的分析。...... 程式語言真的是上下文無關語言嗎? 已經有兩種方法,可以從文法G構建一個決策過程,回答字元串W是否屬於L(G)的問...
正規文法所描述的是VT*上的正規集。四個文法類的定義是逐漸增加限制的,因此每一種正規文法都是上下文無關的,每一種上下文無關文法都是上下文有關的,而每一種...
二型文法,又稱上下文無關文法,擁有足夠強的表述力來表示絕大多數程式設計語言。...... 二型文法,又稱上下文無關文法,擁有足夠強的表述力來表示絕大多數程式設計語...
解析表達文法看起來與正則表達式和巴科斯範式的上下文無關文法(CFG)很像,但是表達的意思不同。和CFG不同的是,PEG不能有二義性;解析一個字元串的時候,這個字元串...
在變換文法中,句子深層結構和表層結構之間的變換是通過變換規則實現的,變換規則把句子從一種結構變換為另一種結構。變換文法的工作過程是先用上下文無關文法建立相應...
3、上下文無關文法這種文法是說,不論上下文如何A都可以用 來替換4、正規文法正規文法是最常用的一種文法。四種分類的關係圖:分類關係圖 ...
設G =(VN,VT,P,S)為一文法,若中的每一個產生式均滿足|β|>=|α|,僅僅α→ε除外,則文法G是1型或上下文有關的。* 2型文法(上下文無關文法)(context...
樹-鄰接文法(TAG)是 Aravind Joshi 定義的文法形式化。樹-鄰接(adjoining)文法在某種意義上類似於上下文無關文法,但是基本的重寫單位是樹而不是符號。上下文無關...
這種文法規定的語言可以被線性有界非確定圖靈機接受。 2-型文法(上下文無關文法)生成上下文無關語言。這種文法的產生式規則取如A-> γ 一樣的形式。這裡的A是...
單詞序列組合成各類語法短語,如“程式”,“語句”,“表達式”等等.語法分析程式判斷源程式在結構上是否正確.源程式的結構由上下文無關文法描述.語法分析程式可以用...
AB語法和上下文無關文法的等價性由Bra-Hillel等人(1960)證明,這種範疇語法的形式化因為只包含兩條函項套用規則,因此具有一定的局限性。組合規則:...
在計算機科學中,聲稱一個上下文無關文法是Greibach 標準式(範式)(GNF)的意味著所有的產生規則都有如下形式: a->αX或 s->ε 這裡的 A 是非終結符,α 是...
4.2.4 語法分析樹和推導4.2.5 二義性4.2.6 驗證文法生成的語言4.2.7上下文無關文法和正則表達式4.2.8 4.2節的練習4.3 設計文法...
一個形式語言是上下文無關的,如果它是由上下文無關文法生成的﹙條目上下文無關語言﹚。 上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程式設計...
3.3 語言與文法簡介3.3.1 正規式與上下文無關文法3.3.2 上下文有關文法3.3.3 形式語言與自動機簡介3.4 自上而下語法分析...
由1型文法產生的語言稱為1型語言或上下文有關語言。1型語言恰是非確定型線性有界自動機所識別的語言類。③2型文法。又稱為上下文無關文法。這種文法要求生成式a...
PCFG(Probabilistic Context Free Grammar),機率上下文無關文法,或稱為SCFG(Stochastic Context Free Grammar),隨機上下文無關文法。...
喬姆斯基後來把這些解釋為對來自標記系統的上下文無關文法產物的操作。哈里斯的政治觀點對喬姆斯基政治立場的形成產生了重要影響。1949年,喬姆斯基和語言學家“卡羅爾·...
擴展巴科斯-瑙爾範式(EBNF)是表達作為描述計算機程式語言和形式語言的正規方式的上下文無關文法的元語法符號表示法。它是基本巴科斯範式(BNF)元語法符號表示法的一種...
所有Kuroda 範式的文法都是單調的,因此生成上下文有關語言。反過來說,所有不生成空串的上下文有關語言都可以被 Kuroda 範式的文法所生成。...
縮寫為CYK algorithm)是由約翰·科克,Younger和嵩忠雄共同研究出來大約發表於1965年的一個算法,它是一個用來判定任意給定的字元串 是否屬於一個上下文無關文法的...