2.1 Context-Free Grammars


A context-free grammar is a 4-tuple (V,Σ,R,S)(V,\Sigma,R,S), where

  1. VV is a finite set called the variables,
  2. Σ\Sigma is a finite set, disjoint from VV, called the terminals,
  3. RR is a finite set of rules, with each rule being a variable and a string of variables and terminals, and
  4. SVS\in V is the start variable


  • 单步推导(yield)uAvuwvuAv\Rightarrow uwv
  • 任意步推导(derive)uvu\Rightarrow^*v. 并产生一棵parse tree

A launguage is called a context-free launguage if it can be generated by a CFG.







A string ww is derived ambiguously in CFG GG if it has two or more different leftmost derivations.

Grammar GG is ambiguous if it derives some string ambiguously.

固有歧义性:有些context-free language只能被ambiguous CFG产生,比如{aibjcki=j\{a^ib^jc^k|i=j or j=k}j=k\}

定义2.8(Chomsky normal form)

A context-free grammar is in Chomsky normal form if every rule is of the form

ABCA\rightarrow BC

AaA\rightarrow a

其中aa是terminal,A,B,CA,B,C是variables,B,CB,C不是start variable

定理(Chomsky normal form的普适性)

Any context-free language is generated by a CFG in Chomsky normal form.

证明方法:构造法,提供了一套把任意CFG改写成等价Chomsky normal form的流程。

这样理解:Parse tree可以有等价的二叉树

results matching ""

    No results matching ""