Bonky
Neither beliver nor reject anything, because any other person has rejected of believed it. Heaven has given you a mind for judging truth and error, Use it.
By Thomas Jefferson

编译原理 – 文法与语言

上下文无关文法

上下文无关文法是一种用于描述程序设计语言语法的表示方法, 或简称”文法”。文法一般被用于组织编译器前端。

CFG是一个四元组:G =(N,T,P,S),被称作一个文法,其中

N是非终结符(Nonterminals)的有限集合;
T是终结符(Terminals)的有限集合,且N∩T=Φ;
P是产生式(Productions)的有限集合,形如:A→α,其中A∈N(左部),α∈(N∪T)*(右部),若α=ε,则称A→ε为空产生式(也可以记为A →);
S是非终结符,称为文法的开始符号(Start symbol)。

下面是一个例子

我们可以得到:S → 0S1 → 00S11 → 000S111 → 00001111

S {=>}^* V 就是S可以推出V,而且S可以等于V

S {=>}^+ V 就是S可以推出V,但是S 不等于V

句子和句型

GS→0S1S→01

G的句型S,0S1 ,00S11 ,000S111,00001111

G的句子00001111, 01,句子一定是句型,反之不然(即句子中必须不能有S,不可再往下推)

语言

由文法G生成的语言记为L(G),它是文法G的一切句子的集合(一切实例的集合):

例子:

推导过程如下

四种文法

img

0型文法(对应图灵机)

  • 如果它的每个产生式α→β是这样一种结构:α∈(VN∪VT)且至少含有一个非终结符,而β∈(VN∪VT),则G[S]是一个0型文法。
  • 0型文法也称短语文法,记为PSG。
  • 一个非常重要的理论结果是:0型文法的能力相当于图灵机。或者说,任何0型文语言都是递归可枚举的,反之,递归可枚举集必定是一个0型语言。

1型文法(对应线性界线自动机,自然语言)

  • 它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。
  • 注意:虽然要求|β|>=|α|,但有一特例:α→ε也满足1型文法。
  • 1型文法也叫上下文有关文法,记为CSG。
  • 此文法对应于线性有界自动机。

2型文法(对应下推自动机,程序设计语言)

  • 2型文法是在1型文法的基础上,再满足:每一个α→β都有α是非终结符。
  • 2型文法也叫上下文无关文法,记为CFG。
  • 此文法对应于下推自动机。

3型文法(对应有限自动机)

  • 它是在2型文法的基础上满足:A→α|αB(右线性)或A→α|Bα(左线性)。
  • 3型文法也叫正规文法,记为RG。
  • 此文法对应于有限状态自动机。

二义性

输入一个句子(字符串),如果能构造出多颗语法树,那么说文法具有二义性。

如下图,对于同一个句子 i*i+i,同一个文法可以构造成下面两种语法树。

句型的分析

自上而下分析法

从文法的开始符号出发,反复使用文法的产生式,寻找与输入符号串匹配的推导,或者说,为输入串寻找一个最左推导。

自下而上分析法:

从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。

短语和句柄

短语就是所有子树的叶子结点构成的

直接短语是只有父子关系的短语

句柄是最左的直接短语

简单可以这么理解:

  • 每个句型都有一棵语法树;

  • 每棵语法树的叶(从左到右)组成一句型;

  • 每个子树的叶(从左到右)组成一短语;

  • 每个简单子树的叶(从左到右)组成一简单短语;

简单子树就是只有父子关系的树(可以理解为只有两层),任何一个儿子都必须为叶子

Unknown

  • 最左简单子树的叶(从左到右)组成一句柄。

规范规约

一些性质

多余规则与有害规则

有害规则:形如U→U的产生式。会引起文法的二义性

多余规则:指文法中任何句子的推导都不会用到的规则

消除左递归问题

对于自上而下分析要求文法不含左递归规则(引起无限循环),我们只能处理不含左递归和回溯的文法
直接左递归:有产生式P→Pa
间接左递归:文法中存在某个P属于Vn,有P→+Pa

参考

  1. 上下文无关文法(CFG)

  2. 编译原理 | 关于四种文法的理解学习及如何根据语言描述给出正则式or相应文法

Share

You may also like...

发表评论

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