软件设计师-编译原理 编译原理及编译程序构造

文法

1、认识终结符和非终结符：终结符是不能够单独出现在推导符左边的式子，属于原子量，不能够分解的量，不能用其他量来代替的和不能分解的；非终结符是可以被分解为多个语句；常用小写字母表示终结符，大写字母表示非终结符；

2、文法的类型

3、如何判断一个串是否为某个文法的句型

例如：A ->aB(A\B非终结符，a终结符)；a ->b错误写法

正规式（3型文法）

0型文法

Vn表示非终结符，Vt表示终结符，P是集合，S表示开始符

G=（Vn，Vt，P，S）；如果他的每一个产生式α -> β中：α∈（Vn ∪ Vt）且至少含有一个非终结符，β∈（Vn ∪ Vt），则G是一个0型文法；任何0型文法都是递归可枚举的，反之递归可枚举集必定是一个0型文法。

1型文法

也叫上下文有关文法，此文法对应于现象有界自动机。在0型文法的基础上每个α -> β都有|β|>=|α|,这里|β|表示的是β是长度

2型文法

也叫上下文无关文法，对应于下推自动机，在1型文法上α -> β都有α 是非终结符；如：A->Ba

3型文法

也叫正规文法，对应于有限状态自动机，在2型文法的基础上满足：A->α|α B（右线性）或 A->α|B α（左线性）

4、正规式的规则：A->xB,B->y,那么A=xy；A->xA|y,A=x*y;A->x,A->y,A=x|y;x*表示0到无穷个x。

有穷自动机（又称为有穷自动机）

NFA（不确定的有限自动机）和DFA（确定的有限自动机）的定义，NFA转化为DFA，正规式与有限自动机的转化。

有限自动机DFA记为：M=（S,Σ，f，S0，Z），其中

S是一个有限状态集合；

Σ是一个字母表，他的每一个元素称为一个输入字符；

f是一个从SxΣ至S的单值部分映射，f（S，a）=s`意味着当现行状态s、输入字符为a是，将转换到下一个状态s`，称s`为s的一个后续状态；

S0∈S，是惟一的初态；

Z∈S，是一个终态集；

不确定有限自动机：S0和Z属于且等于S，是一个非空初态集（可以有多个初态）；

语法推导数

每个节点都有一个标记，此标记是V的一个符号；

根的标记是S；

若一节点n至少有一个他自己除外的子孙，并且有标记A，则A肯定在Vn（非终结符集）中；

如果节点n的直接子孙，从左到右次序节点n1,n2,n3…nk;其标记分别是A1,A2…Ak,那么A->A1,A2…Ak一定是P中的一个产生试；

算符优先

A<b表示a的优先性低于b

a=b表示a的优先性等于b

a>b表示a的优先性高于b

↑向上箭头优先级最高，遵循右结合，A↑b↑a先算b↑a；

*，/优先级其次，遵循左结合

+，-优先级最低，遵循左结合