搜索
2.3程序语言的语法描述2.3.1上下文无关文法2.3.2语法分析树与二义性2.3.3形式语言鸟瞰2.3.1上下文无关文法一、文法引入二、符号和符号串三、文法的直观概念四、文法和语言的形式定义一、文法引入1.如何形式地描述一种语言?2.规则的给出方式3.文法4.语法和文法6.上下文无关文法5.阐明语义1.如何形式地描述一种语言?•如果语言只含有有穷多个句子，只需列出句子的有穷集•如果语言含有无穷多个句子，需要给出它的有穷表示•生成方式•将语言中的每个句子用严格定义的规则来构造•识别方式•自动机从语法上描述2.规则的给出方式(a)递归规则(b)EBNF(c)语法图(d)文法(a)递归规则例：表达式1.任何标识符是表达式。2.任何常数是表达式。3.若表达式1和表达式2都是表达式，那么：表达式1+表达式2以及表达式1*表达式2都是表达式。例：语句(1)标识符:=表达式是语句。(2)while(表达式)do语句和if(表达式)then语句else语句都是语句。(b)EBNF(BACKUS-NAURFORM)扩充的巴科斯－瑙尔范式赋值语句::=标识符“:=”表达式表达式::=表达式“+”表达式表达式::=表达式“*”表达式表达式::=“(”表达式“)”表达式::=id表达式::=n∷=该符号的左部由右部定义,可读作'定义为'〈〉用尖括号括起来的部分表示语法单位EBNF表示的符号说明|表示‘或’{}表示其内的语法成分可以重复[]表示其内的成分为任选项()表示圆括号内的成分优先补充例:PL/0语言文法的EBNF表示程序∷=分程序．分程序∷=[常量说明部分][变量说明部分][过程说明部分]语句常量说明部分∷=CONST常量定义{,常量定义};常量定义∷=标识符〉=无符号整数无符号整数∷=数字〉{数字}变量说明部分∷=VAR标识符〉{,标识符};consta=10;varb,c;beginread(b);c:=11;whileb#0dobeginwrite(b*c);read(b)endend.PL0语言程序范例(c)语法图单词语法单位单词(d)文法例：表达式E→iE→E+EE→E*EE→(E)3.文法•文法是描述语言语法结构的形式规则。p26•文法是一种语言描述。这种描述是适当条数的规则，这些规则仅仅涉及句子的结构描述，这些规则用于产生所要描述的全部句子(可以无限多)。这些规则构成了语言的文法。•文法用生成方式描述语言,用文法可以产生一个合适的程序。也可以判别句子结构合法与否•为什么使用文法作为工具?•严格，无二义地定义句子的结构•以有穷集刻划无穷集合的工具-元语言(metalanguage)4.语法和文法•语法（Syntax）•语言中每个句子的构成规律•文法（Grammar）•阐明语法的工具•它所定义的语法范畴完全独立于这种范畴可能出现的环境•例:表达式•计算不必考虑上下文•变量声明、类型转换需考虑上下文•不宜于描述自然语言,但对于程序设计语言来说基本够用了5.上下文无关文法6.阐明语义•没有一种公认的形式语义系统可借助于用来自动构造出正确的编译系统