编译原理笔记（2）

第二章

1. 程序语言的定义

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

2. 语言的分类：

   • 第一代语言（机器语言）
   • 第二代语言（汇编语言）
   • 第三代语言（高级语言）
     • 命令式（c++）
     • 功能式（Haskell）
     • 说明式（Prolog）
   • 第四代语言（基于应用的语言）

3. 文法的语言：

   • 文法所能表示所有句子的集合就是该文法产生的语言。

4. 程序语言的语法描述

   • 词法：使用有限自动机、正规式描述。
   • 语法：使用巴斯范式（文法）描述。

5. Σ

   • 一个有穷字母表，它的每一个元素成为一个符号。
   • 符号串：Σ上部分符号组成的串。

6. ε

   • 不包含任何字符的串，空串。

7. Ø

   • 不含任何元素的集合，注意这是一个集合，他和ε不同，后者是一个串。

8. 闭包与正则闭包

   • 闭包

   Σ^*

   • 正则闭包

   Σ^+

   • 二者不同在于，正则闭包不包含ε

9. 文法

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

10. 终结符与非终结符

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

11. 上下文无关文法与上下文有关文法

    • 用于设计程序语言的是上下文无关文法，而自然语言是上下文有关文法。
    • 这个有关和无关指的是一个符号的推导，是否需要考虑上下文的情况，例如：

    S->ABC
    A-> 人 | 天
    B-> 吃 | 下
    C-> 饭 | 雨

    • 有关文法是不能推导出人下雨这样的句子的，因为吃|下这个选择需要考虑前面或后面出现的字符。
    • 而无关文法则可以推导出，因为不必考虑上下文的语境。

12. 上下文无关文法

    • 形式化定义：上下文无关文法是一个四元组：

    (V_T , V_N , S ,Ｐ) 
    
    V_T 非空有限集，每个元素为终结符
    
    V_N 非空有限集，每个元素为非终结符
    
    S 起始符号，S \in V_N
    
    P 产生式集合，格式为 S \rightarrow a
    
    S \in V_N , a \in (V_N \cup V_T)^* 
    
    开始符号必须在某个产生式左侧出现一次
    
    若 P \rightarrow a_1 | a_2 | a_3,则a_i称为P的候选式

13. 产生式的简化式

    • 若一个非终结符有多个产生式，这可以将这些产生式的右侧用|连接在一个产生式的右侧，这样就称为化简式。

14. 上下文无关文法的推导

    

15. 句子和句型

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

16. 文法的语言

    • 一个文法G所产生的句子的全体，称为文法的语言，记为L(G)

17. 文法等价

    • 如果两个不同的文法，所产生的语言相同，那么两个文法等价。

18. 最左推导和最右推导

    • 最右推导：任何一步都是对最右非终结符进行替换
    • 最左推导：任何一步对最左非终结符进行替换。

19. 语法分析树

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

20. 语法分析树的二义性

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

21. 文法分类

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

    

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

    S \rightarrow \epsilon 除外，但S不能再出现在任何产生式右侧

    • 2型文法：产生式的左侧有且仅有一个非终结符。又叫上下文无关文法。
    • 3型文法：称为正规文法或线性文法，要求最严格，只可以存在以下形式中的一种。
      • 右线性文法

      S \rightarrow \alpha B
      
      S \rightarrow  \alpha

      • 左线性文法

      S \rightarrow  A \beta
      
         S \rightarrow  \beta