编译原理 第二章 高级语言及其语法描述

编译原理 第二章 高级语言及其语法描述

2.1 高级语言简介

2.1.1 高级语言的定义

任何语言程序都可以看成一定字符集(称为字母表)上的一个字符串(有限序列)。只有满足语法要求的字符串才是合式的程序。

语法:一组可以形成和产生合式程序的规则,包括词法规则和语法规则。

语义:一组可以定义程序意义的规则,这些规则称为语义规则。

2.1.2 高级语言的一般特性

高级语言的分类

  • 强制式语言(Imperative Language)
    • 过程(命令)式语言
    • 命令驱动,面向语句
    • 由一系列语句组成
    • Pascal、C
  • 应用式语言(Applicative Language)
    • 函数式语言
    • 由已有的函数构造出更为复杂的函数
    • LISP
  • 基于规则的语言(Rule-based Language)
    • 逻辑程序设计语言
    • 基本执行条件式谓词逻辑表达式
    • Prolog
  • 面向对象语言(Object-oriented Language)
    • 封装性、继承性、多态性
    • 复杂的数据及操作构成对象
    • 简单对象扩充或继承简单对象,设计复杂对象
    • C++

程序结构

  • 以子程序为主的结构
    • 允许子程序嵌套定义
    • Pascal
  • 以类或程序包等为主的结构
    • 使用类把有关数据及其操作封装在一起,构成一个抽象数据类型
    • Java

数据类型

一个数据类型的三种要素:

  • 用于区别这种类型的数据对象的属性;
  • 这种类型的数据对象可以具有的值;
  • 可以作用于这种类型的数据对象的操作。

数据类型可分为初等数据类型、复杂数据类型和抽象数据类型。

常见的初等数据类型:

  • 数值数据。如整数、实数、复数以及这些类型的双长(或多倍长)精度数 等。
  • 逻辑数据。逻辑型或布尔型数据,
  • 字符数据。字符型或字符串型的数据。
  • 指针类型。往往存放指向数据单元的地址。

复杂数据类型通常是在初等数据类型的基础上定义得到的,常见的复杂数据类型:

  • 数组
    • 同一类型的数据所组成的一种句矩形结构(逻辑上)
  • 记录
    • 已知类型的数据组合起来的一种结构
    • 每个分量称为记录的一个域(Field)
    • 每个域都是一个确定的数据,不同域的数据可以不同
  • 表格、栈和队列
    • 表格:一组记录结构

一个抽象数据类型包括:

  • 数据对象的一个集合;
  • 作用于这些数据对象的抽象运算的集合;
  • 这种类型对象的封装,即:除了使用类型中所定义的运算外,用户不能对 这些对象进行其他操作

语句形式

  • 表达式
    • 由运算量和运算符组成
    • 变量和常数是表达式
    • 表达式与元素符的合法构成也是表达式
  • 赋值语句
    • a := b
    • 将 b 的值送入 a 索爱表的存储单元中
  • 控制语句
    • 控制程序的执行顺序
    • 如 if、while、goto、return
  • 说明语句
    • 定义名字的性质,
    • 通常,编译程序把这些性质登记在符号表中
  • 简单句和复合句
    • 简单句:不包含其他成分的基本句
    • 复合句:内含其他语句的语句

2.2 高级语言的语法描述

2.2.1 符号和符号串

  • 字母表(Σ):在一个高级语言程序中,所有能够使用的字符构成的非空有限集。
  • 符号:Σ 中的任意一个元素。
  • 字(Σ 上的一个符号串):由 Σ 中的符号所构成的一个有穷序列。
  • 空字(ε):不包含任何符号的序列。
  • Σ*:Σ 上所有符号串的全体,包括 ε。
  • Φ:不包含任何元素的空集 {}。
  • |s|:符号串 s 的长度,s 中的符号的个数。

设 U、V 是 Σ* 的两个子集,定义 U 与 V 的乘积为:

\(UV = \{\alpha \beta | \alpha \in U \& \beta \in V \}\)

则,集合 V 的 n 次方幂为:\(V^n = VVV...V\),规定 \(V^0=\{ \epsilon \}\)

令 $V^=V^0 V^1 V^2 V^3 ... $,则称 V 是 V 的闭包。记 \(V^+ = VV^*\),是 V 的正则闭包。

2.2.2 上下文无关文法

文法:描述语言的语法结构的形式规则。

上下文无关文法:不考虑各个语法单位所处的上下文。

\(\rightarrow\):定义为。\(\Rightarrow\):推导

一个上下文无关文 法 G 包括四个组成部分:一组终结符号,一组非终结符号,一个开始符号以及一组 产生式。

  • 终结符号
    • 单词符号、保留字、标识符、界符等
    • 不可分割的基本符合
    • 终结符的集合是非空有限集,\(V_T\)
  • 非终结符号
    • 语法概念,是一个类(集合)的记号
    • 算术表达式、赋值语句、分程序等
    • 非终结符的集合是非空有限集,\(V_N\)
    • \(V =V_T \cup V_N, V_T \cap V_N=\emptyset\)
  • 开始符号
    • 特殊的非终结符,S
  • 产生式
    • 即规则
    • 一般形式:A -> α 或 A ::= α
    • \(A\in V_N\),称为产生式的左部
    • 右边的 α 是由终结符号和非终结符号组成的一个符号串,即 \(\alpha \in V^*\),称为产生式的右部
    • 产生式的集合是有限集,P

形式上讲,一个上下文无关文法 G 是一个四元式 \((V_T,V_N,S,P)\)

  • 开始符号 S 至少必须在某个产生式的左部出现一次,且第一条产生式的左 部必须是开始符号。
  • 大写字母 A、B、C 等代表非终结符号,用小写字母 a、b、c 等代表终结符号,希腊字母 α、β、γ 等代表由终结符和非终结符组成的符号串。
  • 有时为了书写方便,若干个左部相同的产生式,如: \(A\rightarrow \alpha_1, A\rightarrow \alpha_2,...,A\rightarrow \alpha_n\),合并为 $A_1 |_2|...|_n $。每个 \(\alpha_i\) 称为 A 的一个候选式。
  • 为方便起见,书写文法时只需列出产 式并指出开始符号即可。文法 G 也可以写成 G[S],以表示 S 是文法 G 的开始符号。

严格来讲,如果 A→γ​ 是一个产生式,\(α、β∈(V^T∪V^N)^*\),则称 \(αAβ⇒αγβ\) 为一步推出或直接推出。如果 \(α_1⇒α_2⇒…⇒α_n\),则称它是从 \(α_1\)\(α_n\)的一个推导。如 果存在从 \(α_1\)\(α_n\)的一个推导,则称 \(α_1\)可推导出 \(α_n\)

给定文法 G,S 是 G 的开始符号。如果 \(S\overset{*}{\Rightarrow}α\),则称 α 是一个句型

若 α 是文法 G 的一个句型,且 α 中仅含终结符号,即 \(α∈V_T^*\),则称 α 是文法 G 的一个 句子

从文法 G 的开始符号 S 出发,所能推导出的句子的全体称为文法 G 产生的语言, 记为 L(G),表示如下: $L(G)={α | S ⇒α^+ &  α∈V_T^*} $

假设有两个文法 G1 和 G2,若 L(G1) = L(G2),则称 G1 和 G2 是等价的。

最左推导,是指在整个推导过程中,每一步的替换操作都是针对句型中最左边的非终结符进行的。

如果在推导的每一步都替换的是句型最右边的非终结符,则将此过程称为最右推导,或者称为规范推导

2.2.3 语法分析树

语法分析树(语法树):通常是指一颗倒立的树,树根在上,枝叶在下,以此来表示 一个句型的推导过程。

一棵语法树是无法区分一 个推导是左推导还是右推导的。如果只考虑左推导(或右推导) , 则可以消除推导过程中产生式应用顺序的不一致性,从而使得每棵语法树都有一个 与之对应的唯一的左推导(或右推导),也就是说,一棵语法树就完全等价于 一个左(或右)推导。

2.2.4 文法的二义性

如果一个文法存在某个句子对应两棵不同的语法树,或者说,如果一个文法存在某个句子对应两个不同的最左(或最右)推导,则称该文法是二义的。

常常希望文法无二义性。

2.2.5 文法的分类

假设文法 $G =(V_T,V_N,S,P),   、(V_T V_N)^* $。

  • 0 型文法
    • 短语文法
    • P 中每个产生式 α→β 的左部 α 中至少含有 一个非终结符的文法
    • 描述 0 型语言,递归可枚举语言
    • 递归可枚举集必然是 0 型语言,由图灵机识别
  • 1 型文法
    • 上下文有关文法
    • 在 0 型文法基础上, P 中每个产 生式 α→β 还满足|α|≤ |β|(S→ε 除外)的文法
    • 对非终结符进行替换时必须考虑上下文环境,而且一般不允许替换成空串 ε
    • 描述 1 型语言,上下文有关语言,由线性界限自动机识别
  • 2 型文法
    • 上下文无关文法
    • P 中每个产生式形如 A→β 的文法, 其中 \(A \in V_N,\beta \in (V_T \cup V_N)^*\)
    • 对非终结符进行替换时不必考虑上下文
    • 2 型语言,上下文无关语言,由下推自动机识别
    • 描述高级程序设计语言的语法结构
  • 3 型文法
    • 正规文法
    • P 中每个产生式形如 A→αB 或 A→α 的文法,其中 \(A、B∈V_N,α∈V_T^*\),右线性文法
    • P 中每个产生式形如 A→Bα 或 A→α 的文法,其中 \(A、B∈V_N,α∈V_T^*\),z左线性文法
    • 3 型语言,正规语言,由有限自动机识别
    • 描述单词的构成

0 型文法包含 1 型文法,1 型文法包含 2 型文法,2 型文法包含 3 型文法。

3 型文法的描述能力弱,只能用来描述单词的构成;2 型文法的描述能力比 3 型文法的描述能力要强,可以描述现今大多数程序设计语言的语法结构;1 型文法的描述能力则比 2 型文法的描述能力更强;0 型文法的描述能力强。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×