高级语言及其语法描述

第2章高级语言及其语法描述程序语言的定义记号系统=语法+语义+[语用]词法规则语法规则语

法:词法规则和语法规则定义了程序的形式结构,是判断输入字符串是否构成一个形式上正确程序的依据。

定义：是指规定如何由基本符号组成一个完整的程序的规则。可以分文一般的词法规则和语法规则（产生规则)。例子：0.5*X1+C语言的词法规则——单词符号的形成规则单词符号是语言中具有独立意义的最基本单位，包括各类型的常数、标识符、基本字、算符和界符等。语言的语法规则——语法单位的形成规则规定如何从单词符号形成语法单位（包括：表达式、语句、分程序、函数、过程和程序等)的规则。语法规则的描述——上下文无关文法语

义:添加标题语义——单词符号和语法单位的意义。添加标题形式上完全相同的语法单位在不同的语言中语义是不相同的。描述数据和对数据运算。程序语言的每个组成成分都有（抽象的)逻辑和计算机实现两方面的意义。

程序语言的基本功能:高级语言的一般特性:类别特点语法形式示例类别特点示例备注高级语言的分类程序结构数据类型与操作

（P19)类别数据运算示例初等数据类型数据结构抽象数据类型标识符——由字母或数字组成的以字母为开头的一个字符串。它没有意义。名

字——是代表一个抽象的存储单元，存储单元的内容就是该名字的值，也是名字所表示的一个具体对象，名字还有明确的属性（包括类型和作用域)和意义。

数据类型与操作

（P19)：赋值语句

（P24)：01A:=B02右值,表示名字的值03左值,存储单元,地址：字母表——有穷符号集合(注意：是“符号”，而不是“字符”)符号——字母表中的元素例如：

={a,b,c,d,e,….z}

={begin,end,if,for,while}符号串——字母表中的符号构成的有穷序列例如：{aa,bb,cc,dd,…}（显然是一个无穷的集合)空字：不包含任何符号的序列，记为

。注意区分：

，{}，{

}程序语言的语法形式描述(P25)用

*表示*上的所有符号串的全体例如:

={a,b}，则

*={

,a,b,aa,ab,ba,bb,aaa,…}（U、V是

*的子集)即UV中的符号串是U和V中的符号串连接而成的。

连接积——UV={|U且V}例如:U={a,b}、V={aa,bb}则UV={aaa,abb，baa，bbb}Vn=VVV……V规定V0={}

闭包:V*=V0UV1UV2UV3U……正则闭包:V+=VV*

例如:已知字母表X={0,1,2,3,4,5,6,7}，求X*和X+解答:X0={

}，X1=X={0,1,2,3,4,5,6,7}，

X2={00,01,02,03,04,05,06,07，……，77}…………X*={

,0,1,2,3,4,5,6,7,00，…77，000，…，777，…}X+=XX*={0,1,2,3,4,5,6,7,00，…77，000，…，777，…}上下文无关文法（P27)：G={终结符VT，非终结符集VN，开始符号S，产生式集P}（P27)文法的表示方法；G,G[S]2.上下文无关文法1.概念文法——描述语言的语法结构的形式规则（即语法规则)上下文无关文法——文法所定义的语法单位是完全独立于这种语法单位可能出现的环境的。

单击此处可添加副标题例子：给定如下子语言框架：<程序>->Program<程序>;<分程序><分程序>-><分程序体>|<说明>;<分程序体><说明>->Integer<标识符表>|Real|<标识符表>|Bloolean<标识符表>|Procedure<过程标识符><分程序>|<说明>;<说明>;<分程序体>->Begin<语句>End<语句>-><标识符>|<特殊字符>|<语句>;<语句><程序名>-><标识符><过程标识符>-><标识符><标识符表>-><标识符>|<标识符>|<标识符表><标识符>-><字母>|<标识符><字母>|<标识符><数字><特殊字符>->$单击此处添加大标题内容添加标题<字母>->A|B|…|Z|a|b|…|z添加标题<数字>->0|1|2|3|4|5|6|7|8|9|添加标题该子语言文法的开始符号为（)，终结符号为（)非终结符号为（)。

例子:hegavemeabook.VT={he，gave，me，a，book}VN={<句子>,<主语>,<谓语>,<直接宾语>,<间接宾语>,<代词>,<冠词>,<动词>,<名词>}S=<句子>P={<句子>-><主语><谓语><直接宾语><间接宾语>,<主语>--><代词>,…………<代词>-->he,…………}<句子>语法树me<代词><冠词><名词>abook<代词><主语>he<谓语><动词><间接宾语>gave<直接宾语>推导（P29)、最左推导和最右推导（P30)句型、句子

（P29)例如：文法2.1：E→E+E|E*E|（E)|i的推导

单击此处添加正文,文字是您思想的提炼,为了演示发布的良好效果,请言简意赅地阐述您的观点。

E→（E)→（E+E)→（E*E+E)→（i*E+E)→（i*i+E)→（i*i+i)句型有：

（E)、（E+E)、（E*E+E)、（i*E+E)、（i*i+E)、

（i*i+i)句子有：（i*i+i)单击此处添加正文,文字是您思想的提炼,为了演示发布的良好效果,请言简意赅地阐述您的观点。

5.语法树（P31）可以用语法树表示一个句子的结构。语法树是以开始符号（识别符)为根，以句子的推导过程为依据，对每个非终结符，把它的推导所用产生式的右部的全部符号作为它的子结点。语法树的全部叶子，从左到右就是这个句子。

<句子>语法树me<代词><冠词><名词>abook<代词><主语>he<谓语><动词><间接宾语>gave<直接宾语>6、语法树和语法的二义性（P31)某个文法的某个句子存在两个不同的语法树。不能在有限的步骤中一般地证明一个文法是二义的例如：文法2.1：E→E+E|E*E|（E)|i的句子

(i*i+i)的最右推导和最左推导就对应2棵不同的语法树)E(E+EEE*Eiii)E(E*EEE+Eiii判定的额结果是针对文法的,但判定的关键是两棵不同的语法树对应同一个选定的句子。

形式语言鸟瞰:添加标题0型文法——短语文法添加标题1型文法——上下文有关文法添加标题2型文法——上下文无关文法添加标题3型文法——左/右线性文法文法的4种类型:文法的使用限制语法树与二义性文法和语言的形式定义符号与符号串文法和语法字母表与符号串符号串集合的运算（闭包)文法的形式定义语法分析的基本术语语言的形式定义推导与规约句