编译原理 文法

前言

编译原理这种课一听就知道肯定特别晦涩难懂,上课没听懂,今天花了一天时间来学文法,看了一天也只是有些眉目,书上讲的并不是特别清楚,倒是从各大博客中汲取到不少知识。虽然感觉还只是停留在理论阶段,但也要记录一下吧,不然到时候理论都想不起来。

文法的定义

文法 G 定义为一个四元组(VN, VT, P, S)

  • VN :非终结符的非空有穷集
  • VT :终结符的非空有穷集,VN∩VT
  • P :产生式的非空有穷集
  • S :S∈VN,为文法 G 的开始符号

文法的分类

乔姆斯基(Chomsky)根据对产生式的要求不同,将文法分为四类,即:0型文法、1型文法、2型文法和3型文法,这四类文法通常称为 Chomsky 体系。

文法 G产生式结构语言 L(G)
0型文法(短语结构文法)∀α→β∈P,其中α、β∈(VT∪VN)* ,∣α∣≠00型语言(短语结构语言)
1型文法(上下文有关文法)∀α→β∈P,其中α、β∈(VT∪VN)* ,∣α∣≤∣β∣1型语言(上下文有关语言)
2型文法(上下文无关文法)∀A→β∈P,其中A∈VN,β∈(VT∪VN)*2型语言(上下文无关语言)
3型文法(正则文法)∀A→α|αB∈P(右线性)或∀A→α|Bα∈P(左线性),其中,A,B∈VN,α∈VT∪{ε}3型语言(正则语言)

下面的例子中,A、B∈VN, a、b∈VT, 即大写字母表示非终结符,小写字母表示终结符。

0型文法

例:A→a, Aa→aA, AA→a, AA→Aa

左边至少有一个非终结符,不然的话也就不用推导了

1型文法

例:A→a, Ab→Abc, AB→Bc

在0型文法的基础上限制右边长度不能短于左边,所以 AA→a 不是1型文法。(α→ε除外)

2型文法

例:A→a, A→aB, B→a, B→ab

在1型文法的基础上限制左边不能有终结符,所以 Ab→Abc 不是2型文法。

3型文法

例:A→a, A→aB, B→a, B→cB

在2型文法的基础上限制右边只能有一个终结符,而且左线性和右线性不能同时出现,所以 A→aa 或者 B→cB 和 B→Bc 同时出现的都不是3型文法。

疏影横斜水清浅,暗香浮动月黄昏