• 计算机可以执行每一种操作称为一条指令，计算机可以执行的所有指令集都是计算机的指令系统。
• 指令格式：操作码 操作地址码

• 二进制指令序列成为计算机机器语言，它也是计算机能够直接识别和执行的唯一语言。
  • 优点：直接执行，速度快，资源占用少
  • 确定：可读性、可移植性差、编程复杂

• 用助记符取代机器语言的二进制指令
• 例如用“LOAD用000代替000STORT代替0001等
• 汇编语言比机器语言有了很大的进步，但仍存在以下缺点：
  • 严重依赖目标机器；
  • 不易开发、调试；
  • 与自然语言表达习惯相去甚远

• 高级语言已经从特定的机器中抽象出来，要求依赖特定的机器。
• 虽然高级语言更符合人类的思维习惯，但高级语言程序也必须**翻译(编译)**成最终能够直接执行的机器语言程序。而且，难度比汇编过程大很多。

• 是指不应该改变语义的某种语言的源程序**(逻辑等价)**在另一种语言程序-目标语言程序的条件下
• 编译：特别是指由高级语言程序一次性转换为低级语言程序，类似于全文翻译
• 解释：接收高级语言的句子输入，解释和控制计算机执行。在获得该句子的执行结果后，等待下一个句子的解释和执行，并在执行过程中产生目标程序。类似于口译

• 执行高级语言程序通常分为两个阶段：编译阶段和运行阶段。

  [外链图片存储失败，源站可能有防盗链机制，建议保存图片直接上传(img-GEguvg4D-1641311458565)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101123458498.png)]

高级语言程序的执行阶段分为三个阶段的情况：编译阶段、汇编阶段 和运行阶段。

• 输入：源程序， 输出：目标程序
• 五个阶段：词法分析、语法分析、语义分析和中间代码生成

1.词法分析任务：遵循语言构词规则，将源程序中的字符串转换为单词符号流（通常使用上下文无关的文法）。

2.语法分析任务：根据语法规则，从单词符号串中识别各种语法单位（如表达式、描述、程序段等），并检查语法结构的正确性(可生成语法树)。

3.语义分析和中间代码生成的任务:(将语法单位翻译成中间代码，遵循语言语义规则)

• 对各语法单位进行静态语义审查(语法结构严重合法的程序是否真的有意义)
• 在语义检查正确时翻译中间代码
• 中间代码它介于高级语言语句和低级语言指令之间独立于特定硬件的记号系统，它既抽象又接近低级语言指令，因此更容易转换为目标代码。
• 常用的中间代码表示形式：四元、三元、间接三元、逆波兰等

4.优化中间代码的任务:

• 前一阶段生成的中间代码等价为了获得更有趣的目标代码，变换或转换。
• 优化遵循等价变换规则

5.生成目标代码的任务:

• 将中间代码转换成特定机器上的机器语言代码或汇编语言代码，实现最终的翻译工作。
• 这一阶段的工作依赖于硬件和指令系统

[外链图片存储失败，源站可能有防盗链机制，建议保存图片直接上传(img-9RIoUOYQ-1641311458567)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101131737081.png)]

• 自贬意
• 交叉编译
• 自展
• 移植

状态转换图的概念

正规表达式概念和操作

[外链图片存储失败，源站可能有防盗链机制，建议保存图片直接上传(img-vDhxe2yO-1641311458568)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101195046736.png)]

第一种词法分析器与语法分析器完全分离

• 词法分析器的输出作为语法分析器的输入；将词法分析工作作为独立的一边来完成，在这个过程中不断查询和完善符号表。

[外链图片存储失败，源站可能有防盗链机制，建议保存图片直接上传(img-m1pQZV7r-1641311458569)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101141715430.png)]

二是词法分析器作为语法分析器调用的子程序

• 当语法分析器需要一个单词时，请调用词法分析器
• 交替进行词法分析和语法分析

[外链图片存储失败，源站可能有防盗链机制，建议保存图片直接上传(img-6S2Ygyfx-1641311458569)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101141722759.png)]

• 分类：保留字、标识符、常数、操作符、边界符

• 输出形式： 单词种类，单词本身的价值

在词法分析中，状态转换图可以用来识别单词。状态转换图是状态有限的向图，结点代表状态，圆圈表示；结点可以通过向边连接，代表状态转换关系，可以在边缘标记字符，表示接受某个字符后的状态转移。

字母表：语言元素的非空有穷集合，通常使用$\sum$来表示

符号：字母表重的每一个元素，也称为字符

符号串：由符号组成的有穷序列，也叫字

空字：长度为0的字，用$ϵ$表示

字的全体：所有字组成的集合$\sum$*

空语言：不含有任何字的语言{} ，用 $\Phi $来表示

注意区分空字、空语言和空集$\epsilon KaTeX parse error: Expected '}', got 'EOF' at end of input: 、{}和{ \epsilon$}：

$ϵ$是空字，是语言字的集合中的一个元素，不是$\sum$的元素

{ }不包含任何字，属于集合的概念=$\Phi $

{ $ϵ$ }由空子组成的集合，这个集合比{}多一个元素

所谓形式化的方法，是指用一整套带有严格规定的符号体系来描述问题的方法，优点：更加清晰和准确；能够表示的单词集合称为正规集

三条规则：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7JBodmQg-1641311458570)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101153822128.png)]

1.（基础规则）从普通的符号产生对应的正规式和正规集

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ToCuDpmg-1641311458571)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101153918743.png)]

2.（归纳规则）根据已有的正规式和正规集生成其他正规式和正规集

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0jq9cZT6-1641311458572)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101153932078.png)]

3.（终止规则）根据已有的正规式和正规集生成其他正规式和正规集

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-w5r6sL5O-1641311458573)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101154210127.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gnQ0V32t-1641311458575)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101154427902.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2j3YQd3T-1641311458576)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101154450575.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2JcS2Bt2-1641311458577)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101155628871.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rIMxg4DI-1641311458578)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101155641561.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eGpKwGpo-1641311458579)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101155650792.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-J4isLDV5-1641311458580)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101160323062.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ti5UDmjz-1641311458581)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101193308615.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gEYld7nr-1641311458582)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101195058585.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EswAux2T-1641311458583)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101204305574.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HbJ1KgNl-1641311458584)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102181234648.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WCaZutn1-1641311458585)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101212055814.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uw33kmsv-1641311458585)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101212038203.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-FSxTgssa-1641311458586)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101214251342.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bk6kPGwx-1641311458587)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101234522817.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tS2T7ayu-1641311458587)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220101234732868.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t2gzVON5-1641311458588)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102000838568.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uHo5g49U-1641311458589)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102113200101.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2XK7SVoL-1641311458589)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102170223655.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aJ7lxN48-1641311458590)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102115428628.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H6m9S2Bf-1641311458590)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102115723947.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GWs2abQK-1641311458591)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102115732541.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-flsY7mDN-1641311458592)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102120818963.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4WkBGJQs-1641311458593)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102121350702.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-d7KJXKNL-1641311458594)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102163322427.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dgPOBEWu-1641311458595)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102163334784.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6ygknQTe-1641311458595)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102163348271.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TIrTbBT2-1641311458596)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102164828440.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-q7hgvzMJ-1641311458597)(C:\Users\86187\AppData\Roaming\Typora\typora-user-images\image-20220102164745499.png)]