ITOC chapter2 上下文无关语言

2 Context-Free Languages 上下文无关语言

上下文无关文法–构造语法分析器

上下文无关语言⊃正则语言

下推自动机

2.1 Context-Free Grammars 上下文无关文法

上下文无关文法是一个四元组 (V,Σ,R,S), 其中:

  1. V 是一个有穷集合,叫variable(变元集)
  2. Σ 是一个与V不相交的有穷集合,叫terminals(终结符集)
  3. R 是一个有穷的rules集, 每一条规则是一个变元和一个由变元和终结符组成的字符串。
  4. S∈V是起始变元。

设u,v,w是变元/终结符的字符串,A->w是一条文法规则,则uAv生成uwv。

如果u=v,或者存在序列u1,u2,,,uk使得u⇒u1⇒u2⇒⋯⇒uk⇒v,那么记作u(⇒∗)v,这个文法的语言是{w∈Σ∗|S(⇒∗)w}

Ambiguity 歧义性

定义:如果字符串w在上下文无关文法G中有两个或两个以上不同的最左派生,那么我们说:在G中歧义地产生字符串w。

如果文法G歧义地产生某个字符串,那么我们说:G是歧义的。

例子:⟨EXPR⟩→⟨EXPR⟩+⟨EXPR⟩ | ⟨EXPR⟩∗⟨EXPR⟩ | (⟨EXPR⟩) | a  这个文法歧义地产生字符串a+a*a

Chomsky normal form 乔姆斯基范式

定义:如果一个上下文无关文法地每一个规则满足:A→BC和 A→a  那么他是乔姆斯基范式

其中,a是任意地终结符,A,B,C是任意的变元,但B,C不能是起始变元。同时,允许规则S→ε(S为起始变元)

定理:任一上下文无关语言都可以用乔姆斯基范式地上下文无关文法产生

证明方法:先加一个新的起始变元,删除所有A→ε型的ε规则,再删除所有A→B型的单一规则,删除时添加/合并符合乔姆斯基的等价规则,最后把剩下的规则转换成符合乔姆斯基的形式。

2.2 Pushdown Automata (非确定型)下推自动机

与NFA相比,多了个栈,可以识别某些非正则语言。

PDA与CFG能力上等价!

Definition PDA的形式定义

PDA是一个六元组(Q,Σ,Γ,δ,q0,F), 这里Q,Σ,Γ,F都是有穷集合:

  1. Q 是状态集,
  2. Σ是输入字母表,
  3. Γ是栈字母表,
  4. δ:Q×Σε×Γε⟶P(Q×Γε)是转移函数,
  5. q0∈Q 是起始状态集,
  6. F⊆Q 是接受状态集.
Computation

检验空栈:一开始放入一个符号$,当我们再次看到“$”时说明栈空。

检验末端:PDA如何检验到达输入的末端?(没想明白)

定理:一个语言是上下文无关的,当且仅当存在一台下推自动机识别它。

证明思路:设A是一个CFL,那么必存在一个CFG G产生A,我么需要将G转化为一台等价的PDA P。G–>P

PDA P当G产生w时,接受这个输入,设计P以确定是否有一系列使用G的规则的替换,能够从起始变元引导到w。

1)把标记符$和起始变元放入栈中

2)重复下列步骤:

  • a)如果栈顶是变元A,则确定地选择一个关于A地规则,并且把A替换成这条规则右边地字符串。
  • b)如果栈顶是终结符a,则读输入中地下一个符号,并且与a进行比较。如果它们匹配,则重复(2),如果不匹配,则这个非确定性分支拒绝。
  • c)如果栈顶符号是$,则进入接受状态,如果此时已全部读完,则接受这个输入串。

本质上是用PDA的栈模拟CFG最左派生CFL的过程。

引理:如果一个语言被一台下推自动机识别,则他是上下文无关的。

证明思路

现有一台PDA P,要构造一个CFG G,它产生了P接受的所有字符串。换句话说,如果一个字符串能使P从它的起始状态转移到一个接受状态,则G应该能产生这个字符串。P–>G

首先,我们对P作一点修改,使P获得以下特点:

  1. 有唯一的接受状态qaccept。
  2. 在接受之前排空栈。
  3. 每一个转移要不push要不pop,不同时发生。(把同时发生的替换成两个,把同时不发生的替换成先push再pop)接着,设计G,使得Apq产生把P从状态p转移到状态q,并且以空栈开始和结束的所有字符串。

G的规则包含三个部分:

  1. 对于每一个p,q,r,s∈Q,u∈Γ, 和a,b ∈ Σε,如果δ(p,a,ε)包含 (r,u),并且 δ(s,b,u)包含 (q,ε),则把规则 Apq⟶aArsb放入G
  2. 对于每一个p,q,r∈Q , 把规则Apq⟶AprArq放入G
  3. 最后,对于每一个p∈Q, 把规则Apq⟶ε放入G

断言:如果Apq产生x,则x能够把P从p和空栈转移到到q和空栈。

根据 P 第一步 push 进来的 u 和最后一步 pop 出去的 v 是不是同一个可分两种情况:

  1. 同一个:第一步 push 进去的 u 一直到最后才被 pop 出去,那么在中间的过程中,u 一直呆在栈底没动过,所以其实对于中间的过程来说,可以认为也是带着空栈开始,带着空栈结束,那么Apq=aArsb(a 是读入的第一个字符,b 是读入的最后一个字符)
  2. 非同一个:那么说明 u 在中间某一刻就被 pop 出去了,假设 u 是在到达 s 这一状态时被 pop 出去的,那么 Apq=ApsAsq

正则语言与上下文无关语言:

因为每一个正则语言都可以用NFA识别,而每一台NFA都是一台PDA,只要不考虑栈,所以每个正则语言都是上下文无关语言。

2.3 Non-Context-Free Languages 非上下文无关语言

正则语言有Pumping Lemma,上下文无关语言也有~

CFL Pumping Lemma 泵引理

如果A是CFL,则存在数p(泵长度),使得A中任何一个长度不小于p的字符串s能够划分成5段,s=uvxyz,满足:

  1. 对于每个i≥0, uv^ixy^iz∈A,
  2. |vy|>0,
  3. |vxy|≤p.

证明思路:设A为CFL,G为产生A的CFG,证明A中任意足够长的字符串s都能够被抽取,并且留在A中。

2.4 Deterministic Context-Free Languages: 确定性上下文无关语言DCFG 

Deterministic Context-Free Languages: 确定性下推自动机DPDA

非确定性下推自动机比确定性自动机能力更强。

Deterministic Context-Free grammer: 确定性上下文无关文法DCFG

DK检测

在DK检验中,从CFG G开始,我们构造相关的DFA DK,然后通过检查DK的接受状态来确定G是否是确定性的。

定理:如果G通过 DK-test那么G是DCFG.

 DPDA与DCFG的关系

定理An endmarked language is generated by a deterministic context-free grammar iff it is deterministic context free.

引理:每一个DCFG都对应一台DPDA

引理:每个识别endmarked language的DPDA都对应一个的DCFG。

Parsing and LR(k) Grammars

LR(0) 文法与DCFG一样。

LR(1)文法

DK1检测

定理:如果G通过DK1检测那么G是LR(1)文法。

证明思路:与前面DK检测相似,忽略lookahead symbol即可。

一个endmarked language如果是一个DCFL,那么它可由一个LR(1)文法产生。

每一个LR(1)文法对应一个等价的DPDA。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注