语言程序处理

这是一篇关于语言程序处理的思维导图，主要内容包括：正则表达式，表达式，有限自动机，文法，编译过程概述。

语言程序处理

• 1. 编译过程概述
  • 词法分析
    • 定义
      • 从左到右逐个扫描源程序中的字符，识别其中如关键字、标识符、常数、运算符以及分割符等
    • 输入输出
      • 输入
        • 源程序
      • 输出
        • 记号流
    • 判断方法
      • 文法
      • 正则表达式
      • 有限自动机
  • 语法分析
    • 定义
      • 根据语法规则将单词符号分解成各类语法单位，并分析源程序是否存在语法上的错误
      • 主要分析程序语句的结构是否合法
        • 语句结构
          • 括号不配对
          • 判断程序语句的形式
          • 缺少分号
        • 表达式
          • 表达式缺少操作数
    • 输入输出
      • 输入
        • 记号流
      • 输出
        • 语法树
    • 分析方法
      • 自下而上
        • 递归下降
        • 预测分析
        • 回溯法
      • 自下而上
        • 移进归约
  • 语义分析
    • 定义
      • 进行类型分析和检查，主要检测源程序是否存在静态语义错误
        • 语法结构
          • 取余时用浮点数
          • 运算符和运算类型不匹配
    • 静态语义分析
      • 编译时发现的错误
        • 语法指导翻译
          • 翻译的任务是语义分析和正确性检查
  • 中间代码生成
    • 定义
      • 根据语义分析输出生成中间代码
    • 常用中间代码
      • 语法树
      • 后缀式
      • 三地址码
      • 四元式
      • 口诀：雨后34人采蘑菇
    • 动态语义分析
      • 发生在程序运行时
        • 死循环
        • 变量取零做除数
          • 运行时产生异常
        • 元素下标越界
    • 不依赖于具体的机器
    • 提高编译程序的可移植性
  • 代码优化
  • 不是必需的步骤
  • 目标代码生成
    • 分配寄存器
  • 符号表
    • 记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成
    • 在编译过程中需要对符号表进行快速有效地查找、插入、修改和删除等操作
• 2. 文法
  • 程序设计语言大多数语法现象可以用上下文无关文法描述。
• 3. 正则表达式
  • 常用规则
    • *
      • 0到n
        • 0,1,2,3......n
    • |
      • 表示逻辑“或”，用于匹配两个或多个选项中的一个。
    • ab
      • 字符串ab构成的集合
        • {ab}
    • a|b
      • 字符串a、b构成的集合
        • {a,b}
    • a*
      • 由0或n个a构成的集合
        • {空，a,aa,aaa,.....}
    • （a|b）*
      • 所有字符a和b构成的串的集合
        • {空，a,b,ab,aab,abb,baa,aba......}
          • a和b的顺序不确定谁在前
    • a（a |b）*
      • 以a为首字符
        • {a.aa.ab.aab.aba.aaab,......}
    • （a |b）*abb
      • 以abb结尾
        • {abb,aabb,babb,abaabb......}
  • 例
    • ab*a
      • 字符串以'a'开头，以'a'结尾，中间可以有任意数量的'b'
• 4. 有限自动机
  • 确定性有限自动机（DFA）
    • 即每个状态对每个输入只有一个确定的转移路径
  • 非确定性有限自动机（NFA）
    • 一个状态对同一个输入可以有多个可能的转移路径
• 5. 表达式
  • 前缀表达式
    • +ab
  • 中缀表达式
    • a+b
  • 后缀表达式
    • ab+
      • 利用栈进行分析
• 3.3