计算理论：上下文无关文法

course notes › theory of computation

Context-Free Grammars

Context-Free Grammar

Definition

A context-free grammar is defined by the 4-tuple

where

  1. is a finite set, each element is called a nonterminal character or a variable. Each variable defines a sub-language of the language defined by
  2. is a finite set of terminals, disjoint from . The set of terminals is the alphabet of the language defined by the grammar
  3. is a finite relation from to , where the asterisk represents the Kleene star operation. The members of are called the (rewrite) rules or productions of the grammar.
  4. is the start variable (or start symbol), used to present the whole sentence. It must be an element of

A production has the form: variable (head) strings of variables and terminals (body)

Derivation

有两种应用 CFG 的产生式来推断某个特定 string 是否在某个特定 variable 定义的语言之中的方法

recursive inference: 选择 body 中各个 variable 的 language 中的串，将其与 body 中的 terminals 以正确的顺序连接，其结果在 head 中的 variable 定义的语言中。

derivation: 将开始符号用某个产生式展开，再将结果中的 variable 用其产生式展开，重复上述过程直至得到一个全部由 terminal 组成的串，所有这样的串组成了 CFG 定义的语言。

为了定义 derivation，定义一个新的符号

设 是 CFG，令 为一个由 terminal 与 variable 组成的串，其中 为 variable， 。令 为一个产生式，则

可以递归定义零次或多次 derivation

Basis. for any string

Induction. If and , then

为了限制 derivation 时的选择，引入 leftmost derivation 与 rightmost derivation

  • leftmost derivation: at each step we replace the leftmost variable by one of its production bodies,
  • rightmost derivation: at each step we replace the rightmost variable by one of its production bodies,

The Language of a Grammar

If , the language of , denoted is

is a context-free language (CFL)

For a CFG

sentential form:

left-sentential form:

CFG 定义的语言集合比 RE 定义的语言集合要广

BNF Notation

BNF (Backus-Naur Form) is a notation technique for CFG

  • Variables are words in
  • Terminals are multicharacter strings indecated by boldface or underline
  • is used for
  • is used for "or"
  • is used for one or more. e.g. BNF: CFG:
  • Symbols surrounded by is optional. e.g. BNF: CFG:
  • Grouping:

Parse Trees

Definition

Given a grammar , the parse trees for are trees with the following conditions

  • Each interior node is labeled by a variable in
  • Each leaf is labeled by either a variable, a terminal, or . However, if the leaf is labeled , then it must be the only child of its parent
  • If an interior node is labeled , and its children are labeled , then is a production in

将 parse tree 叶节点的 labels 从左向右连接起来，得到的串称为这颗树的 yield。yield 是从 root variable 推导得到的。

有一种特殊的 parse tree 满足

  • The yield is a terminal string
  • The root is labeled by start symbol

这样的 parse tree，其 yield 是属于该文法的串

Inference, Derivations, and Parse trees

Given a grammar , the following are equivalent

  • The recursive infererence procedure determines that terminal string is in the language of
  • There is a parse tree with root and yield

等价性的证明将按照下图的顺序

From Inferences to Trees

Let be a CFG. If the recursive inference procedure tells us that terminal string is in the language of variable , then there is a parse tree with root and yield

Proof.

Induction on the number of step used to infer that is in the language of

Basis. 只用一步推断，故有生成式 ，则必有一颗 parse tree 以 为根且所有 的子节点都为叶节点且组成 。特殊情况下 ，则 的唯一子节点为 ，仍为合法 parse tree

Induction. 假设经过 步推断得出 属于 的语言。考虑推断最后一步，使用的产生式为 ，其中每个 或是 variable 或是 terminal

令 满足

  1. 如果 是 terminal，
  2. 如果 是 variable，则 是经过推断得出在 的语言中的一个 string。在 步推断出 在 的过程中这次推断最多有 步。故根据 I.H. ，存在一颗 parse tree 根为 ，yield 为

故可以构造出一颗 parse tree 根为 且子节点为 ，对于每个子树 ，若为 terminal，则只有其本身一个节点，若为 variable，则其为一颗 parse tree，根为 ，yield 为

如此构造出的 parse tree 根为 ，其 yield 为子树的 yields 从左到右连接，即

Q.E.D.

From Trees to Derivations

Let be a CFG, and suppose there is a parse tree with root labeled by variable and with yield , where is in . Then there is a leftmost derivation in grammar

Proof.

perform an induction on the height of tree.

Basis. 考虑高度为 1 的情况，则这棵树以 为根且所有 的子节点都为叶节点且组成 。根据 parse tree 的定义，存在产生式 ，则最左推导为

Induction. 考虑高度为 时，则 必有子节点 ，其中每个 或是 variable 或是 terminal

  1. 为 terminal，定义 为只有 的 string
  2. 为 variable，则其一定为某颗子树的根，且有 yield 。显然子树的高度小于 ，根据 I.H. 有

显然有

则可以构造出一个最左推导，第一步是

对 有

Proof.

Induction on

Basis.

I.H.

Induction.

  1. 如果 是 terminal，则 ，显然有

  2. 如果 是 variable，根据之前的 I.H. 有 ，令其为 ，则有

    可得

Q.E.D.

根据上述证明，在 时有

Q.E.D.

Let be a CFG, and suppose there is a parse tree with root labeled by variable and with yield , where is in . Then there is a rightmost derivation in grammar

证明同 leftmost derivation，事实上对于一般的 derivation 也有上述结论

From Derivations to Recursive Inference

Let be a CFG, and suppose there is a derivation , where is in . Then the recursive inference procedure applied to determines that is in the language of variable

Proof.

Induction on the length of the derivation

Basis. 推导仅有一步时必有产生式 ，则根据 recursive inference 的 basis 即可得出 在 的语言中

Induction. 假设推导有 步，则 ，可令 ，其中

  1. 如果 是 terminal，
  2. 如果 是 variable，则 的推导肯定小于 步，则根据 I.H. ，recursive inference 得出 在 的语言中

根据以上结论，易得根据 recursive inference 有 在 的语言中

Q.E.D.

Ambiguity in Grammars and Languages

Ambiguous Grammars

对于同一个串可以得到一颗以上 parse tree 的文法就是 ambiguous 的，显然根据不同的 parse tree 可以得到不同的最左/最右推导

ambiguous 是 grammar 而非 language 的属性。有些 ambiguous 的文法在修改后可以得到定义同样语言但 unambiguous 的文法

LL(1) grammars are unambiguous

消歧：结合性/优先级/修改文法

Inherent Ambiguity

Certain CFLs are inherently ambiguous, meaning that every grammar for the language is ambiguous

e.g.

Normal Forms for CFGs

Eliminating Useless Symbols

A symbol is useful for a grammar if there is some derivation of the form , where is in

从文法中删去 useless 的 symbol 并不会改变 CFG 定义的语言。一个 useful 的 symbol 具有以下两种属性

  • generating: for some terminal string . Every terminal is generating
  • reachable: for some and

先删去所有非 generating 的 symbol，再删去所有 unreachable 的 symbol 即可使其余的 symbol 均为 useful

Let be a CFG, and assume that . Let be the grammar we obtain by the following steps:

  1. First eliminate nongenerating symbols and all productions involving one or more of those symbols. Let be this new grammar. must be generating, since
  2. Second, eliminate all symbols that are not reachable in the grammar

Then has no useless symbols, and

Proof.

考虑 是未被消除的 symbol，即 ，显然 ，且在此推导过程中的所有 symbol 都是 generating 的，即

同样的，可以知道 ，且在此推导过程中每个 symbol 都是 reachable 的，即 。易得 中的符号都是 reachable ，且在 中都是 generating 。故 ，显然这个过程中的 symbol 都是 reachable，因此

即任意取 中的 symbol ， 是 useful

只需证明

  • : trivial，我们通过消除产生式和符号得到
  • : 若 ，存在一个推导 ，显然这个推导路径上所有符号都是 generating 且 reachable。故

Q.E.D.

找出所有的 generating symbol 是一个递归的过程

Basis. 所有 中的 symbol 都是 generating

Induction. 考虑 ，若 中所有符号都是 generating，则 也是 generating

上述算法可以找出 中所有的 generating symbol，i.e. 没被找出的都是 nongenerating

Proof.

显然可以得出所有算法找出的 symbol 都是 generating。只需证明所有 generating symbol 都会被算法找出。考虑 ，根据推导长度归纳

Basis. 0 步的推导，则 是 terminal，根据 basis，其是 generating

Induction. 考虑推导 步的情况，则 是 variable，有 ，其中 的每个 symbol 都经过少于 步推导出 的一部分，根据 I.H. 中所有的 symbol 都是 generating，则根据算法的 induction 部分， 也是 generating

Q.E.D.

找出 reachable symbol 的过程同样是一个递归的过程

Basis. is reachable

Induction. 若 是 reachable，则 的所有产生式体中的 symbol 都是 reachable

上述算法可以找出 中所有 reachable symbol，证明类似。

Eliminating -Productions

-production:

If language has a CFG, then has a CFG without -production

Nullable: A variable is nullable if

寻找 nullable symbol 的算法是一个递归的过程

Basis. If is a production of , is nullable

Induction. 考虑 ，若 中所有符号都是 nullable，则 是 nullable， 中所有 symbol 都是 variable，因为 nullable 是针对 variable 而言的

上述算法可以找到 中所有 nullable symbol

Proof.

根据算法的归纳过程易得所有算法找出的 variable 都是 nullable，只需证明所有 nullable variable 都会被算法找出。证明的过程是对 的最短推导长度的归纳

Basis. 仅有一步推导，则 ，从算法的 basis 即可发现 是 nullable

Induction. 考虑推导 步的情况，即 ，其中每个 都经过少于 步推导得出 ，则根据 I.H. ，它们均为 nullable，则根据算法的 induction 部分， 也是 nullable

Q.E.D.

找出所有 nullable variable 后即可构造没有 -production 的 CFG。考虑产生式 ，考虑其中有 个 nullable symbol，则在新 CFG 中加入 个产生式（每个 nullable symbol 都有可能出现/不出现），例外是当 时，不加入所有 都不出现的产生式（即不加入 ）。若有产生式 ，则新 CFG 不加入该产生式

设经过上述过程后生成的新文法为 ，则

Proof.

只需证明对于任意 中的 variable 有

(): 考虑 ，显然 ，因为 中没有 -production。对推导长度归纳以证明

Basis. 一步推导，则 是 中的产生式。根据 的构造过程， 中存在产生式 满足 为 其中加上 0 个或多个 nullable variable，则 ，其中 nullable 的产生式都推导出了

Induction. 考虑 步推导，则 。显然在 中有产生式 ，满足 为 其中加上 0 个或多个 nullable variable。同样，可以将 分为 其中 ，由于推导步数小于 ，根据 I.H. 可以得到 ，则存在推导

(): 同样是根据推导长度归纳

一般情况的 variable 可证，令 即可证明上述结论

Q.E.D.

Eliminating Unit Productions

Unit production: , both are variables

Unit pair: such that using only unit productions

可以递归地构造 unit pair

Basis. is a unit pair

Induction. 若 是 unit pair， 是产生式且 是 variable，则 是 unit pair

上述算法可以找出所有 unit pair

Proof.

只用证明文法中所有 unit pair 都被算法找到。根据 推导长度归纳

Basis. 0 步，则 ，显然在算法的 basis 阶段就找到

Induction. 考虑 步推导，则有 ，考虑 ，这个推导只用了 步，根据 I.H. ， 被找到，则根据算法的 induction 部分， 被找到

Q.E.D.

找到所有 unit pair 之后，可以构造没有 unit pair 的文法

对于每个 ，若 是个 nonunit production，则将 加入新文法。

可以证明通过上述过程得到的新文法 ，有

Proof.

只需证明

(): 考虑 ，由于 中每个产生式都等价于一个产生式序列，包含 0 个或多个 unit production 和一个 nonunit production，其中每个产生式都是 的产生式，即 可以得出 ，则每一步 中的推导都可以替换为多步 中的推导，即

(): 考虑 ，则必有一个对应的最左推导，在最左推导中，每个 unit production 在被替换后其 body 成为最左的 variable，然后被替换，则推导的产生式应用的序列可以看作 0 个或多个 unit production 接着一个 nonunit production，这其中每一步（unit production* + nonunit production）都是 中的一个 production，则有

Q.E.D.

Chomsky Normal Form

简化一个 CFG 只要按顺序

  1. Eliminate -production
  2. Eliminate unit production
  3. Eliminate useless symbols

即可得到没有 -production, unit production, useless symbol 的等价的 CFG

可以证明任何没有 的非空 CFL 都有一个文法 ，其中任意产生式都是以下两种形式之一

  1. ，其中 都是 variable
  2. ，其中 是 variable， 是 terminal

且 中没有 useless symbols，这样的文法称为 Chomsky Normal Form, CNF

将文法按照上述步骤简化后，产生式只有两种可能

  1. ，已经满足 CNF
  2. ，其中

对于第二种情况，可以按照以下步骤处理

  • 将 body 转变为只含 variable
  • 将长度大于 2 的 body 拆成一个链

对于第一步，考虑一个长度大于等于 2 的 body 其中的 terminal ，为每个 引入一个 variable 以及产生式 ，然后将 body 中所有 替换为 即可

对于第二步，考虑产生式 ，引入 个 variable ，将产生式替换为

若 是 CFG 且其中除 外至少有一个 string，则有一个 CNF 文法 满足

证明见课本 P.245