软件设计师笔记——（第二章：程序语言基础知识）

一、程序语言概述（⭐⭐）二、编译、解释程序（⭐⭐⭐）1、解释程序原理2、编译程序原理三、正规式与正规集（⭐⭐⭐）四、有限自动机（⭐⭐⭐）五、语法分析（⭐⭐）六、琐碎知识点（⭐⭐）

大小胖虎

1197人浏览 · 2023-09-20 19:18:29

大小胖虎 · 2023-09-20 19:18:29 发布

一、程序语言概述（⭐⭐）

1、低级语言和高级语言

1、低级语言

机器语言：指用0、1字符串组成的机器指令
汇编语言：指用符号表示指令的语言

2、高级语言：面向各类应用的程序语言，如Java，C，C++，PHP，Python等。

3、程序设计语言规定在源程序中的数据都必须具有类型（无注释和关键字）:

便于为数据合理分配存储单元
便于对参与表达式计算的数据对象进行检查
便于规定数据对象的取值范围及能够进行的运算

2、编译程序和解释程序

源程序不能在计算机上运行，需要将高级语言通过编译程序翻译成目标程序才能执行。

1、编译程序：

翻译时将源程序翻译成独立保存的目标程序
机器上运行的是与源程序等价的目标程序
源程序和编译程序都不在参与目标程序的运行过程

2、解释程序：

翻译源程序时不生成独立的目标程序
解释程序和源程序要参与到程序的运行过程中

3、程序语言的分类

1、命令式程序设计语言

Fortran语言：(第一个高级程序设计语言，科学计算，执行效率高）
Pascal语言：（为教学开发，表达能力强）
C语言：（指针操作能力强，高效）（指针变量存储空间都相同）（链表空间采用堆存储分配策略）

2、面向对象程序语言

C++语言（C上增加了类机制，面向对象，高效，与C兼容）
Java语言（面向对象，中间代码，跨平台，通用的程序设计语言台）
Python（面向对象，解释型程序设计语言，通用的脚本语言）

3、函数式程序语言：大量使用递归

Lisp语言（函数式程序语言，符号处理，人工智能）

4、PHP：（服务器端脚本语言，动态语言、制作动态网页）

5、PROLOG：（逻辑式语言，表达能力强，建造专家系统、数据库）

重点：

C/C++常被用于操作系统开发；javascript、python是（脚本、解释型、动态语言）。
Java、c、c++、属于静态语言。

4、程序语言的基本成分

1、数据成分：常量、变量、全局变量、局部变量、数据类型

2、运算成分：算术、关系、逻辑等

3、控制成分：顺序、选择、循环结构

4、控制语句：复合、选择、循环语句

5、函数：

传值调用：将实参的值传递给形参。实参可以是变量、常量和表达式。

不可以实现形参和实参双向传递的效果（形参不影响实参）

传址调用（引用调用）：将实参的地址传递给形参。形参必须有地址，实参不能是常量（值），表达式。可以实现形参和实参双向传递数据的效果。

二、编译、解释程序（⭐⭐⭐）

1、解释程序原理

原理：编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（由机器码构成，计算机能直接运行的程序）。

编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成（编译程序不参与用户程序的控制）

解释方式：词法分析、语法分析、语义分析（解释程序参与用户程序的控制）

编译器：代码生成、代码优化不是必要的，可省略。（先翻译后执行，执行效率高但可移植性差）

解释器：不产生目标程序、执行效率低（反复扫描源程序）（边翻译边执行）

编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可换。

即编译器方式可以在词法分析、语法分析、语义分析之后直接生成目标代码。

2、编译程序原理

编译程序过程分为6个阶段：

1、词法分析：（输入：源程序，输出：记号流）——正规表达式、正规集

作用：分析构造程序字符、符号是否符合程序语言的规定（非法字符、单词拼写）

2、语法分析：（输入：记号流，输出：语法树）

语法分析阶段可以发现程序中所有的语法错误
作用：对各条语句的结构进行合法性分析（判断程序语句的形式），分析句子结构是否正确
语法错误：结构出错、少括号、变量未定义、括号不匹配
分配策略：（静态存储：编译时就确定空间大小）（动态存储：允许递归和可变数据结构。分为堆分配和栈分配）

3、语义分析：（输入：语法树/分析树）

语法分析阶段不能发现所有的语义错误（eg：动态语义，运行时才能发现）
静态语义错误：类型不一致、参数不匹配。（分析方法是语法制导翻译）
动态语义错误（逻辑错误）：死循环、变量0作除数（运行时产生异常）

4、中间代码生成：（结构简单且可以有多种形式）

不考虑机器的特性，与机器无关、可移植性高、跨平台性
中间代码起着解释器前端和后端分水岭是作用
常用的中间代码：后缀式、三元式、四元式、树（三地址码→三、四元式）

5、代码优化：（对中间代码进行优化，目的使目标代码更加高效）

可以在中间代码生成阶段、也可在目标代码生成阶段进行优化

6、目标代码生成：（与目标机器的体系结构密切相关）

寄存器的分配工作在目标代码生成阶段进行

7、符号表管理：

不断收集记录和使用源程序中一些相关符号的类型和特征信息，并将其存入符号表中，记录源程序各个字符必要的信息，辅助语义的正确性检查和代码生成。

三、正规式与正规集（⭐⭐⭐）

1、正规表达式

2、正规集

3、经典例题

一、例题一

A：a，b的数目不一定相同

B：当m=0时，不符合题意

C：正规式和有限自动机可以相互转化，如果不能用正规式表示，则也不能用有限自动机表示

二、例题二

三、例题三

四、有限自动机（⭐⭐⭐）

有限自动机是词法分析的一个工具，它能正确地识别正规集。

确定的有限自动机（DFA）：对每一个状态来说识别字符后转移的状态是唯一的。
不确定的有限自动机（NFA）：对每一个状态来说识别字符转移的状态是不唯一的。

1、经典例题

一、例题一

二、例题二

三、例题三

A、D：会出现连续两个“11”的情况，此时不符合题意；

C：会出现连续两个”00“的情况，此时不符合题意；

五、语法分析（⭐⭐）

1、递归下降思想：利用递归模拟树自上而下构造过程。
2、移进归纳思想：自下而上的语法分析。
3、上下文无关法：对于大多数通用程序设计语言。

1、上下文无关文法经典例题

一、例题一

二、例题二

三、例题三

六、琐碎知识点（⭐⭐）

1、编程是将高级语言源程序翻译成机器语言程序，反编程是编程的逆过程。反编程不能将可执行文件还原成高级语言源代码，只能还原成等价的汇编程序。

2、汇编程序输入的是汇编语言书写的源代码，输出的是机器语言表示的目标函数。

3、软件开发小组的沟通路径最多有（n×（n-1）/2)

4、编译过程中为变量分配存储单元所用的地址是逻辑地址，程序运行时再映射为物理地址。

5、程序运行时内存空间划分为（代码区、静态数据区、栈区、堆区），其中栈区和堆区是动态数据区。全局变量的存储空间在静态数据区。

6、运行时结合是动态绑定，编译时绑定是静态绑定。

<!DOCTYPE html> 声明为 HTML5 文档
<html> 元素是 HTML 页面的根元素
<head> 元素包含了文档的元（meta）数据，如 <meta charset="utf-8"> 定义网页编码格式为 utf-8。
<title> 元素描述了文档的标题
<body> 元素包含了可见的页面内容
<h1> 元素定义一个大标题
<p> 元素定义一个段落
<br>换行
<hr>定义水平线