【软考】程序设计语言基础

【软考】程序设计语言基础

一.程序设计语言基础概念

计算机要通过程序或指令来控制才能完成各种任务。程序设计语言（计算机语言）：人与机器交换信息的语言。

1.程序设计语言

计算机语言大致分为机器语言、汇编语言和高级语言三种。机器语言是计算机可以直接理解和执行的二进制代码，效率最高但难以编写。汇编语言用助记符代替机器指令，可读性比机器语言强，但仍与硬件紧密耦合。高级语言更接近自然语言，如C++、Python等，可移植性好、易于维护，但执行效率相对较低。编译型语言（如C++）需要先将源代码全部编译成机器码再执行，而解释型语言（如Python）则是一行一行解释执行，前者执行效率更高，后者更灵活。

机器语言（低级语言）
汇编语言（低级语言）
高级语言（分为解释型语言和编译型语言）

总结来说：

• 机器语言： 计算机的“母语”，效率高但晦涩难懂。
• 汇编语言： 机器语言的“速记”，可读性增强但仍依赖硬件。
• 高级语言： 人类友好的语言，可移植性好但效率相对较低。
• 编译型语言： 先编译后执行，效率高。
• 解释型语言： 边解释边执行，灵活度高。

选择哪种语言取决于具体应用场景。 如果对性能要求极高，可以选择机器语言或汇编语言；如果开发效率和可维护性更重要，可以选择高级语言；如果需要快速开发原型或脚本，解释型语言是不错的选择。

2.解释型语言和编译型语言

1、解释程序，也称解释器;直接解释执行源程序，或者将源程序翻译成某种中间代码后再加以执行
2、编译程序，也称编译器;将源程序翻译成目标语言程序，然后在计算机上运行目标程序。
3、两者的根本区别:编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程
序的执行过程，因此执行时效率较高;解释方式下，解释程序和源程序(或某种等价表示)要参与到程序的运行过
程中，运行程序的控制权在解释程序，边解释边执行，执行效率较低。即:解释方式下，翻译程序不生成独立的目
标程序，而编译方式则生成独立保持的目标程序。

总结

编译得到目标代码直接执行。解释得到中间代码，边解释边执行。编译型语言速度更高，但是灵活性差，解释型语言灵活性好，但是速度相对较慢。我举个例子，像C++那种，没办法写完直接在编译器里跑的就是编译型语言，他会生成一个exe文件给你运行，那像java或者python写完直接在解释器里跑就可以了。记住能一步到位直接跑的就是解释型，写完还要打开个新文件的就是编译型语言。

3.常见程序设计语言的特点

(适当记忆，看到了要能想起来这个东西是大概干嘛的就可以了)

Fortran语言(第一个高级程序设计语言，科学计算，执行效率高)

Pascal语言(结构化程序设计语言，表达能力强，Delphi)

C语言(通用、结构化程序设计语言，指针操作能力强，高效)

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

C++语言(C语言基础上增加了类机制，面向对象，高效，与C兼容)

Java语言(面向对象，中间代码，跨平台，通用的程序设计语言)

Python(面向对象，解释型程序设计语言，胶水语言，通用的脚本语言)

PHP(服务器端脚本语言，制作动态网页)

Ruby(简单快捷，面向对象，脚本语言)

Delphi(快速应用程序开发工具，可视化编程环境)

COBOL(数据处理领域最为广泛的程序设计语言，高级编程语言)

XML(可扩展标记语言，标准通用标记语言的子集)

PROLOG(逻辑式语言，间接性，表达能力强，建造专家系统、数据库、自然语言理解、智能知识库等)

注:C/C++常被用于操作系统开发;脚本语言是解释性语言。

4.程序语言设计的基础成分

4.1 程序设计语言的基本成分

程序设计语言作为人与计算机交流的工具，其基本成分主要包括：

• 数据： 程序处理的对象，包括各种类型的数据。
• 运算： 对数据进行操作，包括算术运算、逻辑运算等。
• 控制： 控制程序执行的流程，包括顺序结构、选择结构和循环结构。
• 传输： 数据在程序内部或不同程序之间传递。

4.2 程序设计语言的数据成分

4.2.1 C/C++语言基本数据类型

• 数字类型：
  • 整型：int、short、long、long long
  • 浮点型：float、double、long double
  • 字符型：char
• 布尔类型： bool
• 指针类型： 指向内存地址
• 枚举类型： enum

4.2.2 Java语言基本数据类型

• 数字类型：
  • byte、short、int、long
  • float、double
  • char
• 布尔类型： boolean
• 引用类型： 指向对象的引用

4.2.3 Python语言基本数据类型

• 不可变数据：
  • Number（数字）：int、float、complex
  • String（字符串）：由字符组成的序列
  • Tuple（元组）：有序不可变的元素集合
• 可变数据：
  • List（列表）：有序可变的元素集合
  • Dictionary（字典）：无序可变的键值对集合
  • Set（集合）：无序不可变的元素集合，元素不重复

特性	列表（list）	元组（tuple）	集合（set）	字典（dictionary）	字符串（string）
有序性	有序	有序	无序	无序	有序
可变性	可变	不可变	可变	可变	不可变
元素唯一性	允许重复	允许重复	不允许重复	键唯一	允许重复
访问方式	索引	索引	元素成员测试	键	索引
常见操作	append, insert, remove, pop, sort	连接，切片	交集，并集，差集	增删改查	切片，连接，查找，替换，分割
Java对应类型	ArrayList, LinkedList	Array	HashSet, TreeSet	HashMap, TreeMap	String

4.3运算成分

4.3.1 C/C++语言运算符

• 算术运算符： +、-、*、/、%、++、–
• 关系运算符： ==、!=、>、<、>=、<=
• 逻辑运算符： &&、||、!
• 位运算符： &、|、^、~、<<、>>
• 赋值运算符： =、+=、-=、*=、/=、%=、&=、|=、^=、<<=、>>=
• 其他运算符： sizeof、&（取地址）、*（解引用）、.（成员访问）、->（指针成员访问）

4.3.2 Java语言运算符

• 其他运算符： instanceof、new
• 其他的运算符差不多

4.3.3 Python语言运算符

• 成员运算符： in、not in
• 身份运算符： is、is not
• 其他的运算符差不多

补充说明：

• Java的引用类型： Java中所有对象都是通过引用来访问的。
• Python的动态类型： Python变量不需要事先声明类型，可以动态地改变类型。
• 不同语言的数据类型表示方式可能不同

特性	列表（list）	元组（tuple）	集合（set）	字典（dictionary）	字符串（string）
定义	有序可变的元素集合，用方括号 [] 表示	有序不可变的元素集合，用圆括号 () 表示	无序不重复的元素集合，用大括号 {} 表示	无序可变的键值对集合，用大括号 {} 表示，键必须唯一	由字符组成的有序序列，用单引号或双引号括起来
元素类型	任意数据类型，可以重复	任意数据类型，可以重复	任意不可变数据类型，不能重复	键必须是不可变数据类型（如字符串、数字），值可以是任意数据类型	字符
访问元素	通过索引访问，索引从 0 开始	通过索引访问，索引从 0 开始	不能通过索引访问，常用 in 操作符判断元素是否存在	通过键访问值	通过索引访问，索引从 0 开始
修改元素	可以直接修改元素的值	不能修改元素的值	不能修改元素，但可以添加或删除元素	可以修改键对应的值，也可以添加或删除键值对	不可修改单个字符，但可以创建新的字符串
添加元素	append()、insert() 等方法	不能添加元素	add() 方法	key=value 的形式添加键值对	不能直接添加，通常通过连接操作创建新字符串
删除元素	remove()、pop() 等方法	不能删除元素	remove() 方法	del 语句删除键值对	不能删除单个字符，但可以通过切片等操作创建新字符串
长度	len() 函数获取长度	len() 函数获取长度	len() 函数获取长度	len() 函数获取键值对个数	len() 函数获取字符个数
排序	可以排序	不能排序	元素无序	键无序，但值可以排序	可以排序
常见操作	切片、连接、循环、排序等	切片、连接、循环等	交集、并集、差集等	键的访问、值的修改等	切片、连接、查找、替换、分割等
应用场景	存储有序可变的数据，如列表、数组	存储有序不可变的数据，如常量、配置信息	存储不重复的元素，如去重、成员测试	存储键值对，如字典、配置文件	存储文本信息，如名字、地址、句子等

4.4 控制结构

程序的控制结构决定了程序执行的流程，是程序设计中非常重要的概念。除了您提到的顺序结构、选择结构和循环结构外，还有一些高级的控制结构，如函数调用、异常处理等。

4.4.1 顺序结构

顺序结构是最简单的控制结构，按照语句的书写顺序，从上到下依次执行。

print("Colored")
print("Feather")

4.4.2 选择结构

选择结构根据条件判断的结果，选择不同的执行路径。常见的选择结构有：

if语句： 当条件为真时，执行某个代码块。

age = 18
if age >= 18:print("You are an adult.")

if-else语句： 当条件为真时，执行一个代码块；否则执行另一个代码块。

age = 15
if age >= 18:print("You are an adult.")
else:print("You are a minor.")

switch-case语句： 根据表达式的值，选择不同的代码块执行（C/C++、Java等语言支持）。

4.1.3 循环结构

循环结构用于重复执行一段代码，直到满足某个条件为止。常见的循环结构有：

while循环： 当条件为真时，不断执行循环体。

count = 0
while count < 5:print(count)count += 1

for循环： 一般用于遍历序列（如列表、元组、字符串）中的元素。

for i in range(5):print(i)

do-while循环： 先执行一次循环体，再判断条件，如果条件为真，则继续执行。

4.1.4 其他控制结构

• 函数调用： 将一段代码封装成函数，通过函数名和参数调用。
• 异常处理： 处理程序运行时发生的异常，保证程序的健壮性。
• 跳转语句： 如break、continue，用于控制循环的执行。

4.1.5 控制结构的组合

在实际编程中，各种控制结构可以相互嵌套、组合，以实现复杂的逻辑。

# 嵌套循环
for i in range(3):for j in range(3):print(i, j)

图示

总结

知道程序设计语言的基础成分，以及Python中各种数据结构的区别，就元组，列表这些有什么共同点和不同点，运算和控制了解一下就可以了。

5.函数的调用方式

5.1函数的格式

函数是组织代码的常用方式，它将一段具有独立功能的代码块封装起来，方便重复调用。

函数的一般格式如下：

返回值类型 函数名(参数列表) {// 函数体
}

• 返回值类型： 函数执行完成后返回的值的类型。如果没有返回值，则使用关键字void。
• 函数名： 函数的标识符，用于调用函数。
• 参数列表： 函数接收的参数，用逗号分隔。每个参数都有一个类型和一个名称。
• 函数体： 函数的具体实现，包含一系列语句。

5.2函数的调用

函数的调用通过函数名，并传递实际参数来实现。

函数名(实参1, 实参2, ...)

5.3传值与传址

函数调用时，参数的传递方式主要有两种：传值和传址。

传值（pass by value）

• 概念： 将实际参数的值复制一份传递给函数形参。
• 特点： 函数内部对形参的修改不会影响实参的值。
• 示例：

void swap(int a, int b) {int temp = a;a = b;b = temp;
}int main() {int x = 10, y = 20;swap(x, y);cout << x << " " << y << endl;  // 输出：10 20
}

在上面的例子中，swap函数中的形参a和b是x和y的副本，在函数内部交换a和b的值，并不会影响x和y的值。

传址（pass by reference）

• 概念： 将实际参数的地址传递给函数形参。
• 特点： 函数内部对形参的修改会直接影响实参的值。
• 示例：

void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}int main() {int x = 10, y = 20;swap(&x, &y);cout << x << " " << y << endl;  // 输出：20 10
}

在上面的例子中，swap函数的形参a和b是指向x和y的指针，在函数内部通过指针修改了x和y的值。

5.4传值与传址的对比

特点	传值	传址
参数传递方式	将实际参数的值复制一份	将实际参数的地址传递给形参
函数内部对参数的修改	不影响实参	影响实参
使用场景	一般情况下，如果函数不需要修改实参的值，使用传值	当函数需要修改实参的值时，使用传址

总结

知道传值与传址的对比并且要看得明白具体题目那个值是怎么传的，理解传值与传址的对比，传值就好比你去copy一份别人电脑的数据过来，你怎么折腾都不会影响别人电脑的内容，传地址就好比你直接在别人的电脑上折腾，影响这台电脑下一次copy给别人的值。

二.语言处理程序

1.编译过程概述

(要了解每个阶段都在干嘛，错误分析阶段要学会判断归属)

其中无论是编译型还是解释型错误分析都是必须做的（语法分析，词法分析，语意分析），而中间代码生成和代码优化是看情况来的，可做可不做。出错处理和符号表管理贯穿全程，会在符号表中处理。

编译过程将高级语言编写的源代码转换为计算机能够直接执行的机器码。整个过程可以分为以下几个阶段：

1. 1词法分析 (Lexical Analysis)

是编译过程的第一阶段，其任务是对源程序从前到后(从左到右)逐个字符扫描，从中识别出
一个个“单词”符号。词法分析过程的依据是语言的词法规则，即描述“单词”结构的规则。

• 输入: 源程序的字符序列

• 输出: 记号流 (Token Stream)

• 任务:

  • 从左到右逐个扫描源程序的字符。
  • 识别出有意义的最小单位——单词符号（Token），如关键字、标识符、常量、运算符、分隔符等。
  • 去除源程序中的注释和空白符。

• 示例:

  这个就是看你拼写上有没有问题，会不会出现什么非法字符什么的。

  源代码：VAR XY,Z:real; X:=Y+Z*60;
  记号流：VAR, XY, , Z, :, real, ;, X, :=, Y, +, Z, *, 60, ;
  

常用方法

• 有限自动机（Finite Automata）：用于识别词法单元（tokens），有限自动机可以是确定的有限自动机（DFA）或非确定的有限自动机（NFA）。
• 正则表达式（Regular Expressions）：用于定义词法单元的模式，正则表达式可以转换为有限自动机。
• 词法生成器（Lexer Generators）：如Flex，它们使用正则表达式来生成词法分析器的代码。

1.2语法分析 (Syntax Analysis)

其任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位。通常语法分析是确定整个输入串是否构成一个语法上正确的程序。一般来说，通过编译的程序，不存在语法上的错误。

• 输入: 记号流

• 输出: 语法分析树 (Parse Tree) 或语法分析表

• 任务:

  • 根据语言的语法规则，将记号流组织成语法结构，如表达式、语句、函数等。
  • 检查源程序是否符合语法规则。

• 示例:

  这个更多体现在你的命名是否合法，或者说你的数据类型是否正确，比如说你用来放整数就用int，别用double这种，以及像9a这种以数字开头的非法命名等，还有其他结构上比如循环结构if…end if不匹配，缺少分号、括号不匹配、表达式缺少操作数等。

常用方法

• 上下文无关文法（Context-Free Grammar, CFG）：用于描述编程语言的语法结构。
• 递归下降解析器（Recursive Descent Parsers）：一种自顶向下的解析方法，通过递归函数调用实现。
• LL解析器（LL Parsers）：预测分析的一种形式，从左到右读取输入，并从左端进行最左推导。
• LR解析器（LR Parsers）：从左到右读取输入，并从右端进行推导，如SLR(1)、LALR(1)、LR(1)解析器。

1.3 语义分析 (Semantic Analysis)

其任务主要检査源程序是否包含静态语义错误(动态语义错误在执行过程中才能发现)，并收集类型信息供后面的代码生成阶段使用。语义分析的一个主要工作是进行类型分析和检查。

• 输入: 语法分析树

• 输出: 带有类型信息的语法分析树或中间代码

• 任务:

  • 检查程序的静态语义错误，如类型不匹配、变量未声明、数组越界等。
  • 收集类型信息，为后面的代码生成做准备。
  • 进行类型检查和转换。

• 示例:

  运算符和运算类型不符合，如取余时用浮点数，再比如字符串的拼接“Colored”+“Feathers”可以，但是如果换成-号就不行了，会报错，这些东西会在静态语义分析阶段就会报错。

  • 检查 X:=Y+Z*60; 中，变量 X, Y, Z 的类型是否为 real，运算符 +, * 是否适用于 real 类型。

特点	静态语义分析	动态语义分析
执行时间	编译期间	运行期间
检查对象	程序的结构和类型	程序的运行时行为
发现错误类型	类型错误、语法错误、未声明变量等	空指针引用、数组越界、除以零等
局限性	无法发现所有错误，例如运行时产生的错误	需要在运行时执行，效率较低

常用方法

• 属性文法（Attribute Grammars）：用于定义和计算语言结构上的属性。
• 类型检查（Type Checking）：确保操作数类型正确，变量在使用前已声明等。
• 符号表（Symbol Table）：用于存储变量名、函数名、类名等标识符的信息，以及它们的属性。

1.4中间代码生成 (Intermediate Code Generation)

其任务是根据语义分析的输出生成中间代码。此阶段不是必须的。常见的中间代码有:树、后缀式、三地址码(四元式)。

• 输入: 带有类型信息的语法分析树

• 输出: 中间代码 (Intermediate Code)

• 任务:

  • 将语法分析树转换为一种机器无关的中间表示形式，如后缀式、三地址码、四元式、树等。
  • 中间代码更易于优化和生成目标代码。

• 示例:

  • 三地址码：

    t1 := Z * 60
    t2 := Y + t1
    X := t2
    

常用方法

• 三地址代码（Three-Address Code）：一种简化的机器无关的中间表示形式。
• 抽象语法树（Abstract Syntax Tree, AST）：表示源代码的抽象语法结构的树形结构。

1.5 代码优化 (Code Optimization)

其任务是优化中间代码。此阶段不是必须的。

• 输入: 中间代码
• 输出: 优化后的中间代码
• 任务:
  • 对中间代码进行优化，提高目标代码的执行效率。
  • 常见的优化技术有常量折叠、公共子表达式消除、死代码消除等。
• 示例:
  • 如果 Z 的值在程序中始终为常数，那么 Z * 60 可以提前计算。

常用方法

• 数据流分析（Data Flow Analysis）：分析程序中变量的定义和使用，以优化代码。
• 控制流分析（Control Flow Analysis）：分析程序的控制结构，以优化代码。
• 变换规则（Transformation Rules）：用于转换程序代码，以改善性能和效率。

1.6 目标代码生成 (Code Generation)

是编译器工作的最后一个阶段。其任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。本阶段与具体机器密切相关。

• 输入: 优化后的中间代码

• 输出: 目标机器代码

• 任务:

  • 将优化后的中间代码翻译成特定机器的机器指令。

• 示例:

  • x86汇编代码：

    MOV EAX, [Z] ; 将Z的值加载到EAX寄存器
    IMUL EAX, 60 ; EAX = EAX * 60
    ADD EAX, [Y] ; EAX = EAX + Y
    MOV [X], EAX ; 将EAX的值存入X
    

常用方法

• 目标代码优化（Target Code Optimization）：针对特定目标机器的代码优化。
• 寄存器分配（Register Allocation）：将变量映射到处理器的寄存器。
• 指令选择（Instruction Selection）：将中间代码映射到目标机器的指令集。

总结

编译过程是一个将高级语言转换为机器语言的过程，每个阶段都有其特定的任务。通过词法分析、语法分析、语义分析等阶段，编译器逐步将源代码转化为机器可执行的指令，考试能知道什么问题在哪个阶段能被看出来就够了，大致了解一下各阶段的常用方法。

补充几点

1.自顶向下(或自上而下) 分析法【递归下降分析法、预测分析法都是自顶向下的分析方法。】自底向上语法分析方法(移进归约分析法)、

2.符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作。符号表的存在可以贯穿编译所有阶段。

3.错误管理
**静态错误:**编译时所发现的程序错误，分为语法错误和静态语义错误,
**语法错误包含:**单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误。【单词拼写错误、标点符号错误(中文符号等)属于词法错误;缺少分号、缺少括号、缺少操作数属于语法错误。】
**静态语义分析:**运算符与运算对象类型不合法等错误。
**动态错误:**发生在程序运行时，也叫动态语义错误。包括死循环、变量取零时做除数、引用数组元素下标越界等错
误。

二.文法

文法速通

（会推会做题就行）

我举个例子，比如文法G=({a,b},{S,A},S,P),其中：S能推出aAS|a；A能推出SbA|SS|ba，请你来构造句型aabAa的推导树，如下图所示。从一开始的S开始慢慢去构造，一开始S推aAS，这样我们就完成了a的构造，然后再看剩下的AS，ASA可以推SbA，这样S就可以变成a，我们就可以得到aabAS，S可以推a，这样就可以得到aabAa了。

如果看不懂我给你说详细点：

首先，我们要构造的句型是aabAa，使用的文法G=({a,b},{S,A},S,P)，其中产生式规则P如下：

• S → aAS | a
• A → SbA | SS | ba

下面是构造句型aabAa的详细步骤：

1. 从起始符号S开始，我们选择产生式S → aAS，这样我们得到了句型aAS。这一步我们完成了第一个字符’a’的构造。
2. 接下来，我们需要处理剩下的部分AS。我们选择A的产生式A → SbA，将A替换为SbA，得到句型aaSbAS。
3. 现在我们关注第二个S，我们再次使用S的产生式S → a，将S替换为’a’，得到句型aabAS。
4. 最后，我们处理剩下的部分AS。我们选择A的产生式A → ba，将A替换为’ba’，得到最终的句型aabAa。

综上所述，通过以下步骤我们构造出了句型aabAa：

• S → aAS → aaaSbAS → aabaAS → aabAa

如果想看文法相关的概念就继续往下看就好了。

1.什么是文法？

在计算机科学中，尤其是编译原理领域，文法是一种用来描述形式语言的工具。它通过一系列规则定义了语言中所有合法句子的结构。这些规则通常以产生式的方式给出，描述了如何从起始符号开始，逐步生成语言中的句子。

2.文法的组成部分

• 终结符: 语言中最小的不可再分的符号，它们构成了句子的基本元素。例如，在编程语言中，关键字、标识符、常量等都是终结符。
• 非终结符: 表示语法结构的符号，它们可以被替换成更小的子结构。通常用大写字母表示。
• 产生式: 描述了非终结符如何被替换成更小的子结构或终结符的规则。
• 开始符号: 文法中唯一的非终结符，表示整个句子的开始。

3.文法的类型

根据产生式的形式，文法可以分为不同的类型：

• 0型文法: 最一般的文法形式，没有限制。
• 1型文法: 上下文敏感文法，产生式的左部和右部长度存在限制。
• 2型文法: 上下文无关文法，产生式的左部只有一个非终结符。
• 3型文法: 正则文法，产生式的右部最多有一个非终结符，并且位于开头或结尾。

4.上下文无关文法（Context-Free Grammar, CFG）

上下文无关文法是编译原理中最常用的文法类型。它的产生式形式为：

A -> α

其中，A 是非终结符，α 是由终结符和非终结符组成的字符串。

示例：

一个简单的算术表达式的上下文无关文法：

E -> E + T | E - T | T
T -> T * F | T / F | F
F -> ( E ) | id | num

其中：

• E：表达式
• T：项
• F：因子
• id：标识符
• num：数字*

5.语法分析

语法分析是编译过程中的一个重要阶段，它的任务是根据文法规则，分析输入的字符串是否符合该文法。常用的语法分析方法有：

• 自顶向下分析: 从文法的开始符号出发，逐步向下推导，直到匹配输入字符串。
• 自底向上分析: 从输入字符串出发，逐步向上归约，直到归约到文法的开始符号。

6.文法在编译原理中的应用

• 语法定义: 文法用来精确地定义编程语言的语法结构。
• 语法分析: 编译器通过语法分析器，根据文法规则检查源程序的语法正确性。
• 代码生成: 语法分析树可以作为代码生成阶段的输入，生成目标代码。

总结

文法是描述形式语言的强大工具。通过文法，我们可以精确地定义编程语言的语法，并进行语法分析。上下文无关文法是编译原理中最常用的文法类型。理解文法的概念和应用，对于深入学习编译原理具有重要意义。但是对于考试来说你要能理解能算就够了。

三.正规式与正规集

速通正规式与正规集

（这个考的挺简单的，我给你举个例子）

由字符a、b构成的字符串中，若每个a后至少跟子个b则该字符串集合可用正规式表示为()。

A.(b|ab)*   B.(ab*)*   C.(a*b*)*   D.(a|b)*

我个人觉得这个还是蛮简单的，选A,每个a后面要有个b，那么就a肯定不会单独出现，所以CD就错了，b可以自己出现，所以B排除，就选A咯，如果看懂了的话这部分内容就可以了，不懂或者想多学点就继续往下看吧。

正规式（Regular Expression）和正规集（Regular Set）是形式语言和编译原理中的基本概念。下面分别讲述它们的相关内容，并提供适当的例子。

1.正规式（Regular Expression）

正规式是一个用于描述字符串集合的数学表达式，它由以下元素组成：

• 字母表中的单个字符（例如，a, b, 0, 1）
• 空字符串 ε（表示没有任何字符的字符串）
• 并运算符 ∪（表示选择，“或”）
• 连接运算符（通常省略不写，表示字符串的连接）
• 闭包运算符 *（表示零次或多次重复）

正规式的运算规则如下：

• 字母表中的字符本身是一个正规式，它所表示的正规集就是包含该字符的集合。
• ε 是一个正规式，它所表示的正规集只包含空字符串 ε。
• 如果 r 和 s 是正规式，那么 r∪s、rs 和 r* 也是正规式，分别表示它们的并集、连接和闭包。

2.正规集（Regular Set）

正规集是由正规式定义的字符串集合。换句话说，正规集是可以通过正规式来描述的所有可能字符串的集合。

举个例子，假设字母表为 Σ = {a, b}，以下是一些正规式和它们对应的正规集的例子：

正规式	正规集描述	具体例子（假设字母表为{a, b}）
a	包含单个字符 ‘a’ 的集合	{a}
ε	只包含空字符串 ε 的集合	{ε}
a∪b	包含字符 ‘a’ 或 ‘b’ 的集合	{a, b}
ab	包含字符串 “ab” 的集合	{ab}
a*	包含零个或多个 ‘a’ 的字符串集合	{ε, a, aa, aaa, …}
(a∪b)*	包含任意由 ‘a’ 和 ‘b’ 组成的字符串集合	{ε, a, b, aa, ab, ba, bb, aaa, aab, …}
a*b	以零个或多个 ‘a’ 开头，后接 ‘b’ 的字符串集合	{b, ab, aab, aaab, …}
(ab)*	包含零个或多个 “ab” 序列的字符串集合	{ε, ab, abab, ababab, …}

四.有限自动机

速通有限自动机

这种题一般都会给你个图然后去让你分析，你要看什么东西能到末状态，

举个例子，比如下面这张图，其中A是起始状态，C是末状态，也就是结束状态。从A开始看也就是蓝线部分，是1是0是无法确定的，而观察红线部分如果要到达结束状态，那么这个结尾肯定是。所以选项D结尾不一定是1，所以排除D，然后再看开头部分，可以以1开始，也可以以10、010、10、110开始都行，但是B,C,D都是1一定在0的前面，这是不对的，所以这道题选A。其实题选什么不重要，主要是要学会先分析结尾字符，一定以什么结尾，再分析起始字符，如果实在不行再代入也是可以的

下图所示为一个有限自动机(其中，A是初态、C是终态)，该自动机识别的语言可用正规式()表示。
A.(0|1)*01  B.1*0*10*1  C.1*(0)*01  D.1*(0|10)*1*

再举一个简单点的例子：

下图所示为一个不确定有限自动机(NFA)的状态转换图。该NFA可识别字符串()。
A、0110
B、0101
C、1100
D、1010

和上面一样，先分析结尾，肯定是以0结束，所以B排除，开头以0开头，所以CD排除剩下A就是对的。如果遇到排完还有其他选项你就代入进去看看就知道了。

1.基本定义

有限自动机（Finite Automaton）是理论计算机科学中的一个基本概念，它是计算理论中的一个抽象模型，用来进行字符串的识别和处理。有限自动机广泛应用于自然语言处理、编译原理、网络协议、软件工程等领域。以下是有限自动机的相关概念及内容：

M=(S,∑, δ,S0,Z)
1)S是一个有限集，每个元素为一个状态
2)∑是一个有穷字母表，每个元素为一个输入字符
3)8是转换函数:是一个单值对照
4)S0,属于S，是其唯一的初态
5)Z是一个终态集(可空)

2.分类

有限自动机能够识别的串:从初态出发可以到达终态且停留在终态
**确定的有限自动机:**当一个状态面对一个输入符号的时候，所转换到的是一个唯一确定的状态。
**不确定的有限自动机:**当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合

3.特点

• 有限自动机的状态数是有限的。
• 有限自动机在任一时刻只处于一个状态。
• 有限自动机的下一个状态完全由当前状态和当前输入决定。

4.运行方式

有限自动机的运行过程可以看作是在输入字符串上的一个动作序列：

1. 开始时，自动机处于初始状态 s0s0。
2. 逐个读取输入字符串中的符号。
3. 根据当前状态和输入符号，使用状态转移函数 δδ 转移到下一个状态。
4. 重复步骤 2 和 3，直到输入字符串结束。
5. 如果最后自动机处于一个终止状态，则称该自动机接受了这个字符串；否则，字符串被拒绝。

5.应用

• 模式匹配：例如，正则表达式引擎可以用有限自动机实现。
• 文本分析：用于语言识别、词法分析等。
• 协议解析：网络协议中的状态管理。

6.与其他计算模型的比较

有限自动机是计算模型中最基本的一种，它的计算能力弱于图灵机，但强于更简单的模型如有限状态机（ FSM，它没有输入字母表的概念）。DFA 和 NFA 在计算能力上是等价的，即任何 NFA 都可以转换成等价的 DFA。

有限自动机的理论研究和实际应用对于理解计算机科学中的基本概念和设计高效算法都具有重要的意义。

五.表达式

表达式速通

（要会画图分析就可以了）

写这种表达式的题的时候最好把图画出来，这样容易看很多，也有一些小技巧，我举个例子，比如说（A*B）+（C-D）花出来图就下面这个样子，然后其中蓝色球按顺序连起来就是前序遍历，黄色球连起来就是中序遍历，红色球连起来就是后续遍历，如果听不懂就看下面的图或者其他例子吧。

前序遍历示图，其他的也一样，蓝线进过蓝球的顺序就是前序遍历，再换一条线连接黄色球就是中序遍历，一样也可以求出后序遍历（你要是不信你可以用你的方法验证一下）。

如果看不懂上面在说什么就从这里开始学吧，前序遍历、中序遍历和后序遍历是二叉树遍历的三种方式，它们分别按照不同的顺序访问二叉树的节点。下面分别介绍这三种遍历方式：

1.前序遍历（Pre-order Traversal）

前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。具体步骤如下：

• 访问根节点；
• 前序遍历左子树；
• 前序遍历右子树。

例如，对于以下二叉树：

    A/ \B   C/ \   \
D   E   F

前序遍历的结果为：A -> B -> D -> E -> C -> F

2.中序遍历（In-order Traversal）

中序遍历的顺序是：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。具体步骤如下：

• 中序遍历左子树；
• 访问根节点；
• 中序遍历右子树。

以上述二叉树为例，中序遍历的结果为：D -> B -> E -> A -> C -> F

3.后序遍历（Post-order Traversal）

后序遍历的顺序是：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。具体步骤如下：

• 后序遍历左子树；
• 后序遍历右子树；
• 访问根节点。

以上述二叉树为例，后序遍历的结果为：D -> E -> B -> F -> C -> A

这三种遍历方式在二叉树的操作中非常常见，它们可以用于查找、插入、删除等操作。不同的遍历方式适用于不同的场景，例如，前序遍历常用于复制二叉树，中序遍历常用于二叉搜索树的中序遍历结果为有序序列，后序遍历常用于删除二叉树。

总结

mg-dgP72RJ5-1726151377708)]

如果看不懂上面在说什么就从这里开始学吧，前序遍历、中序遍历和后序遍历是二叉树遍历的三种方式，它们分别按照不同的顺序访问二叉树的节点。下面分别介绍这三种遍历方式：

1.前序遍历（Pre-order Traversal）

前序遍历的顺序是：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。具体步骤如下：

• 访问根节点；
• 前序遍历左子树；
• 前序遍历右子树。

例如，对于以下二叉树：

    A/ \B   C/ \   \
D   E   F

前序遍历的结果为：A -> B -> D -> E -> C -> F

2.中序遍历（In-order Traversal）

中序遍历的顺序是：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。具体步骤如下：

• 中序遍历左子树；
• 访问根节点；
• 中序遍历右子树。

以上述二叉树为例，中序遍历的结果为：D -> B -> E -> A -> C -> F

3.后序遍历（Post-order Traversal）

后序遍历的顺序是：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。具体步骤如下：

• 后序遍历左子树；
• 后序遍历右子树；
• 访问根节点。

以上述二叉树为例，后序遍历的结果为：D -> E -> B -> F -> C -> A

这三种遍历方式在二叉树的操作中非常常见，它们可以用于查找、插入、删除等操作。不同的遍历方式适用于不同的场景，例如，前序遍历常用于复制二叉树，中序遍历常用于二叉搜索树的中序遍历结果为有序序列，后序遍历常用于删除二叉树。

总结

这三种遍历方式在二叉树的操作中非常常见，它们可以用于查找、插入、删除等操作。不同的遍历方式适用于不同的场景，例如，前序遍历常用于复制二叉树，中序遍历常用于二叉搜索树的中序遍历结果为有序序列，后序遍历常用于删除二叉树。三种遍历方式的相互转换，学会画图推断。