程序语言处理基础

区别 编译 解释
区别代码 生成，并优化 不生成
独立的可执行文件 生成 不生成，逐行边翻译边执行
执行效率 较快 较慢（反复扫描源程序）
占用内存 较少 较多
灵活性 较低 较高（反复扫描源程序）
可移植性 较差 较高 
Python:
    x = [ 1 , 2 ] = list列表
    tuple(元组)是一种不可变、有序的序列结构
    dict(字典)、list(列表)、set(集合) 可变的

程序设计语言分类

  1. 低级语言：机器语言（只能识别0和1的指令序列），汇编语言
  2. 高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近

常见的编程语言

  1. SQL语言（数据库结构化语言）
  2. Pascal(为教学而开发的，表达能力更强)
  3. C语言（指针操作能力强，高效）
  4. Python（脚本语言，胶水语言）
  5. C++（面向对象，高效）
  6. Java（面向对象，中间代码，跨平台）
  7. C#语言（面向对象，中间代码，.net）
  8. JavaScript(脚本语言，网页动态效果，嵌入在html中)

编译和解释：都是将高级语言翻译成计算机硬件认可的机器语言加以执行
程序语言设计组成：

  1. 语法（一组规则）
  2. 语义（语法成分的含义）
  3. 语用（构成语言的各个记号和使用者的关系）

在编译方式下，必须先形成源程序的中间代码，然后再产生与机器对应的目标代码

程序设计语言的基本成分

  1. 数据成分：指数据类型，数据分类常量、全局量、局部量
  2. 运算成分：指运算符号及运算规则，包括算数、逻辑、关系、位运算
  3. 控制成分：指顺序，选择，循环结构
  4. 传输成分：如赋值处理数据的输入输出

函数使用涉及三个概念：函数定义、函数声明、函数调用

传值调用：将实参的值传给形参，形参的改变不会导致调用点所传的实参的值改变。实参可以是合法的变量，常量和表达式

传址调用即引用调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此其值改变的同时就改变了实参的值。
实参不能为常量，只能是合法的变量和表达式，因此在编程时，要改变参数值就传址，不改变，就传值

在传地址方式下，将实参的地址传给形参，因此，实参必须有地址

编译程序的基本原理

编译程序的功能就是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言）
编译程序工作分为6个阶段：

源程序
词法分析
符 语法分析 上下文无关 出
号 语义分析 上下文有关 错
表 中间代码生成 机器无关 管
管 代码优化 非必须 理
理 目标代码生成
目标代码
  1. 词法分析 是编译的第一个阶段，从左到右一个字符一次地读入源程序
  2. 语法分析 是编译过程的一个逻辑阶段，判断源程序在结构上是否正确，比如缺少右边括号，分号忘记写之类的
  3. 语义分析 需要依赖于符号表联系上下文的，在声明，赋值、引用、控制、循环条件时需要进行翻译。
    比如 遍历未声明就使用，重复使用，函数调用参数不对之类的。
  4. 中间代码和目标代码生成
    中间代码是语义分析产生的，需要进行优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与代码无关的优化处理
    常见的中间代码有后缀式（逆波兰式）、三元式（三地址式）、四元式和数，图等形式

目标代码生成的三个因素

  1. 如何生成较短的目标代码
  2. 如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数
  3. 如何充分利用计算机指令系统的特点，以提高目标代码的质量

中间代码不能用栈（FILO）和队列（FIFO）表示
中间代码不依赖于具体机器，可以提高编译程序的可移植性

编译程序的基本原理

  1. 前缀表达式（+ab）
  2. 中缀表达式（a+b）
  3. 后缀表达式（ab+）
flowchart TB
    '+' --> A
    '+' --> B

主要掌握上述三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历，即中缀表达式，根据其构造出树，再按照题目要求求出前缀或后缀。
简单求法：后缀表达式是从左到右开始的，先把表达式加上括号，再依次把运算符加到本层次的括号后面

例：a + (b - c) * d 的后缀表达式是？
= ( (a) + ((b - c) * d))
= ((a) + (bc- * d))
= (a + bc-dx)
= abc-dx+

文法定义

计算机文法是指用于描述计算机语言的一种形式语法。
计算机语言可以分为自然语言和形式语言两种类型，而形式语言又可以分为：
上下文无关文法
上下文有关文法，两种类型。

一个形式文法是一个有序的四元组G=（ V , T , S , P）其中：

  1. V：非终结符，不是语言组成部分，不是最终结果可以理解为占位符
  2. T：终结符，是语言的组成部分，是最终结果
  3. S：起始符，是语言的开始符号
  4. P：产生式，用终结符代替非终结符的规则。

总结符:最终结果，不能推导出其他元素
非终结符：能够推导出其他元素
产生式：即非终结符推导出终结符的公式/

闭包

一般考察闭包可以为0个的情况带入运算：
正则闭包：A^x = A^1 U A^2 U A^3 .... A^n (也就是所有幂的组合)
闭包：A^x = A^0 U A^x (在正则闭包的基础上加上A^0={ϵ})

例如：a^x = {a,aa,aaa,….,ϵ}
而(ab)^x = {ab,abab,ababab,…..ϵ}

文法定义

已知文法 G：S-> A0 | B1 , A -> S1 | 1 , B -> S0 | 0
S = A0 | B1 = (S1 | 1)0 | (S0 | 0) 1
S = S10 | 10 | S01 | 01

对于大多数通用程序设计语言用上下文无关文法描述语法即可

有限自动机

是一种计算模型，它可以接收一些输入，然后根据预定的规则转移到不同的状态。
有限自动机可以分为
确定性有限自动机 DFA
非确定性有限自动机 NFA
有限自动机和不确定的有限自动机：输入一个字符，看是否能得出为唯一后继，若能，则是确定的，否则若得出多个后继，则是不确定的。


已知，A是初态，C是终态，该自动机所识别的字符串的特点是：
必须以01结尾的0，1串


为一个不确定的有限自动机NFA的状态转换图，该NFA可识别的字符串是
01100