程序设计语言与编译
语法描述方法等价
文法和语法图是语言语法的等价表示 文法从产生的观点来定义语言的语法， 更通用、更准确。 语法图以识别的观点定义语言的语法， 更直观、更清晰。
程序设计语言与编译
采用生成的方法还是采用识别的方 法来定义语言
由语言的设计者确定。
程序设计语言与编译 4.语法描述的基本用途
个合式(well-formed)的程序。
例：字符串 0.5x1+c 其中，0.5、x1、等称单词符号，而表达 式称语言的一个语法范畴或语法单位。
5
程序设计语言与编译
语法
词法规则：单词符号的形成规则。
– 单词符号是语言中具有独立意义的最基本结构 。一般包括：常数、标识符、基本字、算符、 界符等。
+ * /
)
表达式
18
程序设计语言与编译
② 识别原则 若一个终结符序列是合法的，那么,必须从语法图的 入口边通过语法图而到达出口边，而且在通过的过 程中,恰恰能识别该终结符序列。具体如下： ①终结符框:标识的终结符与被识别的终结符刚好符合 ①非终结符框:由该非终结符的语法图来识别； ②分支:若遇到分支，则任选一分支来识别；
注意：描述以上规则的符号系统称为巴科斯-诺 尔范式，即通常的BNF（Backus-Naur Form）。
12
Hale Waihona Puke 程序设计语言与编译② 文法
在形式语言中，上述例子可写成文法 G=(N,T,P,S)其中
N={<语句>,<主语>,<谓语>} T={I,students,study,run} P={<语句>→<主语><谓语>,
x
非终结符N 对应于
N
16
程序设计语言与编译
N→1|2|…|n
1
2
→b1b2…bm
n
b1 b2
bm
→b|g
g b
17
程序设计语言与编译
语法图的一些例子
字母 标识符
数字 字母
运算符
字母
标识符
(
表达式
)
表达式
运算符 表达式
(
表达式
表达式
表达式
+ * /
数字
字母 表达式
严重的困难，但仍必须严格根据语言的定义实现它
3
程序设计语言与编译
一个程序语言是一个记号系统
• 程序语言由两方面定义：
–语法 –语义 –语用
语言＝语法＋语义 语法:用以构造程序及其成分的一组规则的集合 语义:用以规定语法正确的程序或其成分的含义的一组规
则的集合
4
程序设计语言与编译 1. 语 法
• 程序本质上是一定字符集上的字符串。 • 语法：一组规则，用它可以形成和产生一
③回溯:若一个分支识别不成功，则选另一分支来识别
③ 语言 语法图能识别的所有终结符序列的集合
19
程序设计语言与编译
高级语言语法规则的描述方法
FORTRAN采用自然语言描述语法； ALGOL 60首次用BNF对语法进行 形式描述,为语言定义做出了重要贡献； Pascal首次采用语法图来定义语言， 给出了较为直观的语法结构。
10
程序设计语言与编译
语言的定义
语言的定义可以从生成（文法） 和识别（语法图）的观点进行。
程序设计语言与编译
2.生成的观点
① 一个简单英语句子的描述 I/Students Study/Run
如何描述？
<语句>→<主语><谓语> <主语>→I|Students <谓语>→Study|Run
每一行称为一条语法规则； 终结符、非终结符
程序设计语言与编译
表达式
<表达式>→<标识符> <表达式>→(<表达式>) <表达式>→<表达式><运算符><表达式> <运算符>→+|-|*|/
15
程序设计语言与编译
3.识别的观点：语法图
①定义
每一非终结符N连同相应的产生式 N→a1|a2|…|an
对应一个语法图；具体对应如下：
终结符x 对应于
<主语>→I|Students, <谓语>→Study|Run} S=<语句>
③ 语言:所有句子的集合
④ 标识符和表达式描述
13
程序设计语言与编译
标识符
<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→A|…|Z|a|…|z <数字>→0|…|9
14
程序设计语言与编译
第四章 程序语言的设计
第2章和第3章分别讨论了程序设计 语言的数据类型和控制结构，
分别描述程序的数据结构和算法。 本章介绍语言的设计方法。
程序设计语言与编译
主要内容 1.语言的定义
语法：定义语言是否合法的一组规则 语义：用以规定程序或其成分的含义 2.文法：定义语言语法的形式化规则 3.语言的设计
程序设计语言与编译
程序
自上而下：
每一层由其
下层部分组 成。
子程序或分程序
语句
自下而上：
通过对下层成 分的理解来掌 握上层成分， 从而掌握整个 程序。
表达式
数据引用
算符
函数调用
9
程序设计语言与编译
一.语法
1.几个术语
①字 母 表:语言允许使用字符的集合,其元素称为字符 ②符 号:由字符组成的有限串（字符串） ③字 汇 表:由符号组成的集合，其元素称为字 ④词法规则:规定什么样的字符串可以构成语言的有效符号 ⑤语法规则:确定一个符号序列是否为一个句子, 并提供句子 的结构（什么样的符号序列是合法的）
– 描述工具：有限自动机
语法规则：语法单位的形成规则。
– 语法单位通常包括：表达式、语句、分程序、 过程、函数、程序等;
– 描述工具：上下文无关文法
本课程中，有限自动机和上下文无关文 法是词法分析和语法分析的主要理论基础。
6
程序设计语言与编译 2. 语 义
• 语义：一组规则，用它可以定义一个程 序的意义。
2
程§序2设.1计程语序言语与言编的译定义
程序设计语言是用来描述计算机所执行的 算法的形式表示；
语言定义是语言实现的基础：
从语言用户角度看
– 语言初等成分的实际含义是什么？ – 如何有意义地使用它们？
– 怎样以有意义的方式组合它们？
从编译程序设计者角度看
– 哪些构造允许出现
» 即使一时不能看出某种构造的实际应用，或者判断实现该结构会导致
• 描述方法：
–自然语言描述：隐藏错误、二义性和不完整 性
–形式描述：
操作语义(PL/1) 指称语义(ADA) 代数语义(PASCAL)
7
程序设计语言与编译
程序语言的基本功能和层次结构
程序语言的基本功能：描述数据和对数据 的运算。
所谓程序，本质上说是描述一定数据的处 理过程。
8