文法和语言

编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。 编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。

文法和语言

• 字母表
  • 定义
    • 元素的非空有穷集合
• 符号串
  • 运算
    • 连接
      • 注意顺序，AB≠BA
    • 乘积
  • 定义
  • 长度
  • 空串
• 集合
  • 运算
    • 乘积
    • 幂
    • 闭包
      • 正闭包
      • 广义闭包
• 形式语言
  • 定义
    • 是用严格规定的符号体系描述的一个字母表上的所有串的集合
  • 描述
    • 有穷集合
      • 列举法
    • 无穷集合
      • 文法
• 语言的形式定义
  • 直接推导
    • 一次规则式
  • 正推导
    • 一次或多次规则是
  • 广义推导
    • 0次或多次
  • 句型、句子
    • 句子一定是句型
    • 仅有非终结符组成的句型叫句子
  • 语言L(G[S])
    • 文法描述的语言是该文法一切句子的集合
    • 若文法给定，语言就确定了，反之不对
• 形式化方法
  • 指用一整套带有严格规定的符号体系来描述问题的方法
• 语言
  • 在某特定字母表上定义且按一定规则构成的符号串的集合（有穷或无穷）
• 规约
  • 最左规约
    • 规范规约
    • 是最右推导的逆过程
    • 先规约最左边的那个字符串
  • 最右规约
• 推导
  • 最左推导
    • 每次对最左边的非终结符进行替换
  • 最右推导
    • 规范推导
• 递归
  • 作用
    • 定义无穷集合的语言
  • 类别
    • 规则递归
      • 左递归
      • 右递归
      • 规则递归
    • 文法递归
      • 左递归
      • 右递归
      • 规则递归
• 句型分析
  • 定义
    • 形式上
      • 识别一个符号串是否是文法G的句型
    • 实质上
      • 确定输入符号串是否是语法上正确的程序
  • how
    • 语法树
      • 句型
        • 根节点的所有叶子从左到右
      • 短语
        • 每棵子树的叶子从左到右
      • 直接短语
        • 每棵简单子树（高度≤2）的叶子从左到右
      • 句柄
        • 最左边简单子树的叶子从左到右构成一句柄
  • 二义性
    • 有些文法是先天二义，不可更改
    • 对于二义文法来说，一个句型不一定只对应一棵唯一的语法树
  • 如何消除
    • 不改变规则式，仅加进非形式化的语法规定
    • 增加层次就可以改变优先级
• 文法
  • 定义
    • 定义或描述语言的语法结构的一组规则及其符号
    • G=（Vn, Vt, S ,P）
  • 文法的等价性
    • 不扩大范围
    • 不减小范围
  • 类别
    • 0类
    • 1类
      • 上下文有关文法
    • 2类
      • 上下文无关文法
    • 3类
      • 左线性文法
        • 要么不含非终结符，要么只含1个非终结符且在产生式最左侧
      • 右线性文法
        • 要么不含非终结符，要么只含1个非终结符且在产生式最右侧
        • 正规文法
          • 规则式的右部只含有单个终结符
  • 化简
    • 1.去掉A->A
    • 2.去掉无用的非终结符
      • 算法
    • 3.去掉终点不可达
      • 算法
    • 4.去掉不含多余规则表达式