软考 软件设计师基础笔记二：程序设计语言_软考正则表达式

本节知识架构：

程序设计语言的基本概念

低级语言与高级语言：

• 低级语言：汇编
• 高级语言：常见的有Java、C、C++、PHP、Python等

翻译形式：汇编、解释、编译
程序设计语言的定义：语法、语义、语用
程序设计语言的分类：

• 过程式（命令式和结构式）：FORTRAN、Pascal、C
• 面向对象：Simula、Smalltalk、C++、Objective C、Java、Python
• 函数式：lisp、python、scala
• 逻辑式：Prolog
• 脚本语言：shell、bat、js、python

程序设计语言的基本成分

程序语言的节本成分包括数据、运算、控制和函数等。
数据

• 常量和变量
• 全局量和局部量
• 数据类型

运算：算术式运算、关系运算、逻辑运算
控制：顺序结构、选择结构、循环结构

函数：定义、声明、调用（值调用、引用调用）
值调用：形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变。
引用调用：形参取的是实参的地址，相当于实参存储单元的地址引用，值的改变同时改变形参的值。

汇编程序基本原理

汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化程序设计语言。
汇编程序是因为计算机不能直接识别和运行符号语言程序，所以专门的一种翻译程序。将汇编语言翻译成机器指令的程序。

• 第一次扫描：检查语法错误，确定符号名字；建立使用的全部符号名字表；每一符号名字后缀一个对应值（地址或数值）
• 第二次扫描：在第一次扫描的基础上，将符号地址转换成真地址（代真）；利用操作码表将助记符转换成相应的目标码。

汇编语言源程序由若干条语句组成，一个程序中可以有三类语句：指令语句、伪指令语句和宏指令语句。

编译程序的基本原理

编译程序的工作过程分为六个阶段：

文法：以有穷的集合描述无穷的计划的工具。根据对文法施加不同的限制，分成4种类型。

• 0型或短语文法：任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言。总之一般文法都是0型文法。
• 1型文法：又称为上下文有关文法
• 2型文法：又称为上下文无关文法
• 3型文法：又称为正规文法（正规文法又包括左线性文法和右线性文法）

有限自动机：确定有限自动机（DFA）和非确定有限自动机（NFA），都是进行词法分析的适当工具。

正则表达式是以下中的一种：

基本正则表达式由单个字符a(其中a在正规字符的字母表 ∑ 中)，以及元字符ε或元字符 Φ。 分别表示为：

L(a) = {a};
L(ε) = {ε};
L(Φ) = {}.

r|s格式的表达式：其中r和s均是正则表达式。在这种情况下：L(r|s) = L(r)|L(s)。
rs格式的表达式：其中r是正则表达式。在这种情况下：L(rs) = L(r)L(s)。
r格式的表达式：其中r是正则表达式。在这种情况下：L(r) = L(r)*。
(r)格式的表达式：其中r是正则表达式。在这种情况下：L((r)) = L(r)，因此，括号并不改变语言，它们只调整运算的优先级。
1
2
3
4
5
6
7
8
9
10

注意到这个定义中，|,*,(,),Φ,ε均为元字符。

r+ 正闭包，至少匹配一个

. 匹配任意一个字符

区间匹配 如[a-z],[0-9],[A-Za-z]

~a或^a 排除匹配

r? 可选匹配
1
2
3
4
5
6
7
8
9

有限自动机转为正规式：正规式转有限自动机反之。

解释程序基本原理

解释程序是另一种语言处理程序，在词法、语法和语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，它直接执行源程序或源程序的中间代码。解释程序不产生源程序的目标程序，这是它和编译程序的主要区别。