重点模块说明
编译与解释、文法、**正规式、有限自动机、表达式、传值与传址、**多种程序语言特点
编译与解释
画板
文法的定义以及语法推导树
文法定义
一个形式文法是一个有序四元组G=（V，T，S，P），其中：
1）V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符。
2）T：终结符。是语言的组成部分，是最终结果。VnT=
3）S：起始符。是语言的开始符号。
4）P：产生式。用终结符替代非终结符的规则。形如α→β
正则闭包：A+=A1UA2UA3UUAU.（也就是所有幂的组合）
闭包：A=A°UA+（在正则闭包的基础上，加上A={c}）。
例如a²=[a,aa,aaa,.,e}，而（ab)={ab,abab,ababab,.,c}
文法的类型
| 类型 |
别称 |
说明 |
对应自动机 |
| 0型 |
短语文法 |
G的每条产生式a一P满足a属于V的正则闭包
且至少含有一个非终结符，而属于V的闭包 |
图灵机 |
| 1 型 |
上下文有关文法 |
**G的任何产生式a一β满足 |
al<= |
| 2型 |
上下文无关文法 |
G的任何产生式为A一β，A为非终结符，β为V的闭包 |
非确定的下推自动机 |
| 3型 |
正规文法 |
G的任何产生式为A一αB或A一α，α属于非终结符的闭包，A、B都属于非终结符 |
有限自动机 |
语法推导树
一棵语法树应具有以下特征：
1.每个结点都有一个标记，此标记是V的一个符号：
2.根的标记是S：
3.若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在V中：
4.如果结点n的直接子孙，从左到右的次序是结点n，n.n，其标记分别是：A，A，A，那么A>A，AA，一定是P中的一个产生式。
有限自动机与正规式（非确定有限自动机（NFA）、确定有限自动机（DFA））
有限自动机
image
S是一个有限集，每个元素为一个状态
是一个有穷字母表，每个元素为一个输入字符
是转换函数：是一个单值对照
S0，属于S，是其唯一的初态
Z是一个终态集(可空)
正规式（对有限自动机的另一种表达形式）
:::color1
正规式是描述程序语言单词的表达式，对于字母，其上的正规式及其表示的
正规集可以递归定义如下。
①ε是一个正规式，它表示集合L（E）={e}。
②若a是Z上的字符，则a是一个正则式，它所表示的正规L（a）={a}。
③若正规式r和s分别表示正规集L（r）=L（s），则
（a）r|s是正规式，表示集合L（r）UL（s）：
（b）r·s是正规式，表示集合L（r)L（s）；
（c）r是正规式，表示集合（L（r））；
（d）（r）是正规式，表示集合L（r）。
仅由有限次地使用上述三个步骤定义的表达式才是上的正规式。由此可见，
正规式要么为空，要么由字母、或、连接、闭包运算符组成。其中闭包运算符
“*”具有最高的优先级，连接运算具有次高优先级，或运算符“1”具有最低
优先级。
:::
表达式（逆波兰式/后序式）。解析逆波兰式的时候仅需要从左到右依次解析即可，但要考虑括号的优先级。
前缀表达式（+ab）
中缀表达式（a+b)
后缀表达式（ab+）
画板
函数调用（传值与传址）
| 传递方式 |
主要特点 |
| 传值调用 |
形参取的是实参的值，形参的改变不会影响实参的值【单向】 |
传址调用
引用调用
指针调用 |
形参取的是实参的地址，形参的改变会影响实参的值【双向】 |
多种程序语言的特点
1.Fortran语言（科学计算，执行效率高）
2.Pascal语言（为教学而开发的，表达能力强，Delphi）
3.C语言（指针操作能力强，高效）
4.Lisp语言（函数式程序语言，符号处理，人工智能）
5.C++语言（面向对象，高效）
6.Java语言（面向对象，中间代码，跨平台）
7.C#语言（面向对象，中间代码，.Net）
8.Prolog语言（逻辑推理，简洁性，表达能力，数据库和专家系统）