编译原理及实现技术：6.语法分析 形式语言基础.ppt

第三章：语法分析  文法与语言 文法的分类 文法的相关概念
内容介绍
文法与语言
文法的相关概念
文法的分类
语言与文法
文法的产生：自然语言与程序设计语言的区别
语言的三个基本要素：语法、语义、语用
语言与文法
文法能清晰地描述程序设计语言的语法构成易于理解。
文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。
文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。
基于文法实现的语言易于扩展。
巴克斯范式BNF
BNF：
语法成分::=组成部分
赋值语句::=变量=表达式
变量::=标识符|下标变量|指针变量...
表达式::=算术表达式|逻辑表达式...
上下文无关文法
上下文无关文法的规则：
P(语法符号)X1X2...Xn
赋值语句变量=表达式
文法G定义为四元组(VT,VN,S,P)
VT是有限的终极符集合
VN是有限的非终极符集合
S是开始符，SVN
P是产生式（规则）的集合
上下文无关文法
例子和简写：
G={VN,VT,P,S}
VN={N,D} VT={0,1,2,...,9}
P={ND, NND, D0|1|...|9多条规则}
S=N
基本概念(1)
直接推导：如果A是一个产生式，则有1A212,其中表示一步推导。这时称12是由1A2直接推导的。
的含义是，使用一条规则，代替左边的符号，产生右端的符号串。
A + :表示A通过一步或多步可推导出
A * :表示A通过零步或多步可推导出
基本概念(1)
句型：设有文法G，如果有S*  ，则称符号串为G的句型 。我们用SF(G)表示文法G的所有句型的集合 (VTVN)*
句子：设为文法G的一个句型，且只包含终极符，则称为G的句子   VT*
语言：L(G)={ | S + ,  VT* }。 文法G所定义的语言是其所有句子的集合。
基本概念与高级语言语法
每一种高级程序设计语言都有自己的语法
符合高级语言文法的程序就是该语法的句子
所有程序组成的集合就构成了语言。