程序设计语言基础知识

2.1 程序设计语言概述

2.1.1 程序设计语言的基本概念

• 低级语言：机器语言 (由0、1序列构成）、汇编语言 (Add、Sum）
• 高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近
  • C (指针操作能力强，且高效）
  • C++ (面向对象，且高效）
  • C# (面向对象，中间代码，.NET）
  • Java (面向对象，中间代码，跨平台）
  • Python (面向对象，脚本语言，解释型语言）
  • JavaScript (脚本语言，广泛用于Web开发）

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

• 数据成分：指一种程序设计语言的数据和数据类型
  • 数据：常量、变量、全局量、局部量
  • 数据类型：整型、字符型、单精度浮点型、双精度浮点型、布尔型、枚举类型
• 运算成分：指明允许使用的运算符及运算规则。包括算术运算、逻辑运算、关系运算、位运算等
• 控制成分
  • 顺序结构
  • 选择结构 (if）
  • 循环结构 (for、while）
• 传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等
• 函数：是一段具有处理独立功能的代码块，包括 函数定义、函数声明 (先声明再使用）、函数调用
  • 函数定义：返回值类型 函数名(形参..){函数体;} (void test() {printf(“Hello,World!”);}）
  • 函数声明：返回值类型 函数名(参数类型..) (void test();）
  • 函数调用：函数名(实参…) (test();）
    • 传值调用：将实参的值传递给形参，形参的改变不会导致实参的改变。实参可以是合法的变量、常量或表达式
    • 引用调用：即传地址调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此形参的值改变的同时，实参的值也跟着改变。实参不能为常量，只能是合法的变量和表达式

2.2 语言处理程序基础

2.2.1 汇编程序基本原理

汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。
汇编程序将汇编语言所编写的源程序翻译成机器指令程序。
汇编程序一般需要两次扫描源程序才能完成翻译过程。

• 第一次扫描：检查语法错误，确定符号名字；建立符号表；
• 第二次扫描：产生目标程序

2.2.2 编译程序基本原理

编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序 (汇编语言或机器语言）

• 词法分析：
  • 将源代码的字符流转换为有意义的词法单元记号（Token），输出的是记号流
  • 例如：将类似 int a = 5 + b; 的代码分解为 int、a、=、5、+、b、; 等 Token
• 语法分析：
  • 将 Token 序列转换为抽象语法树、检查代码结构是否符合编程语言的语法规则。
  • 例如：验证表达式的括号是否匹配、语句结构是否正确等
  • 语法分析方法
    • 自上而下
      • 自上而下语法分析法：最左推导，从左至右。给定文法G和源程序串r，从G的开始符号S出发，通过反复使用产生式P对句型中的非终结符进行替换(推导)，逐步推导出r
      • 递归下降分析法：原理是利用函数之间的递归调用，模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法
    • 自下而上
      • 自下而上语法分析法：最右推导，从右至左。从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号S
      • 移进-归约分析法：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式P的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部推导出左部，因此是自下而上语法分析的核心思想。
• 语义分析：
  • 检查代码的语义是否合理，确保程序的逻辑正确性。包括类型检查 (如整数不能与字符串相加）、变量作用域检查 (如使用未定义的变量）
  • 分为静态语义错误 (在编译阶段能够查找出来）和动态语义错误 (只能在运行时发现）
• 中间代码生成：(非必须）
  • 将 AST 转换为与机器无关的中间表示形式 (如后缀式(逆波兰式)、三元式 (三地址码)、四元式、树和图等），引入中间代码的目的是进行与机器无关的代码优化处理，有助于提高可移植性
  • 示例：表达式 a + b * c 可能转换为 t1 = b * c; t2 = a + t1。
• 代码优化：(非必须）
  • 对中间代码进行改进，在不改变功能的前提下提升效率（如减少运算次数、优化内存使用）
• 目标代码生成：
  • 将优化后的中间代码转换为目标机器的机器语言或汇编代码
• 
• 符号表
  • 作用是记录源程序中各个符号 (如变量、函数、类、常量等）的必要信息，在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作，在编译过程中辅助编译器完成各种分析和处理工作
• 后缀式 (逆波兰式）
  • 后缀式是中间代码的一种表现形式
  • 这种表示方式把运算符写在运算对象的后面
  • 例如 a*(b+c/d)-e 的后缀式为 abcd/+*e-
  • abcd/+*e- 推出 a*(b+c/d)-e时，先扫描ab，ab后面没有运算符，再扫描bc，bc后面也没有运算符，再扫描cd，cd后面运算符为/，则就是c/d，然后将c/d看出一个整体，原来式子就成了abc/d+*e-，重新开始从ab扫描，后面没有运算符，bc/d后面的运算符是+，则就是b+c/d，再将b+c/d看成一个整体，原来式子就成了ab+c/d*e-，后面以此类推。
• 文法
  • 文法：
    • 文法是词法分析和语法分析的 “理论基础”，但两者使用的文法类型不同
    • 文法的形式化定义为四元组 G = (Vₙ, Vₜ, P, S)
      • Vₙ：非终结符集合 (能够推导出其他元素，如 “句子”“名词短语”）
      • Vₜ：终结符集合 (不能推导出其他元素，即语言的基本字符，如字母、数字）
      • P：产生式规则集合 (即非终结符推导出终结符的公式，如 “句子 → 名词短语 + 动词短语”）
      • S：起始符号 (推导的起点，如 “句子”）
    • 文法的分类
      • 
  • 正规表达式，简称 正规式
    • 正规式是用特定符号（如 |、*、+、()）组合起来的字符串，直接描述正规语言的 “形态”。它更直观，像数学公式一样简洁地表示语言范围。
    • 基础符号：∅（空集）、ε（空串）、a（单个终结符）
    • 组合规则
      • A|B（选择）：A 和 B 的并集，如 a|b 表示 {a} 或 {b} ，也可以表示为{a,b}；
      • AB（连接）：A 的每个字符串后接 B 的每个字符串，如 ab 表示 {ab}
      • A*（闭包）：A 的字符串重复 0 次或多次，如 a* 表示 {ε、a、aa、aaa…}
      • A+（正闭包）：A 的字符串重复 1 次或多次，如 a+ 表示 {a、aa、aaa…}
      • (a|b)* 表示 {ε,a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb,...}
      • a* 为正规式，{a、aa、aaa…} 为 正规集
  • 有限自动机
    • 有限自动机是一种抽象的计算模型，模拟 “读取字符串、判断是否属于某语言” 的过程
    • 有限自动机分类
      • 确定有限自动机 (DFA）：每个状态对每个输入字符，只有唯一一条转移路径 (无歧义）；
      • 非确定有限自动机 (NFA）：每个状态对每个输入字符，可能有多条转移路径或 ε 转移 (有歧义）。
  • 3型文法 (正规文法）、正规表达式 (正规式）、有限自动机 (DFA/NFA），它们本质是描述或识别 “正规语言” 的不同工具，且能力完全等价，可以相互转换。
    • 

2.2.3 解释程序基本原理

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