什么是上下文无关文法？

语法 - 它是一套规则，用于检查字符串是否属于特定语言。

一个程序由各种字符串组成。但是，并非每个字符串都是一个正确或有意义的字符串。因此，为了识别语言中的有效字符串，应该指定一些规则来检查字符串是否有效。这些规则就是构成语法。

示例 - 在英语中，语法检查字符串是否可接受，即检查名词、动词、副词等是否按正确的顺序排列。

上下文无关文法

它是一种用于指定语言语法的符号。上下文无关文法用于设计解析器。

词法分析器生成一系列标记，这些标记被传递给解析器以构建语法树。但在构建语法树之前，这些标记将被分组，以便分组的结果是语言的有效结构。因此，为了指定语言的结构，使用了一种合适的符号，这种符号应该精确且易于理解。这种符号就是上下文无关文法。

正式地，上下文无关文法 (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+ 次查看

开启你的 职业生涯

完成课程获得认证

开始学习
广告