📝 软考专项：上午题 #2 程序设计语言

一、语言与程序

低级语言和高级语言

• 低级语言
• 机器语言：0和1
• 汇编语言：ADD、SUB，用符号表示的指令称为汇编指令，汇编指令的集合是汇编语言。

• 高级语言
• 面向各类应用的程序设计语言

编译程序和解释程序

• 由于计算机只能理解0和1 序列构成的机器语言，因此高级程序设计语言需要翻译，担负这一任务的程序被称为“语言处理程序”。语言之间的翻译形式有很多种，基本方式为汇编、解释和编译。

• 用某种高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机上执行。如果源程序是汇编语言编写的，那么需要一个汇编程序将其翻译成对应的目标程序后才能执行。如果源程序是用高级语言编写的，那么需要对应的解释程序或编译器对其进行翻译，然后再机器上运行

• 解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间代码后加以执行；而编译程序则是将源程序翻译成目标语言程序，然后再计算机上运行目标程序。
• 根本区别：在编译方式下，机器运行的是与源程序等价的目标程序，源程序与编译程序都不参与幕布秒程序的执行过程；而在解释方式下，解释程序和源程序要参与到程序的运行过程中，运行程序的控制权在解释程序。
• 简单来说，在解释方式下翻译源程序时不产生独立的目标程序，而编译器则将源程序翻译成独立保存的目标程序。

总结

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

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

二、函数

传值调用

• 若实现函数调用时将实参的值传给相应的形参，则称为是传值调用，在这种方式下形参不能向实参传递信息

• 实参可以是变量、常量和表达式。

引用（传地址）调用

• 当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上是针对相应实参所做的访问和改变。

• 将实参的地址传给形参，实参必须有地址

• 实参不能是常量，表达式。

• 可以实现形参和实参双向传递数据

三、编译、解释程序翻译阶段

• 编译方式
• 词法分析
• 语法分析
• 抑郁分析
• 中间代码生成
• 代码优化
• 目标代码生成

• 解释方式
• 词法分析
• 语法分析
• 语义分析

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

• 编译器方式中中间代码生成和代码优化不是必要，可省略。即编译器方式最后一步是目标代码生成

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

四、编译过程

• 编译程序的功能是把某高级语言书写的源程序防疫成预支等价的目标程序（汇编语言或机器语言）。编译程序的工作过程可以分为6个阶段，词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。其中中间代码生成和代码优化可省略

词法分析（输出是记号流）

• 源程序可以简单的被看成是一个多行的字符串，词法分析阶段是编译规程的第一个阶段，这个阶段的任务是对源程序从前到后逐个字符的扫描，从中识别出一个个单词符号。“单词”符号是程序设计的基本语法单位，如关键字、边师傅、常熟运算符分隔符等。词法分析程序输出的单词常以二元组的方式输出，即单词种别和单词自身的值。例：

语法分析（输出是语法树）

• 其任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如表达式 语句 和程序等。语法规则就是各类语法单位的构成规则，通过语法分析确定整个输入串是否构成一个语法上正确的程序。如果源程序中没有语法错误，语法分析后就能正确的构造出其语法树；否则支出语法错误，并给出相应的诊断信息。

• 语法分析阶段可以发现程序中的所有语法错误

语义分析（输入是语法树）

• 语义分析阶段的主要作用是进行类型分析和检查

• 语义分析阶段不能发现程序中所有的语义错误，可以发现静态语义错误，不能发现动态语义错误，动态语义错误运行时才能发现。

目标代码生成

• 该阶段的工作与具体的机器密切相关

• 寄存器的分配处于目标代码生成阶段

疑难点

• 词法分析、语法分析、语义分析，二法一义

• 词法分析扫描字符识别单词

• 语法分析判断程序语句的形式是否正确（结构），语法分析能发现所有的语法错误

• 语义分析不能发现所有语义错误，进行类型分析和检查

动态语义错误

• 语义分析只能检测出静态的语义错误，动态语义错误要在程序运行时才能检测出来

中间代码生成

• 其共同特征是与具体的机器无关，可以将不同的高级程序语言翻译成同一种中间代码，中间代码可以跨平台。

• 因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性。

• 常见的中间代码有：后缀式、三地址码、三元式、四元式和树（图）等形式

正规式

• 词法分析的一个工具

有限自动机

• 是词法分析的一个工具，它能正确地识别正规集

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

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

上下文无关文法

• 属于乔姆斯基定义的2型文法，被广泛的用于表示各种程序设计语言的语法规则。

五、中缀、后缀表达式转换

• a ？b

• ab？

• 1、（） 2、x / 3、+ -

• 优先级相同，从右向左

语法树中序后序遍历

• 中序遍历：左根右，得到中缀式

• 后序遍历：左右根，得到后缀式

疑难点

• 逻辑与相当于乘号，逻辑或相当于加号

• 在看二叉树表示的算术表达式时，根据中序（左根右）求时，需要注意+、-是一个结果，带括号

• 脚本语言（JS、PHP、PY）属于动态语言，其程序结构可以在运行中改变，一般通过脚本引擎执行，不产生独立保存的目标程序（解释器不产生目标程序，编译器产生目标程序）

• 栈是局部变量以及每次函数调用时所需保存的信息的存储区域，其空间的分配和释放由操作系统进行管理。每次函数调用时，其返回地址以及调用者的环境信息（例如某些寄存器）都存放在栈中。然后再栈中为新北调用的函数的自动和临时变量分配存储空间。栈空间向低地址方向增长。

• 堆是一块动态存储区域，由程序员在程序中尽显分配和释放，若程序语句没有释放，则程序结束时由操作系统回收。堆空间地址的增长方向是从低地址向高地址。在C程序中，通过调用标准库函数malloc/calloc/readloc等向系统动态的申请堆存储空间来存储相应规模的数据，之后用free函数释放所申请到的存储空间

• 用C/C++语言为某个应用编写的程序，经过预处理、编译、汇编、链接后形成可执行程序。

• Java语言符合的特征有
• 采用即时编译
• 对象在堆空间分配，new出来的
• 自动的垃圾回收处理

• Python语言的特点
• 跨平台、开源
• 支持面向对象程序设计
• 动态编程

• Python中
• 元祖(tuple)不可变
• 列表(list)可变、有序的序列结构，其中元素可以重复
• 集合(set)去重
• 字符串不可变