文章 47
评论 4
浏览 11472
编译原理笔记(2)

编译原理笔记(2)

第二章

  1. 程序语言的定义

    • 语言的定义是语言实现的基础。
    • 程序语言由两方面定义:语法规则和语义规则。
    • 语法:一组规则,用它可以产生一个合式(well-formed)的程序。
    • 语义:语言成分的含义,由程序的执行效果来说明。
  2. 语言的分类:

    • 第一代语言(机器语言)
    • 第二代语言(汇编语言)
    • 第三代语言(高级语言)
      • 命令式(c++)
      • 功能式(Haskell)
      • 说明式(Prolog)
    • 第四代语言(基于应用的语言)
  3. 文法的语言:

    • 文法所能表示所有句子的集合就是该文法产生的语言。
  4. 程序语言的语法描述

    • 词法:使用有限自动机、正规式描述。
    • 语法:使用巴斯范式(文法)描述。
  5. Σ

    • 一个有穷字母表,它的每一个元素称为一个符号。
    • 符号串:Σ上部分符号组成的串。
  6. ε

    • 不包含任何字符的串,空串。
  7. Ø

    • 不含任何元素的集合,注意这是一个集合,他和ε不同,后者是一个串。
  8. 闭包与正则闭包

    • 闭包
      $ Σ^*$
    • 正规闭包
      $ Σ^+$
    • 二者不同在于,正则闭包不包含ε
  9. 文法

    • 描述语言的形式规则,用于组织编译程序的前端
    • 这些规则需要是准确的、易于理解的,有相当强的描述能力足以描述不同的结构。
  10. 终结符与非终结符

    • 终结符:不能再推导为其他符号的符号,常用符号或者小写字母表示。在程序语言中是基本字、关键字、标识符、常数、运算符、界符。
    • 非终结符:可以继续推导为其他符号的符号,常用大写字母表示。在程序语言中是语句、表达式。
  11. 上下文无关文法与上下文有关文法

    • 用于设计程序语言的是上下文无关文法,而自然语言是上下文有关文法。
    • 这个有关和无关指的是一个符号的推导,是否需要考虑上下文的情况,例如:
    S->ABC
    A-> 人 | 天
    B-> 吃 | 下
    C-> 饭 | 雨
    
    • 有关文法是不能推导出人下雨这样的句子的,因为吃|下这个选择需要考虑前面或后面出现的字符。
    • 而无关文法则可以推导出,因为不必考虑上下文的语境。
  12. 上下文无关文法

    • 形式化定义:上下文无关文法是一个四元组:
      image.png
  13. 产生式的简化式

    • 若一个非终结符有多个产生式,这可以将这些产生式的右侧用|连接在一个产生式的右侧,这样就称为化简式。
  14. 上下文无关文法的推导

    image.png

  15. 句子和句型

    • 若一个符号串仅含有终结符,那么这个符号串就称为句子。
    • 反之符号中存在非终结符的符号串那么就是句型,句子是特殊的句型。
  16. 文法的语言

    • 一个文法 G 所产生的句子的全体,称为文法的语言,记为 L(G)
  17. 文法等价

    • 如果两个不同的文法,所产生的语言相同,那么两个文法等价。
  18. 最左推导和最右推导

    • 最右推导:任何一步都是对最右非终结符进行替换
    • 最左推导:任何一步都是对最左非终结符进行替换。
  19. 语法分析树

    • 语法分析树是推导过程的共性抽象。
    • 最左推导和最右推导的语法树一样。
  20. 语法分析树的二义性

    • 如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。
  21. 文法分类

    • 0 型文法:产生式的左侧至少含有一个非终结符。能力相当于图灵机。

    image.png

    • 1 型文法:产生式左侧的长度小于等于右侧的长度。又叫上下文有关文法。
      image.png

    • 2 型文法:产生式的左侧有且仅有一个非终结符。又叫上下文无关文法。

    • 3 型文法:称为正规文法或线性文法,要求最严格,只可以存在以下形式中的一种。

      • 右线性文法
        image.png
      • 左线性文法
        image.png

标题:编译原理笔记(2)
作者:llym
地址:https://www.wendau.com/articles/2020/03/13/1584112530666.html

闻道

取消