《编译原理实践及应用》第2章文法基础

《《编译原理实践及应用》第2章文法基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、形式语言基本知识第二章本章要求主要内容：符号串，文法的概念及分类，语言的定义过程重点掌握：上下文无关文法、推导、句型、句子、语言，语法树、二义性文法、文法的语言生成过程以C和PASCAL为例复习高级语言1语言的基本字符集的定义(字母,数字,界符)2单词集的定义3数据类型的定义4表达式的定义5语句的定义6程序定义PASCAL和C的主要区别2.1符号和符号串1.字母表：是元素的有穷非空集合Σ2.符号：字母表中的每个元素，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如英文的字母表中26个字母、数字及标点符号等。PASCAL语言的字母表是由字母、数字

2、、若干专用符号组成。符号是该语言能识别的符号，字母表是该语言能识别的所有符号的全体（字符集）。基本概念(续)3.符号串:由字母表中的符号组成的任何有穷序列称为符号串，例如001110是字母表=｛0，1｝上的符号串.字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca等。在符号串中，符号的顺序是很重要的，符号串ab就不同于ba,abca和aabc也不同。符号串STR表示“由符号S、T和R，并按此顺序组成.基本概念(续)4.符号串的运算a.字符串的连接：字符串αβ称为字符串α和β的连接符号串的长度:符号串中符号的个数，例如:某符号串中有m个

3、符号,则称其长度为m，表示为｜x｜=m，如001110的长度是6。空符号串:即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。用Σ*表示Σ上所有的符号串的全体(长度为0，1，2，…)。集合的运算b.Σ*的子集U、V的积：UV={αβ

4、α∈U&β∈V}长度相加即:集合UV中的符号串是由U和V的符号串连接而成。U={aa,bb}V={00,11}则UV=?c.集合的方幂：n个相同符号连接Vn=VVVV….V规定V0={ε}d.闭包、正闭包的运算例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,

5、ab,ba,bb,aaa,aab,…}使用*表示上的一切符号串（包括ε）组成的集合。称为Σ的闭包。上的除ε外的所有符号串组成的集合记为+。称为Σ的正闭包。......32SSS=S+V={0,1}V*=?V+=?......32SSS={ε}S*2.2上下文无关文法及其语言文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合文法是被用来精确而无歧义地描述语言的句子的构成方式.文法描述语言的时候不考虑语言的含义。引例例1：有如下规则<句子><主语><谓语>(表示由…组成)<主语>

6、<代词>

7、<名词><代词>我<名词>大学生<谓语><动词><直接宾语><动词>是<直接宾语><代词>

8、<名词>现要求根据如上规则得出句子：我是大学生<句子>=><主语><谓语> =><代词><谓语>=><代词><动词><直接宾语>=><代词><动词><名词>=>我是大学生句子“我是大学生”也可以如下图示分析在有规则的情况下，每一次用上述规则的右边去替换左边，得到“我是大学生”是符合上述规则的句子<句子><主语><谓语><代词><动词><直接宾语><名词>大学生我是上下文无关文法的形式定义由四部分组成：终结符号：是组成该语言的最基本的符号，是不可

9、再分的基本符号,如保留字、标识符等。非终结符号：规则中用尖括号括起来的符号，表示一些语法成分，可以推导出其他的语法成分,表示一定符号串的集合，是一个类，如表达式。开始符号：规则中的一个特殊的非终结符号，语言中的句子都从它开始推导,如程序、句子产生式：定义语法成分的规则，其中：文法的形式定义(续)一个文法G抽象地表示为四元组G=（Vn,Vt,P,S）其中Vn表示非终结符号Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φS是开始符号，P是产生式，形如：αβ(α∈V+且至少含有一个非终结符号，β∈V*)上例中：G=（Vn,Vt,P,<句子>）Vn=

10、（<句子>，<主语>，<谓语>，<代词>，<动词>，<名词>，<直接宾语>）Vt=(我，是，大学生)P=<句子><主语><谓语><主语><代词>

11、<名词><代词>我<名词>大学生<谓语><动词><直接宾语><动词>是<直接宾语><代词>

12、<名词>产生式的形式为：Aα左部符号，非终结符右部，可以含有非终结符和终结符又称为一条规则有时一个产生式不足以描述该语法范畴，就用多个产生式，如算术表达式的描述为：(递归定义)EE+EEE*EEi相同左部的一个右部又称一个候选式上下文无关文法所定义的语法成分独立于它可能出现的环境，即不考虑上下文。算

13、术表达式的文法定义变量是表达式表达式+表达式是表达式表达式*表达式是表达式(表达