# 程序设计语言与语言处理程序基础
- 编译与解释
- 文法
- 正规式
- 有限自动机
- 表达式
- 传值与传址
- 多种程序语言特点
# 编译过程
源程序 -> 词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 代码优化 -> 目标代码生成 -> 目标程序
- 词法分析:关键词是否有误。
- 语法分析:语法问题,缺符号等。
- 语义分析:循环有没有终止的条件,是不是有零除的情况等,只能分析出一部分语义错误。
- 目标代码生成:中间代码转低级语言代码,需要考虑硬件系统结构。
# 文法定义
一个形式文法是一个有序四元组G=(V, T, S, P),其中:
- V:非终结符。不是语言组成部分,不是最终结果,可理解为占位符。
- T:终结符。是语言的组成部分,是最终结果。V⋂T=∅
- S:起始符。是语言的开始符号。
- P:产生式。用终结符代替非终结符的规则。形如 a -> b
类型 | 别称 | 说明 | 对应自动机 |
---|---|---|---|
0型 | 短语文法 | G的每条产生式a->b满足a属于V的正则闭包且至少含有一个非终结符,而b属于V的闭包。 | 图灵机 |
1型 | 上下文有关文法 | G的任何产生式a->b满足|a|<=|b|,仅仅S->例外,但S不得出现在任何产生式右部。 | 线性界限自动机 |
2型 | 上下文无关文法 | G的任何产生式为A->b,A为非终结符,b为V的闭包。 | 非确定的下推自动机 |
3型 | 正规文法 | G的任何产生式为A->aB或A->a,a属于非终结符的闭包,A、B都属于非终结符。 | 有限自动机 |
# 语法推导树
一棵语法树应具有以下特征:
- 每个结点都有一个标记,此标记是V的一个符号;
- 根的标记是S;
- 若一结点n至少有一个它自己除外的子孙,并且有标记A,则A肯定在 Vn 中
- 如果结点n的直接子孙,从左到右的次序是结点n1,n2,n3...nk,其标记分别是:A1,A2,...Ak,那么A->A1,A2,...Ak,一定是P中的一个产生式。
# 有限自动机
就是有限的路径图,生成有限的数据。
# 正规式
例如以下文法:
G[S]: S->aA|bB , A->bS|b , B->aS|a
大写字母相当于函数,小写字母直接输出。
以上文法对应的正规式为:(ab|ba)*
# 表达式
- 前缀表达式(+ab): 算数符号在前面。
- 中缀表达式(a+b): 算数符号在中间。
- 后缀表达式(ab+): 算数符号在最后。
例如:表达式 (a-b)*(c+5)的后缀式是(D)
- A.a b c 5 + * -
- B.a b - c + 5 *
- C.a b c - * 5 +
- D.a b - c 5 + *
# 传值与传址
传递方式 | 主要特点 |
---|---|
传值调用 | 形参取的是实参的值,形参的改变不会导致调用点所传的实参的值发生改变。 |
引用(传址)调用 | 形参取得是实参的地址,即相当于实参存储单元的地址引用,因此其值的改变同时就改变了实参的值。 |
传值相当于复制一份值,修改不影响本体。传址的话,修改的是本体。
# 各种程序语言的特点
语言 | 特点 |
---|---|
Fortran | 科学计算,执行效率高 |
Pascal | 为教学而开发的,表达能力强,Delphi |
C | 指针操作能力强,高效 |
Lisp | 函数式程序语言,符号处理,人工智能 |
C++ | 面向对象,高效 |
Java | 面向对象,中间代码,跨平台 |
C# | 面向对象,中间代码,.Net |
Prolog | 逻辑推理,简洁性,表达能力,数据库和专家系统 |