用属性解释类型 2 语法

类型 2文法是上下文无关文法 (CFG)。

所有作品都采用以下形式 -

A → x — 其中 A 是非终结符，x 是非终结符和终结符的字符串，

上下文无关文法等价于下推自动机(PDA) 和上下文无关语言。

示例 - 下推自动机(PDA)

特性

• 如果产生式规则的形式为 A → α，则称 A 文法 G = (V, T, P, S) 是上下文无关的。

• 转换允许 A → ε [即，α → ε] 其中，A 是非终结符，α 是任何终结符或非终结符。

• 在这里，转换规则的左侧仅包含一个非终结符。

• 类型 2 语法是大多数编程语言（例如 XML）的语法基础。特性

CFG 在以下情况下关闭 -

• 联盟

• 级联

• Kleene 闭合

它不是在互补、替代、逆转下封闭的。

示例

考虑生产，P ⇒ {S → aSa, S → bSb, S → ε}

Since S → aSa
   → aaSaa [as S → aSa]
   → aabSbaa [as S → bSb]
   → aabbaa [as S → ε]

因此，S 可能生成 S = {ε, aa, bb, abba, aabbaa, abaaba, ...}

因此，语言定义为L(G)= {w wR | w ε {a, b}*}

可以使用使用堆栈内存来存储符号的下推自动机来处理 CFG。