编译原理-第二章 一个简单的语法指导编译器-2.3 语法定义

语法定义：

• 文法定义：
  • 定义：用以描述程序设计语言语法的表示方法——“上下文无关文法”，简称“文法”，文法自然地描述了大多数程序设计语言构造地层次化语法结构
  • 实例：
    • 如果用变量expr来表示表达式，用变量stmt表示语句，则
    • 

       

  • 相关概念：
    • • 产生式：使用箭头(→)表示"可以具有如下形式"，用相关变量表示表达式和语句的构造规则产生的式子。每个生产式包括一个称为生产式头或左部的非终结符号，一个箭头，和一个称为生产式体或右部的由终结符号组成的序列。
      • 终结符号：有时也称为词法单元，终结符号是该文法所定义的语言的基本符号的集合
        • 字母表中的小写字母，如 a，b，c
        • 黑体串，关键字，如 id,  while
        • 数字 0, 1, … , 9
        • 标点符号，如括号，逗号等
        • 运算符号，如+, -等
      • 空串：零个终结符号组成的串，记为ε
    • • 非终结符号：有时也称为语法变量，每个非终结符号表示一个终结符号串的集合
        • 表示终结符号的序列的变量，如expr和stmt这样的变量
      • • 字母表中的大写字母，如 A, B, C
      • • 字母 S，并且通常代表开始符号
      • • 小写字母的名字(斜体)，如expr, stmt
  • 组成：
    • 终结符号集合
    • 非终结符号集合
    • 产生式集合
    • 开始符号∈非终结符号集合
  • 书写规定：
    •  字母表中后面的大写字母，如X, Y, Z, 可以是终结符或非终结符
  • • 字母表中后面的小写字母，如u, v,… z, 可代表终结符号串
    • 小写希腊字母，如a，b，可代表文法的符号串
    • 对于A →a₁，A→ a₂，… A →a_n可以写成Aa₁|a₂|…|a_n
    • 除非特别说明，第一个产生式的头就是开始符号
• 推导：
  • 定义：根据文法，首先从开始符号出发，不断将某个非终结符号替换为该非终结符号的某个产生式的体；把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替
  • 文法定义的语言：从开始符号推导得到的所有终结符号串的集合
  • 实例：
    • 

    •  max(x，y)：

      • 文法：optparams(可选参数列表)

    •  
• 语法分析：
  • 任务：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法，如果不能找出，则报告语法错误
  • 语法分析树
    • 作用：用图形方式展现了从文法的开始符号推导出相应语言中的符号串的过程
    • 性质：
      • 根结点是开始符号
        
      • 叶子结点是终结符或ε
      • 内部结点是一个非终结符
      • 若A→x1x2....xn，则A是一个非终结符，x₁x₂...x_n 是终结符或非终结符
    • 结果：一颗语法树的叶子节点从左向右构成了树的结果
    • 实例： 
  • 为一个给定的终结符号串构建一棵语法树的过程称为对该符号串进行语法分析
• 二义性：
  •  
• 运算符的结合性：
• 运算符的优先级：