第2章 语言分析基础(1)

1第二章语言分析基础2语言分析基础文法和语言概述字母表和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析有关文法实用中的说明3让计算机熟悉和掌握源语言和目标语言编译程序研究如何将源语言程序翻译为目标语言程序。源程序目标程序编译程序2.1文法和语言概述4源程序目标程序编译程序2.1文法和语言概述让计算机掌握语言的语法和语义编译程序研究如何将源语言程序翻译为目标语言程序。5文法是对语法进行形式化描述的工具源程序目标程序编译程序2.1文法和语言概述对语法和语义进行形式化描述编译程序研究如何将源语言程序翻译为目标语言程序。6文法的直观概念语言是由句子组成的集合，是由一组符号所构成的集合。自然语言语言句子的集合句子多个单词按一定规则组成单词多个字符按一定规则组成程序语言编程语言程序的集合程序多个单词按语法规则组成单词多个字符按词法规则组成2.1文法和语言概述72.1文法和语言概述语言的描述穷举：如，L={Iamateacher,Youarestudents}文法：制定有限条规则，用来产生所要描述的语言中全部句子的集合。例：“我是大学生”是否是汉语的一个句子？〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉如何定义句子的合法性?•有穷语言：只需逐一列举句子•无穷语言：使用文法定义句子结构，用适当条数的规则把语言的全部句子描述出来。文法是以有穷集合刻划无穷的集合的工具。8如何定义句子的合法性？•有穷语言：只需逐一列举句子•无穷语言：使用文法定义句子结构，用适当条数的规则把语言的全部句子描述出来。文法是以有穷集合刻划无穷的集合的工具。92.1文法和语言概述〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生“我是大学生”是汉语的一个句子。有穷非空的规则的集合就称为文法。这些规则看成是一种元语言，用它描述汉语。文法是程序语言的产生系统“大学生是”？？“我学习大学生”？？×√〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉｜〈名词〉〈代词〉∷=我｜你｜他〈名词〉∷=王明｜大学生｜工人｜英语〈谓语〉∷=〈动词〉〈直接宾语〉|〈动词〉〈动词〉∷=是｜学习〈直接宾语〉∷=〈代词〉｜〈名词〉102.1文法和语言概述规则集句子::=主语谓语状语主语::=名词谓语::=动词状语::=介词名词名词::=Peter|river动词::=swims介词::=in产生的语言{Peterswimsinriver,Riverswimsinriver,PeterswimsinPeter,RiverswimsinPeter}产生语言的规则示例112.1文法和语言概述一个程序设计语言是一个记号系统。程序设计语言研究的三个方面–语法（Syntax）：各记号之间的组合规律。–语义（Semantics）：各记号的特定含义。–语用（Pragmatics）：各记号的来源、使用和影响。例：对于赋值语句x:=a+b*c的非形式描述是：语法：赋值语句=变量+:=+表达式语义：先求右部，然后把结果给左部变量语用：赋值语句可用来计算和保存表达式的值12形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法。形式语言：一种不考虑含义的符号语言。形式语言抽象地定义为一个数学系统。形式语言是程序设计语言语法分析研究的基础。2.1文法和语言概述13字母表：符号的非空有限集例：={0，1}2.2字母表和符号串符号：字母表中的元素。例：0，1符号串：由字母表中的符号组成的任何有穷序列例：0,1,01,10,011，...空符号串：无任何符号的符号串，用ε表示符号串的长度：符号串S中符号的个数,记为|S|。C语言的字母表：A＝{a,b,…,0,1,…,9,+,－,×,/,(,),=，…，if,else,for，...}不对，={if,else,for,while}符号就是字符，对吗？14从符号串s的尾部删去若干个(包括0个)符号之后所余下的部分称为s的前缀；从符号串s的前部删去若干个(包括0个)符号之后所余下的部分称为s的后缀。ε，0，01及011都是符号串011的前缀ε，1，11及011都是符号串011的后缀符号串集合：若集合A中的一切元素都是某字母表上的符号串，则称A为该字母表上的符号串集合。例：={a，b，c}A={a,aa,ac}符号串的前缀和后缀2.1字母表和符号串15符号串x和y的连接:是把y的符号写在x的符号之后得到的符号串xy对于任意一个符号串s，有εs=sε=s符号串的连接运算符号串的运算2.1字母表和符号串例如：x=00，y=11，则xy=？001116符号串自身连接n次得到的符号串sn定义为ss…ss，包括n个s，称为符号串的幂运算。s0=ε，s1=s，s2=ss，……设：s=01，则：s0=？s1=？s2=？……符号串的幂运算2.1字母表和符号串ε01010117设A、B为符号串集合，则A和B的乘积定义为：AB＝{xy|x∈A,y∈B}例如，A＝{a,b}，B={c,d}则AB=？符号串集合的乘积2.1字母表和符号串{ac,ad,bc,bd}18有符号串集合A，定义A0={ε},A1=A,A2=AA,A3=AAA,……An＝An-1A=AAn-1，n0例如：A＝{0,1}，则：A0=？A1=？A2=？A3=？符号串集合的幂运算2.1字母表和符号串{ε}{0,1}{00,01,10,11}{000,001,010,011,100,101,110,111}19设A是符号串集合，定义：A＋＝A1∪A2∪A3∪……∪An∪……称为集合A的正闭包。A*＝A0∪A＋称为集合A的闭包。例：A={x,y}A＋＝？A*=？{x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A1A2A3{ε,x,y,xx,xy,yx,yy,xxx,xxy,xyx,xyy,……}A0A1A2A3符号串集合的闭包运算2.1字母表和符号串20Σ的闭包*:表示上的一切符号串（包括ε）组成的集合Σ的正闭包+:表示上的除ε外的所有符号串组成的集合例：Σ={a,b}Σ*=？Σ+=？......}{2*......}{32**2.1字母表和符号串{ε,a,b,aa,ab,ba,bb,aaa,aab,…}{a,b,aa,ab,ba,bb,aaa,aab,…}21若：A为某语言的字母表A＝{a,b,…,0,1,…,9,+,－,×,_/,(,),=…if,else,for...}B为单词集B={if,else,for,……,标识符,常量,……}则：BA*。语言的句子是定义在B上的符号串。若令C为句子集合，则CB*,程序C为什么对符号、符号串、符号串集合以及它们的运算感兴趣？2.1字母表和符号串22例：字母表Σ={a,b}，则字母表上的语言有：(1)Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}(2)集合{ab,aabb,aaabbb,…,anbn,…}或表示为{w|w∈Σ*且w=anbn,n≥1}。(3)集合{a,aa,aaa,…}或表示为{w|w∈Σ*且w=an,n≥1}(4)ε是一个语言。(5)即是一个语言。语言是由句子组成的集合，是由一组符号所构成的集合。换言之,字母表上的一个语言是上的一些符号串的集合(字母表上的每个语言是*的一个子集)。(列举法)(命题法)2.1字母表和符号串