您的位置: 首页  >  文章  >  编译原理第二章 高级语言及其语法描述

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

分类: 文章 • 2025-04-28 08:42:22

一、知识总结

2.1  程序语言的定义

程序语言是建立在有限字母集之上的一个符号系统，功能是描述数据和对数据的运算。

程序语言主要由语法和语义两方面定义。

1.语法

定义：一组规则，使用它可以产生形式上正确的程序。

这些规则包括词法规则（单词）和语法规则（程序）。

  •     字母表
  •     单词符号：语言中具有独立意义的最基本结构
  •     语法单位

2.语义

定义：一组规则，使用它可以定义一个程序的意义。

这些规则为语义规则。

 2.2高级语言的一般特性

1.分类

按语言范型分类：

  • 强制式语言，也称过程式语言
  • 应用式语言，也称函数式语言
  • 基于规则的语言
  • 面向对象的语言——封装性、继承性、多态性

2.程序设计语言的一般特性：

  • 程序结构——决定符号表构造方法
  • 数据类型与操作——数据类型三要素：属性、值、操作

            数据类型分类：      

                    基本数据类型（int，char,float,double）

                    构造数据类型(指针，静态数组，动态数组)

                    自定义数据类型（栈，队列，字符串，结构体）

            数据结构类型：

                    数组：由同一类型数据所组成的某种n维矩形结构

                    记录

                    字符串、表格、栈、队列

  • 语句与控制结构

            表达式：运算量和算符组成，表示形式有前缀式、中缀式、后缀式

            语句：分为说明性语句和执行性语句（包括赋值语句、控制语句、输入/输出语句）

2.3程序语言的语法描述

1.基础概念

  • 字母表：由若干元素组成的有限非空集合，用S表示，它的每个元素称为一个符号。
  • 符号串： 由S中的符号所构成的有穷序列。
  • 空字：不包含任何符号的序列，记为e。
  • 用S*表示S上的所有符号串的全体，空字也包括在其中。如：

            若S={a,b},则S*={e,a,b,aa,ab,bb,aaa,…}。

  • f表示不含任何元素的空集{}。
  • S*的子集U和V中的（连接）积定义为:UV={ab∣aÎU & bÎV }
  • 符号串集合V自身的n次（连接）积记为：Vn = V V…V (n个V)，规定V0 = {e}
  • V的闭包V* =V0ÈV1ÈV2È…
  • V的正则包（正闭包，正则闭包）：V+ = VV* =V1ÈV2ÈV3È…

2.上下文无关文法

文法是描述语言的语法结构的形式规则（即语法规则）。

  • 特点：所定义的语法范畴是完全独立于这种范畴可能出现的环境的——独立性
  • 缺点：不能用来描述自然语言

形式上定义一个上下文无关文法Ｇ是一个四元式（ＶＴ，ＶＮ，Ｓ，P），包括四个组成部分：

一组终结符号ＶＴ：组成语言的基本符号（单词符号）；

一组非终结符号ＶＮ（语法变量）：代表语法范畴，代表一个一定的语法概念；

一个开始符号Ｓ：特殊的非终结符号，我们最感兴趣的语法范畴；

一组产生式P（产生规则、简称规则）：定义语法范畴的一种书写规则，形式为A→ α。

3.语法分析树（表示推导过程）

  • 根结点由开始符号标记。
  • 随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结点。
  • 在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型。

4.文法的二义性

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

  • 文法的二义性证明：找出一个句子，它有两个不同的最左推导或最右推导
  • 文法的二义性是不可判定的
  • 文法二义性的消除：给每个产生式定义优先级

5.形式语言鸟瞰

乔姆斯基把文法分成四种类型：0型、1型、2型、3型，对比如下表：

  产生式形式 文法名称 定义的语言 描述能力 包含关系
0型文法

α->β

 短语文法 递归可枚举语言 最强 -
1型文法 α->β、|α|<=β 上下文有关文法 上下文有关语言 次之 也是0型文法
2型文法 A->β 上下文无关文法 上下文无关语言 次之 0、1型文法
3型文法 A->Bβ、A->βB 正规文法 正规语言 最弱 0、1、2型文法
二、课后习题

6.（1）L(G1)表示0到9组成的字符串

（2）最左推导：

    N->ND->NDD->NDDD->DDDD->0DDD->01DD->012D->0127

    N->ND->DD->3D->34

    N->ND->NDD->DDD->5DD->56D->568

        最右推导：

    N->ND->N7->ND7->N27->ND27->N127->D127->0127

    N->ND->N4->D4->34

    N->ND->N8->ND8->N68->D68->568

7.分析：奇数的组成和特点：可以包含符号位，可以是一位奇数1、3、5、7、9，可以是多位奇数：首位不能为0，末位只能是1、3、5、7、9，中间为任意。

G(Z):

E->SA|SB

S->+|-|e

A->1|3|5|7|9

C->A|2|4|6|8

D->0|C

G->0|A

B->CFG

F->DF|D|e

8.（1）最左推导：

    E->E+T->T+T->F+T->i+T->i+T*F->i+F*F->i+i*F->i+i*i

    E->T->T*F->F*F->i*F->i*(E)->i*(E+T)->i*(T+T)->i*(F+T)->i*(i*T)->i*(i+F)->i*(i+i)

    最右推导：

    E->E+T->E+T*F->E+T*i-> E+F*i->E+i*i-> T+i*i -> F+i*i ->i+i*i

    E->T->F*T->F*F->F*(E)->F*(E+T)->F*(E+F)->F*(E+i)->F*(T*i)->F*(F+i)->F*(i+i)->i*(i+i)

（2）语法树

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

三、学习反思

这一章主要讲解了高级程序语言的定义和特征，重点内容是高级语言的语法描述和应用。本章概念比较多 ，而概念是学好后面应用的基础。对于这些概念要深入理解，真正的搞明白概念所说的东西，而不能是一味的死记硬背概念。词法、语法、句型、句子、最左推导、最右推导等知识都比较抽象，对此的理解我的方法是找一个实例，在实例的基础上理解，把抽象的东西具体化。同时课后的总结复习也很重要，把概念都整理出来对比理解，这样也可以加深印象。





相关推荐