什么是上下文无关语法？

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

一个程序由各种字符串组成。但是，每个字符串都不是正确的或有意义的字符串。因此，要识别语言中的有效字符串，应指定一些规则来检查字符串是否有效。这些规则只不过是让语法。

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

上下文无关语法

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

由于词法分析器生成一串标记，这些标记被提供给解析器以构造解析树。但是，在构造解析树之前，这些标记将被分组，这样分组的结果将是一种语言的有效构造。因此，为了指定语言的结构，使用合适的符号，这将是精确且易于理解的。这种表示法是上下文无关语法。

形式上，上下文无关语法(G)可以定义为 -

它是一个 4 元组 (V,∑,P,S)

如果每个产生式 (P) 的形式为 A → α，则 G 是上下文无关的，其中 A∈V 和 α ∈(V∪ ∑ )*。

Example1 - 写下语言的语法

L={a ⁿ |n≥1}

解决方案

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

这些产生式生成语言 a ⁿ。

i.e., S ⇒ a

S ⇒ a S ⇒ a a or a2S ⇒ a S ⇒ a a S ⇒ a a a or a3.

S ⇒ a S ⇒ a a S ⇒ a a a S ⇒ ... ⇒ an

在上下文无关文法中，变量或非终结符号出现在 →（箭头）的左侧。这些符号将被扩展，直到生成所有终端符号。

终端符号是一种语言中使用的标记。

Example2 - 找出语法生成的语言。

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

解决方案

S ⇒ a $\下划线{S}$b

⇒ a $\下划线{aSb}$b

⇒ aaa $\下划线{S}$bbb

⇒ aaaa S bbbb

…………………………

⇒ a ⁿ⁻¹ $\下划线{S}$b ⁿ⁻¹

⇒ a ⁿ⁻¹ $\下划线{a\:b}$b ⁿ⁻¹

⇒ 一个ⁿ b ⁿ

∴ 语言 L= {a ⁿ b ⁿ |