软件设计师-编译原理

1.文法程序

1.1认识终结符和非终结符

终结符是一个原子量，不能再分解了，不能单独在左边的。用小写的字符表示。

非终结符可理解为一个可以再进行拆分的元素。用大写字母表示。

1.2文法的类型

0型文法

() 闭包表示集合中的任意个元素任意组合成一个串。

1型文法

2型文法

3型文法

 2.正规式（正则表达式）

 x*表示x的个数从0个到无穷个。

状态图∑小写表示不需要输入任何元素就可以转换到下一个状态,也就是输入为空的时候就可以转换到下一个状态.

有限自动机（有穷自动机）

1.NFA与DFA的定义

NFA 不确定的有限自动机 DFA确定的有限自动机

语法推导数

1.每个节点都有一个标记,此标记是V的一个符号;

2.根的节点是S;

3若一节点n至少有一个它除自己外的子孙,并且标记为A,则A肯定在Vn中.

4.如果节点n的直接子孙，从左到右的次序是节点n1,n2,..nK,其 标记分别是A1，A2，....Ak,那么

A->A1,A2...Ak,一定是P中的一个产生式。

短语 语法树中任意一个节点的叶子节点就是短语

直接短语  语法树中节点与子节点