编译原理基本概念

一、编译过程与T形图

1.编译过程

从宏观上讲就是由高级语言生成机器码的过程。

2.T形图

二、自动机基础

1.文法定义：G=(VT,VN,P,S)

字母表：有穷符号集合。
乘积：连接。
正闭包与克林闭包：克林闭包多了一个空串。(所有不同长度的字符串组成的集合)
G=(VT,VN,P,S)

• VT：终结符，a,b,c,id…
• VN：非终结符，通常用来描述终结符,E,T…
• P：产生式集合，描述将终结符和非终结符组合成串的方法。
• S：开始符号，表示的是该文法中最大的语法成分。

2.推导与规约

+表示经过正数次推导，*表示经过若干次推导(多了一个0次)。

3.句型与句子

不包含非终结符的是句子，包含的是句型，句子是一个特殊的句型。

4.语言

由文法开始符号推导出所有的句子构成的集合称为该文法生成的语言。

5.文法分类

是通过对产生式内容的限制来划分的。

(1)0型文法

无限制文法，a->b

，a中至少有一个非终结符。

(2)1型文法(上下文有关语言)

a->b

a中至少一个非终结符
且|a|<=|b|

(3)2型文法(上下文无关文法)

a->b

a中至少一个非终结符
|a|<=|b|
a只能是非终结符

(4)3型文法

a->b

a中至少一个非终结符
|a|<=|b|
a只能是非终结符
右线性：(a->w)||(a->wB) 左线性：(a->w)||(a->Bw)

(5)四种文法关系

6.上下文无关文法(CFG)分析树

我们只对2型文法做研究。

(1)建树规则

根节点符号为文法开始符号。
子树根节点为产生式左侧，子节点从左到右构成产生式右侧。
叶节点既可以是终结符，也可以是非终结符。

(2)衍生概念

边缘：从左到右排列叶子节点，得到符号串称为这棵树的边缘。
短语：分析树中的每一个子树的边缘称为该句型的一个短语。
直接短语：子树只有父子两代节点，它的边缘为一个直接短语。

7.二义性文法

形成多棵分析树的文法是二义性文法，我们要避免。有一个充分条件，如果文法满足，则为一个二义性文法。