第2章编译原理.ppt

第2章高级语言及其语法描述教学目的2.1程序语言的定义语言研究的三个方面计算机语言的组成结构一个程序语言就是一个记号系统
主要由语法和语义两方面定义。
语法形成和产生合适程序的规则集
词法规则形成单词符号的规则
语法规则形成语法单位的规则
语义用以定义程序意义的规则集
在不同语言中完全相同的语法单位
含义却可能完全不同
例如：x=yC语言——赋值表达式
Pascal语言——关系表达式C中x==y程序语言的语法构成2.2高级语言的一般特性2.3程序语言的语法描述基本概念符号串由字母表中的符号所组成的任何有穷序
列称为该字母表上的符号串
例001110是字母表∑上的符号串(∑={0，1})
a,b,aa,bb,abb,bba,…都是字母表A上的符号串(A={a，b}
注意符号串中符号的顺序是重要的
例ab不同于ba
符号串的长度符号串中符号的个数
例x=001110则x长度|x|=6
空串(ε—空字)长度为0的符号串（不包含任何符号）
|ε|=0
子符号串v是xvy的子符号串，v非空
头，尾x是xy的头，y是xy的尾
符号串集合
若集合A中的一切元素都是某字母表上的符号
串，则称A为该字母表上的符号串的集合
例∑={0，1}是字母表,其中0,1为符号，则D={0,1}其中0,1为符号串
E={ε,0,1,00,01,10,11,000,…}
是∑上的符号串集合

特别空集记为ф={}注意与ε区别
连接(并置)x=123,y=45那么xy=12345

乘积UV={αβ|αU且βV}
例A={a，b}B={c，d}
则AB={ac，ad，bc，bd}

方幂V的n次方幂就是将n个V相乘
设A={a，b}
A0={ε}
A1=A={a，b}
A2=AA={aa，ab，ba，bb}
An=AA…A(n个A的乘积）
所有由A中符号构成的长度为n的符号串的集合符号串集V的闭包V*
V*=V0∪V1∪V2∪V3∪…
设V={a，b}，则
V*={ε}∪{a，b}∪{aa，ab，ba，bb}∪…
={ε，a，b，aa，ab，ba，bb，aaa，…}
V的闭包V*是V上的所有符号串(包括空字ε)的集合

符号串集V正则闭包V+
V*=V0∪V1∪V2∪V3∪…=V0V+
设V={a，b}，则
V+={a，b}∪{aa，ab，ba，bb}∪…
={a，b，aa，ab，ba，bb，aaa，…}
V的正则闭包V+是V上的所有的非空符号串的集合30-8月-25例：Hegavemeabook
应用P26的语法规则：
句子
=>主语谓语间接宾语直接宾语
=>代词谓语间接宾语直接宾语
=>He谓语间接宾语直接宾语
=>He动词间接宾语直接宾语
=>Hegave间接宾语直接宾语
=>Hegave代词直接宾语
=>Hegaveme直接宾语
=>Hegaveme冠词名词
=>Hegavemea名词
=>Hegavemeabook例Hegavemeabook上下文无关文法G组成文法G的形式定义上下文无关文法描述约定例算术表达式的文法G什么是直接推导？说明：什么是句型、句子？例:文法G(E)为：
E→E+E|E*E|(E)|i
表达式(i*i+i)的生成
E=>(E)
=>(E+E)
=>(E*E+E)
=>(i*E+E)
=>(i*i+E)
=>(i*i+i)例:文法G(E)为：
E→E+E|E*E|(E)|i
表达式i+i*i的生成
E=>E+E
=>i+E
=>i+E*E
=>i+i*E
=>i+i*i什么是语言？文法G1：S→bA
A→aA|a
S=>bA=>ba
S=>bA=>baA=>baa
S=>bA=>baA=>baaA
=>baaa
L(G1)={ban|n>=1}构造一个文法G3，使L(G3)={anbn|n>=1}
分析每个句子，a在前，b在后，且个数相同
文法G3(S):S→aSb|ab

构造一个文法G，使L(G)={anbnci|n>=1,i>=0}
分析每个句子分成两部分考虑
ab(至少出现一次)c(可以不出现)
ab个数相同,与c的个数可以不同
文法G(S):S→AC|A
A→aAb|ab
C→Cc|c练习最左(右)推导什么是语法树？句子i+i*i的最左推导过程
E=>E+E
=>i+E
=>i+E*E
=>i+i*E
=>i+i*i语法树的构造特点30-8月-25例：文法G:
S→AB
A→aAb|ab
B→cBd|cd
请给出abccdd的
语法树
语法树的特点一个句型是否对应唯一的一棵语法树？文法的二义性文法的二义性和语言的二义性二义性文法的判定无二义性文法文法的分类2型文法（上下文无关文法）
对任一产生式α→β，
都有α∈ＶN，β∈(ＶN∪ＶT)*
例如E→E+T|T
足以描述大多数程序设计语言语法特征
该文法中要求α