编译原理 第2章 文法和语言的基本知识

所谓文法是在形式上对句子结构的定义与描述，而未
涉及语义问题。
编译原理
2013年11月17日
• 例2-3，利用例2-2中的文法，推导出文法的句子012： 最左推导：N =>S =>SD =>SDD =>DDD =>0DD =>01D =>012 最右推导：N =>S =>SD =>S2 =>SD2 =>S12 =>D12 =>012 2 1 在这里，N S为长度为1的推导， N SD为长度为2的推导 7 N 012为长度为7的推导。其中，对于N S来说，S是N的直接推 导，或N是S的直接归约。 • 一些规定： =>推导 N S =>规范推导 S SD|D 长度大于零的推导 * D 0|1|2…|9 长度可为零的推导 n 长度为n的推导
编译原理
2013年11月17日
1.语法规则：我们通过建立一组规则，来描述句子的语法结构。 规定用“::=”表示“由……组成”。
文法的BBiblioteka BaiduF表示
<句子>::=<主语><谓语> <主语>::=<代词>|<名词> <代词> ::=你|我|他 <名词>::= 王民|大学生|工人|英语 <谓语>::=<动词><直接宾语> <动词>::=是|学习 <直接宾语>::=<代词>|<名词>
编译原理
2013年11月17日
教学内容
• 2.1 字母表和符号串的基本概念
• 2.2 文法和语言的形式定义 • 2.3 句型的分析 • 2.4 文法和语言的分类
编译原理
2013年11月17日
• 程序设计语言是一种形式语言，与自然语言既有相 似的性质又有本质的不同。 –最主要的区别是：形式语言的规则简单、严格、 无例外、无二义性。 • 编译程序的正确转换建立在对程序设计语言的精确 定义和描述基础上。 –语法——文法是描述语言语法的形式规则 –语义——语言中各语句的含义 –语用——从使用者的角度对语言的描述
=> the big elephant ate the <名词>
=> the big elephant ate the
编译原理
peanut
2013年11月17日
+ 上述推导可写成<句子> => the big elephant ate the peanut
说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为最左推导，类似的有最右推导（一般推 导）。 (2) 从一组规则可推出不同的句子，如以上规则还可推出 “大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们 在语法上都正确，但在语义上都不正确。
T N
编译原理
2013年11月17日
赋值语句
y =x+r*6
表达式
标识符
= y
表达式
+
表达式
标识符
表达式
*
表达式
x
标识符
整数
r
编译原理
6
2013年11月17日
文法的非形式定义
例：有一句子：“我是大学生” 。这是一个在语法、 语义上都正确定句子，该句子的结构（称为语法结构）是由 它的语法决定的 。在本例中它为“主谓结构”。 如何定义句子的合法性？ •有穷语言：只需逐一列举句子 •无穷语言：使用文法定义句子的结构，用适当条数的规 则把语言的全部句子描述出来。文法是以有穷的集 合刻划无穷的集合的工具。
编译原理
2013年11月17日
2.由规则推导句子：有了一组规则之后，可以按照一定的方式 用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应规则的 右部来替代规则的左部，每次仅用一条规则去进行推导。
<句子> => <主语><谓语>
<主语><谓语> => <代词><谓语>
…… ……

编译原理
2013年11月17日
• 文法的形式定义：P10的定义1.1 V V – 例2-1，文法G=（ ， ，P，S）是描述标识符的文 法，则其中： V N ={标识符，字母，数字} V T ={a,b,c….x,y,z,0,1,2,3…9} P ={<标识符> <字母>|<标识符><字母>| <标识符><数字> <字母> a|b|c|….|z <数字> 0|1|2|….|9} S =<标识符>
第2章
文法和语言的基本知识
教学目标
1. 本章是编译原理课程的理论基础，要求掌握形 式语言的基本术语和概念,重点掌握短语、直接 短语、句柄、素短语、规范推导、规范归约。 2. 掌握文法和语言的定义，文法的二义性与递归 性的判断方法及句型的分析方法，文法分类。 3. 熟练使用文法定义程序设计语言的单词和语法 成分。 4. 对形式语言的理论有一个初步认识。
编译原理
编译原理
2013年11月17日
符号串的运算
符号串的连接运算 符号串x和y的连接:是把y的符号写在x的符号之后 得到的符号串xy 例如x=00，y=11，则xy=0011 对于任意一个符号串s，有εs= sε=s
编译原理
2013年11月17日
符号串的幂运算 符号串自身连接n次得到的符号串sn 定义为 ss…ss ，包括n个s，称为符号串的幂运算 s0=ε，s1=s，s2=ss，…… 设s=01，则 s0=ε s1=01 s2=0101 „„
<名词>::= 王民|大学生|工人|英语
<谓语>::=<动词><直接宾语> <动词>::=是|学习 <直接宾语>::=<代词>|<名词>
<句子> => <主语><谓语>
=> < 代词><谓语>
=> 我<谓语>
=>我<动词><直接宾语> =>我是<直接宾语> =>我是<名词> =>我是大学生
编译原理
2013年11月17日
编译原理
2013年11月17日
符号串集合的闭包运算
设A是符号串集合，定义 A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪…… 称为集合A的正闭包。 A*＝ A0 ∪A＋ 称为集合A的闭包。 例：A={x,y} A＋＝？ {x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……}
=> the <形容词><名词><谓语> => the big <名词> <谓语> => the big elephant <谓语>
=> the big elephant <动词><宾语>
=> the big elephant ate <宾语> => the big elephant ate <冠词><名词>
编译原理
2013年11月17日
• 文法的直观概念：以汉语中的“我是大学生”为例。
①一组终结符号 采用BNF来表示汉语句子的构成规则为： （语言的基本符号） 〈句子〉：：=〈主语〉〈谓语〉 ②一组非终结符号 〈主语〉：：=〈代词〉|〈名词〉 （语法单位） ③一个开始符号 〈代词〉：：=我|你|他 文法的四部分 （一个特殊的非终结 〈名词〉：：=王明|大学生|工人|英语 符号，最感兴趣的语 〈谓语〉：：=〈动词〉〈直接宾语〉 法单位） 〈动词〉：：=是|学习 ④一组规则（也称产 生式或产生规则） 〈直接宾语〉：：=〈代词〉|〈名词〉 根据上述规则，“我是大学生”的构成符合上述规则，而“我 大学生是”不符合，我们说它不是句子。这些规则成为我们判别 句子结构合法与否的依据。换句话说，这些规则看成是一种元语 言，用它描述汉语。这种的语言描述成为文法。
编译原理
2013年11月17日
<句子>::=<主语><谓语> <主语>::=<冠词><形容词><名词> <冠词> ::=the <形容词>::=big <谓语>::=<动词><宾语> <动词>::=ate <宾语>::=<冠词><名词>
<句子> => <主语><谓语>
=> <冠词><形容词><名词><谓语> <名词>::=elephant | peanut
例：有一英语句子：The big elephant ate the peanut.
<句子>::=<主语><谓语>
<主语>::=<冠词><形容词><名词> <冠词> ::=the
<形容词>::=big
<名词>::=elephant <谓语>::=<动词><宾语>
<动词>::=ate
<宾语>::=<冠词><名词> <名词> ::=peanut
编译原理
2013年11月17日
符号串的前缀和后缀: 从符号串s的尾部删去若干个(包括0个)符号之后所余下的 部分称为s的前缀
ε，0，01及011都是符号串011的前缀
ε，1，11及011都是符号串011的后缀
符号串集合：若集合A中的一切元素都是某字母表上的符号 串，则称A为该字母表上的符号串集合。 例：={a，b，c} A={ a,aa,ac}
编译原理
2013年11月17日
2.2
文法和语言的形式定义
文法是对语言结构的定义与描述。（或称为“语法”）。
<赋值语句>::=<标识符>“=”<表达式> <表达式>::=<表达式>“+”<表达式> | <表达式>“*”<表达式> <表达式>::=“(”<表达式>“)” | <标识符> | <整数> | <实数>
A1 A A A2 A A3 A
{ε, A*＝ ？ 0x,y, 1 xx,xy,yx,yy , xxx,xxy,xyx,xyy, ……} 2 3
编译原理
2013年11月17日
Σ的闭包* 表示上的一切符号串（包括ε）组成的集合 Σ的正闭包+ 表示上的除ε外的所有符号串组成的集合
{ } ......
编译原理
2013年11月17日
符号串集合的乘积 设A、B为符号串集合，则A和B的乘积定义为： AB＝{ xy |x∈A,y∈B} 例如，A＝{a,b}，B={c,d} 则AB= {ac,ad,bc,bd}
编译原理
2013年11月17日
符号串集合的幂运算 有符号串集合A，定义A0 ={ε}, A1=A, A2=AA, A3=AAA,…… An＝An-1A=AAn-1 ，n>0 例如，A＝{0,1}，则 A0= {ε} A1= {0,1} A2= {00,01,10,11} A3= {000,001,010,011,100,101,110,111}
编译原理
2013年11月17日
2.1
字母表和符号串
不对 符号就是字符，对吗？ 如={if,else,for,while} 字母表：符号的非空有限集 例：={0，1} C语言的字母表 A＝{a,b,…,0,1,…,9, +,－,×,_/, ( , ), =… if, else,for...} 符号：字母表中的元素 例： 0，1 符号串：由字母表中的符号组成的任何有穷序列 例：0,1, 01, 10, 011，.. 空符号串：无任何符号的符号串，用ε 表示
编译原理
2013年11月17日
语言是由句子组成的集合，是由一组符号所构成的集合
字母表上的一个语言是上的一些符号串的集合 字母表上的每个语言是*的一个子集 例如：字母表 Σ ={a,b} ,Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,…}
集合{ab,aabb,aaabbb,…,anbn,…} 或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言 集合{a,aa,aaa,…} 或表示为{w|w∈Σ*且w=an,n≥1} 为 字母表上的一个语言
* 2
{ } ......
* * 2 3
例：Σ ={a,b} Σ *={ε ,a,b,aa,ab,ba,bb,aaa,aab,…} Σ +={a,b,aa,ab,ba,bb,aaa,aab,…}
编译原理
2013年11月17日
为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 若A为某语言的字母表 A＝{a,b,…,0,1,…,9, +,－,×,_/, ( , ), =… if, else,for...} B为单词集 B ={if, else,for,……,<标识符>,<常量>,……} 则B A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C B * , 程序 C
这种推导一直进行下去，直到所有带< >的符号都由终结符号 替代为止。
编译原理
2013年11月17日
推导方法：从一个要识别的符号 开始推导，即用相应规则的 右部来替代规则的左部， 每次仅用一条规则去进行推导。
<句子>::=<主语><谓语> <主语>::=<代词>|<名词> <代词> ::=你|我|他