上下文无关语法简介
定义 − 由一组有限的语法规则组成的上下文无关语法 (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 → x1x2 …… xn 是 CFG 中的生成规则，则解析树/派生树将如下所示 −
有两种不同的方法来绘制派生树 −
自上而下的方法 −
从起始符号 S
开始
使用生成式向下到树叶
自下而上的方法 −
从树叶开始
向上进行到根，即起始符号S
树的派生或产量
解析树的派生或产量是通过从左到右连接树叶的标签而获得的最终字符串，忽略 Null。但是，如果所有树叶都是 Null，则派生为 Null。
示例
让 CFG {N,T,P,S} 为
N = {S}, T = {a, b}, 起始符号 = S, P = S → SS | aSb | ε
从上述 CFG 派生出的一个词是"abaabb"
S → SS → aSbS → abS → abaSb → abaaaSbb → 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' 是终结符串，这被称为右递归产生式。具有右递归产生的语法被称为右递归语法。
