Automata Theory 简明教程

Context-Free Grammar Introduction

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

Definition − A context-free grammar (CFG) consisting of a finite set of grammar rules is a quadruple (N, T, P, S) where

  1. N is a set of non-terminal symbols.

  2. T is a set of terminals where N ∩ T = NULL.

  3. P is a set of rules, P: N → (N ∪ T)*, i.e., the left-hand side of the production rule P does have any right context or left context.

  4. S is the start symbol.

Example

  1. The grammar ({A}, {a, b, c}, P, A), P : A → aA, A → abc.

  2. The grammar ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S → ε

  3. The grammar ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε

Generation of Derivation Tree

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

A derivation tree or parse tree is an ordered rooted tree that graphically represents the semantic information a string derived from a context-free grammar.

Representation Technique

  1. Root vertex − Must be labeled by the start symbol.

  2. Vertex − Labeled by a non-terminal symbol.

  3. Leaves − Labeled by a terminal symbol or ε.

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

If S → x1x2 …… xn is a production rule in a CFG, then the parse tree / derivation tree will be as follows −

derivation tree

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

There are two different approaches to draw a derivation tree −

Top-down Approach −

Top-down Approach −

  1. Starts with the starting symbol S

  2. Goes down to tree leaves using productions

Bottom-up Approach −

Bottom-up Approach −

  1. Starts from tree leaves

  2. Proceeds upward to the root which is the starting symbol S

Derivation or Yield of a Tree

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

The derivation or the yield of a parse tree is the final string obtained by concatenating the labels of the leaves of the tree from left to right, ignoring the Nulls. However, if all the leaves are Null, derivation is Null.

Example

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

Let a CFG {N,T,P,S} be

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

N = {S}, T = {a, b}, Starting symbol = S, P = S → SS | aSb | ε

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

One derivation from the above CFG is “abaabb”

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

yield of a tree

Sentential Form and Partial Derivation Tree

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

A partial derivation tree is a sub-tree of a derivation tree/parse tree such that either all of its children are in the sub-tree or none of them are in the sub-tree.

Example

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

If in any CFG the productions are −

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

部分派生树可以是以下 -

the partial derivation tree can be the following −

sentential form and partial derivation tree

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

If a partial derivation tree contains the root S, it is called a sentential form. The above sub-tree is also in sentential form.

Leftmost and Rightmost Derivation of a String

  1. Leftmost derivation − A leftmost derivation is obtained by applying production to the leftmost variable in each step.

  2. Rightmost derivation − A rightmost derivation is obtained by applying production to the rightmost variable in each step.

Example

设 CFG 中的任何一组生成规则

Let any set of production rules in a CFG be

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

在一个字母表 {a} 中。

over an alphabet {a}.

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

The leftmost derivation for the string "a+a*a" may be −

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

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

The stepwise derivation of the above string is shown as below −

leftmost

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

The rightmost derivation for the above string "a+a*a" may be −

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

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

The stepwise derivation of the above string is shown as below −

rightmost

Left and Right Recursive Grammars

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

In a context-free grammar G, if there is a production in the form X → Xa where X is a non-terminal and ‘a’ is a string of terminals, it is called a left recursive production. The grammar having a left recursive production is called a left recursive grammar.

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

And if in a context-free grammar G, if there is a production is in the form X → aX where X is a non-terminal and ‘a’ is a string of terminals, it is called a right recursive production. The grammar having a right recursive production is called a right recursive grammar.