Automata Theory 简明教程

Context-Free Grammar Introduction

Definition - 上下文无关文法 (CFG) 由一组有限的文法规则组成，是四元组 (N, T, P, S) ，其中

  1. N 是非终结符符号的集合。

  2. T 是终结符的集合，其中 N ∩ T = NULL.

  3. P 是规则的集合， P: N → (N ∪ T) ，即产生规则 P 的左手边没有任何右上下文或左上下文。

  4. S 是起始符号。

Example

  1. 文法 ({A}, {a, b, c}, P, A)，P：A → aA，A → abc。

  2. 文法 ({S, a, b}, {a, b}, P, S)，P：S → aSa，S → bSb，S → ε

  3. 文法 ({S, F}, {0, 1}, P, S)，P：S → 00S | 11F，F → 00F | ε

Generation of Derivation Tree

导出树或解析树是有序的根树，可以直观地表示从上下文无关文法导出的字符串的语义信息。

Representation Technique

  1. Root vertex - 必须由起始符号标记。

  2. Vertex - 由非终结符符号标记。

  3. Leaves - 由终结符符号或 ε 标记。

如果 S → x1x2 …… xn 是 CFG 中的一条产生规则，则解析树/导出树如下：

derivation tree

绘制导出树有两种不同的方法：

Top-down Approach −

  1. 从开始符号 S 开始

  2. 通过产生使用生产来降低到树叶

Bottom-up Approach −

  1. Starts from tree leaves

  2. 向上转换到根，这是开始符号 S

Derivation or Yield of a Tree

解析树的导出或产生的最终字符串通过从左到右串联树的叶子的标签获得，而忽略空值。然而，如果所有叶子都是空值，那么派生就是空值。

Example

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

N = {S}, T = {a, b}, 开始符号 = S, P = S → SS | aSb | ε

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

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

yield of a tree

Sentential Form and Partial Derivation Tree

部分派生树是派生树/解析树的一个子树，使得它的所有子组件都在子树中，或者它们都不在子树中。

Example

在任何 CFG 中，如果生成是 -

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

部分派生树可以是以下 -

sentential form and partial derivation tree

如果部分派生树包含根 S，则称为 sentential form 。上述子树也是以句子形式出现的。

Leftmost and Rightmost Derivation of a String

  1. Leftmost derivation - 通过在每一步中将生成应用到最左边的变量来获得最左边的派生。

  2. Rightmost derivation - 通过在每一步中将生成应用到最右边的变量来获得最右边的派生。

Example

设 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

以上字符串逐步推导如下 −

leftmost

字符串 "a+a*a" 最右侧推导可能如下 −

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

以上字符串逐步推导如下 −

rightmost

Left and Right Recursive Grammars

在一个上下文无关文法中 G ，如果有一个形式为 X → Xa 的产生式，其中 X 是一个非终结符， ‘a’ 是一个终结符字符串，它被称为 left recursive production 。具有左递归产生式的文法称为 left recursive grammar 。

而如果在一个上下文无关文法中 G ，如果有一个形式为 X → aX 的产生式，其中 X 是一个非终结符， ‘a’ 是一个终结符字符串，它被称为 right recursive production 。具有右递归产生式的文法称为 right recursive grammar 。