编译原理
chapter2
高级语言及其语法描述
2.3 程序语言的语法描述 符号串的长度:符号串中符号的个数为符号串的长度. 符号串的长度:符号串中符号的个数为符号串的长度. 长度 个数为符号串的长度 是符号串, 表示符号串的长度. 例:若ab是符号串,则|ab|表示符号串的长度. 是符号串 表示符号串的长度 |ab|=2 注意:特别规定 注意: 同理: 同理:|aabb|= 4 |ε|=0
编译原理
chapter2
高级语言及其语法描述
2.3 程序语言的语法描述
上下文无关文法
文法(Grammar):是描述语言的语法结构的形式规则. 是描述语言的语法结构的形式规则. 文法 是描述语言的语法结构的形式规则
The big elephant ate the peanut.
语法树(Parse Tree):句子结构的图形表示方式. 句子结构的图形表示方式. 语法树 句子结构的图形表示方式
编译原理
chapter2
高级语言及其语法描述
句子的推导:用规则(产生式) 句子的推导:用规则(产生式)按一定方式去推导或产生 句子的过程. 句子的过程.
<句子 句子> 句子 <主语 <谓语 主语> 谓语 主语 谓语> <冠词 <形容词 <名词 <谓语 冠词> 形容词> 名词> 谓语> 冠词 形容词 名词 谓语 The <形容词 <名词 <谓语 形容词> 名词> 谓语> 形容词 名词 谓语 The big <名词> <谓语> <名词 <谓语 名词> 谓语> The big elephant <谓语 谓语> 谓语 The big elephant <动词 <直接宾语 动词> 直接宾语> 动词 直接宾语 The big elephant ate <直接宾语 直接宾语> 直接宾语 The big elephant ate <冠词 名词 冠词><名词 冠词 名词> The big elephant ate the <名词 名词> 名词 The big elephant ate the peanut
编译原理
chapter2
高级语言及其语法描述
2.3 程序语言的语法描述 符号串的运算: 符号串的运算: 连接( ):符号串 符号串的连接 联结,乘积):符号串x和 的连接是 符号串的连接(联结,乘积):符号串 和y的连接是 的符号按先后顺序排列 指x和y的符号按先后顺序排列在一起组成一个新的符 和 的符号按先后顺序排列在一起组成一个新的符 号串, 表示. 号串,用xy表示. 表示 若字母表∑={a,b},符号串 例,若字母表 ,符号串x=ab,y=ba , 则xy=abba 注意: 连接运算不满足交换律 注意 (1)连接运算不满足交换律,即xy≠yx 连接运算不满足交换律, (2)任何符号串 与空串 的连接都等于 ,即: 任何符号串x与空串 的连接都等于x, 任何符号串 与空串ε的连接都等于 εx=xε=x
<句子 →<主语 <谓语 句子> 主语> 谓语> 句子 主语 谓语 <主语 → <冠词 <形容词 <名词 主语> 冠词> 形容词> 名词> 主语 冠词 形容词 名词 <冠词 → the 冠词> 冠词 <形容词 →big 形容词> 形容词 <谓词 → <动词 <直接宾语 谓词> 动词> 直接宾语> 谓词 动词 直接宾语 <动词 →ate 动词> 动词 <直接宾语 →<冠词 <名词 直接宾语> 冠词> 名词> 直接宾语 冠词 名词 <名词 →elephant 名词> 名词 <名词 →peanut 名词> 名词
<句子 句子> 句子 <主语 主语> 主语 <冠词 冠词> 冠词 <形容词 <名词 形容词> 名词 名词> 形容词 <动词 动词> 动词 <谓语 谓语> 谓语 <直接宾语 直接宾语> 直接宾语 <冠词 冠词> 冠词 The big elephan t ate the <名词 名词> 名词 peanut
显然, 显然,若n>0,则Xn=XXn-1 =Xn-1X 则 符号串的幂运算服从结合律 即:符号串的幂运算服从结合律 .
编译原理
chapter2
高级语言及其语法描述
2.3 程序语言的语法描述 的运算: 符号串集合的运算: 运算: 为符号串集合( 符号串集合的乘积运算:设A,B为符号串集合(集合 , 为符号串集合 中各元素都是字母表上的字符串), ),两个字符串集合的 中各元素都是字母表上的字符串),两个字符串集合的 乘积定义为: 乘积定义为:AB={xy|x∈A , y∈B}(笛卡儿乘积). ∈ ∈ (笛卡儿乘积). 设有字母表∑={a,b,c,d},令A={aa,bb},B={cc,dd} 例:设有字母表 , , 则AB= {aacc,aadd,bbcc,bbdd} BA= {ccaa,ccbb,ddaa,ddbb} 特别定义:空符号集合:{ε} 特别定义:空符号集合: 空集合:φ={} 空集合: 注意: 注意:因εx = xε ,故 {ε}A=A{ε}=A A φ= φA= φ
编译原理
chapter2
高级语言及其语法描述
定义3 符号串的推导与归约 已给文法G=(VN,VT,P,S), 推导与归约: 定义 :符号串的推导与归约:已给文法 , V= VN∪VT,令x,y,α,β∈V*,且α→β∈P,此时,由 ∈ , ∈ ,此时, 符号串xαy能够直接产生出符号串 能够直接产生出符号串xβy,我们称: 符号串 能够直接产生出符号串 ,我们称: 符号串xβy是符号串 是符号串xαy的直接推导; 符号串 是符号串 的 符号串xαy是符号串 是符号串xβy的直接归约; 符号串 是符号串 的
定义2:文法是一个四元组:G[S]=(VN, VT, P, S),其中: 是一个四元组: 定义 :文法是一个四元组 ,其中: VN:非终结符集合; 非终结符集合 集合; VT :终结符集合; 终结符集合 集合; P :产生式集合(α→β或α∷=β); 产生式集合 集合( 或 ∷ ); 开始符号(或称根符号 识别符号). 或称根符号, S :开始符号 或称根符号,识别符号 . 另外: 也可简写为G 另外:G[S]也可简写为 也可简写为
编译原理
chapter2
高级语言及其语法描述
例:G1 =({N},{0,1},{N→0N,N→1N,N→0,N→1},N) , ) 其中: 其中 非终结符 VN ={N} 终结符V 终结符 T ={0,1} , P={N→0N,N→1N,N→0,N→1} , , , 开始符号S 开始符号S 为N 通常情况下,文法只用产生式集合表示: 通常情况下,文法只用产生式集合表示: G1[N]: N→0N N→1N N→0 N→1
记作: xαy xβy
若有α 若有 1,α2,…,αn∈V* 且α1 α2 … αn-1 αn + 的推导. 则称α 则称 n是α1的推导. αn 记作: 记作:α1 特别约定:若在推导关系α α 中允许α 特别约定:若在推导关系 1 n中允许 1=αn, 的广义推导. 则称α 则称 n是α1 的广义推导. * 记作: 记作:α1 αn
编译原理
chapter2
高级语言及其语法描述
2.1 程序语言的定义 词法规则:单词符号的形成规则. 词法规则:单词符号的形成规则.也就是规定了 字母表中哪些字符串是一个单词符号. 字母表中哪些字符串是一个单词符号. 正规式和有限自动机理论 语法规则:是语法单位的形成规则. 语法规则:是语法单位的形成规则.也就是规定 了如何从单词符号形成更大的语法单位. 了如何从单词符号形成更大的语法单位. 上下文无关文法和有限自动机 语义:可以定义程序意义的规则. 语义:可以定义程序意义的规则. 语法制导翻译方法
2.3 程序语言的语法描述 字母表:字母表∑是有穷符号元素的非空集合 符号元素的非空集合. 字母表:字母表 是有穷符号元素的非空集合. 符号:字母表中的元素. 符号:字母表中的元素. 符号串:字母表中的符号所组成的任意有穷序列. 有穷序列 符号串:字母表中的符号所组成的任意有穷序列. 空符号串:不含任何符号的符号串, 用 ε 表示. 表示. 空符号串:不含任何符号的符号串, 例如,若有字母表 例如,若有字母表∑={a,b} 是字母表∑中的元素 符号) 则a,b是字母表 中的元素 符号 是字母表 中的元素(符号 a,b,aa,ab,ba…都是符号串. 都是符号串. 都是符号串 注意: 注意:符号串中的符号与顺序有关
编译原理
chapter2
高级语言及其语法描述
2.3 程序语言的语法描述 为符号串集合, 符号串集合的幂运算: 符号串集合的幂运算:设A为符号串集合,则集合的幂 为符号串集合 运算定义如下: 运算定义如下
A0={ε} A1=A A2=AA … A= AA……A =AAn-1 =An-1A n个 个
符号串集合的闭包:设A为符号串集合,则集合的闭包 为符号串集合, 符号串集合的闭包: 闭包 为符号串集合 定义如下: 定义如下 A的正则闭包: A+=A1∪A2∪… 的正则闭包: A的闭包: A*=A0∪A1∪A2∪… 的闭包: 例:设集合A={a,b},则 设集合 , A+={a,b,aa,ab,ba,bb,aaa, …} A*={ε,a,b,aa,ab,ba,bb,aaa, …} 显然: A+=AA* 显然: A*=A0∪A+
编译原理
chapter2
高级语言及其语法描述