上下文无关语法简介

---

定义- 由一组有限的语法规则组成的上下文无关语法（CFG）是一个四元组（N，T，P，S），其中

• N是一组非终结符。

• T是终结点的集合，其中N ∩ T = NULL。

• P是一组规则，P: N → (N ∪ T)* ，即产生式规则P的左侧确实有任何右上下文或左上下文。

• S是起始符号。

例子

• 语法 ({A}, {a, b, c}, P, A), P : A → aA, A → abc。
• 语法 ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε
• 语法 ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε

派生树的生成

派生树或解析树是一种有序的有根树，它以图形方式表示从上下文无关语法派生的字符串的语义信息。

表现技术

• 根顶点- 必须用起始符号标记。

• 顶点- 由非终结符标记。

• 叶子- 由终端符号或 ε 标记。

如果 S → x ₁ x ₂ …… x _n是 CFG 中的产生式规则，则解析树/推导树将如下 -

有两种不同的方法来绘制派生树 -

自上而下的方法 -

• 以起始符号S开头

• 使用产品深入到树叶

自下而上的方法 -

• 从树叶开始

• 向上前进到根，即起始符号S

树的衍生或产量

解析树的推导或产出是通过从左到右连接树的叶子标签而获得的最终字符串，忽略空值。但是，如果所有叶子都为 Null，则派生为 Null。

例子

设 CFG {N,T,P,S} 为

N = {S}，T = {a，b}，起始符号 = S，P = S → SS | 砷化镓 | ε

上述 CFG 的派生之一是“abaabb”

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

句子形式和偏推导树

部分推导树是推导树/解析树的子树，其所有子树要么都在子树中，要么都不在子树中。

例子

如果在任何 CFG 中，产生式是 -

S → AB，A → aaA | ε, B → Bb| ε

偏导树可以如下 -

如果偏导树包含根S，则称为句子形式。上面的子树也是句子形式的。

字符串的最左推导和最右推导

• 最左推导- 最左推导是通过将产生式应用于每个步骤中最左侧的变量来获得的。

• 最右推导- 最右推导是通过将产生式应用于每个步骤中最右变量来获得的。

例子

令 CFG 中的任意一组产生式规则为

X → X+X | X*X|X| A

在字母表 {a} 上。

字符串“a+a*a”的最左推导可能是 -

X → X+X → a+X → a + X*X → a+a*X → a+a*a

上述字符串的逐步推导如下所示：

上述字符串“a+a*a”的最右推导可能是 -

X → X*X → X*a → X+X*a → X+a*a → a+a*a

上述字符串的逐步推导如下所示：

左递归文法和右递归文法

在上下文无关语法G中，如果存在X → Xa形式的产生式，其中X是非终结符，“a”是终结符串，则称为左递归产生式。具有左递归产生式的文法称为左递归文法。

如果在上下文无关语法G中，如果存在形式为X → aX 的产生式，其中X是非终结符，“a”是终结符串，则称为右递归产生式。具有右递归产生式的文法称为右递归文法。