什麼是上下文無關文法？

語法 - 它是一套規則，用於檢查字串是否屬於特定語言。

一個程式由各種字串組成。但是，並非每個字串都是一個正確或有意義的字串。因此，為了識別語言中的有效字串，應該指定一些規則來檢查字串是否有效。這些規則就是構成語法。

示例 - 在英語中，語法檢查字串是否可接受，即檢查名詞、動詞、副詞等是否按正確的順序排列。

上下文無關文法

它是一種用於指定語言語法的符號。上下文無關文法用於設計解析器。

詞法分析器生成一系列標記，這些標記被傳遞給解析器以構建語法樹。但在構建語法樹之前，這些標記將被分組，以便分組的結果是語言的有效結構。因此，為了指定語言的結構，使用了一種合適的符號，這種符號應該精確且易於理解。這種符號就是上下文無關文法。

正式地，上下文無關文法 (G) 可以定義為 -

它是 4 元組 (V,∑,P,S)

  • V 是一組非終結符或變數。
  • ∑ 是一組終結符。
  • P 是一組產生式或規則集。
  • S 是起始符號。

如果每個產生式 (P) 都是 A → α 的形式，其中 A∈V 且 α ∈(V∪ ∑ )*，則 G 是上下文無關的。

示例 1 - 為語言編寫語法

L={an|n≥1}

解決方案

Let G=(V,Σ,P,S)
V = {S}
Σ={a}
P = {
   S→aS
   S→a
}

這些產生式生成語言 an。

i.e., S ⇒ a
S ⇒ a S ⇒ a a or a2
S ⇒ a S ⇒ a a S ⇒ a a a or a3
.
.
.
S ⇒ a S ⇒ a a S ⇒ a a a S ⇒ ... ⇒ an

在上下文無關文法中，變數或非終結符出現在 →（箭頭）的左側。這些符號將被擴充套件，直到生成所有終結符。

終結符是在語言中使用的標記。

示例 2 - 找出由語法生成的語言。

G=({S},{a,b}{S → a S b,S → a,b},S)

解決方案

S ⇒ a $\underline{S}$ b

⇒ a $\underline{aSb}$ b

⇒ a a a $\underline{S}$ b b b

⇒ a a a a S b b b b

………………………

⇒ an−1$\underline{S}$ bn−1

⇒ an−1 $\underline{a\:b}$ bn−1

⇒ an bn

∴ 語言 L= {an bn| 𝑛≥2}

示例 3 - 寫下生成所有整數的 CFG G。

解決方案

G=(V,∑,P,S)

V = {S, <sign>, <digit>, <integer>}

Σ = {0, 1, 2, 3,……………………..9, +, - }

$ P= \begin{Bmatrix} \:\:\:\:S → <sign> <integer>\ \:\:\:\:\:\:\:\:<sign>→ +|−\ <integer> → <digit> <integer>|<digit>\ \:\:\:\: <digit> → 0 | 1 | 2 | 3…………|9 \end{Bmatrix} $

例如，- 12 的推導由 - 給出

S ⇒ <sign> <integer>
⟹ −<integer>
⟹ −<digit> <integer>
⟹ −1<integer>
⟹ −1<digit>⟹−12.

更新於: 2021 年 10 月 26 日

5K+ 次檢視

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告