编译原理文法和语言与语法分析

《编译原理文法和语言与语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高级程序设计语言编译原理主讲周有顺(适用于2008级计算机本科师范专业)8/22/20211编译原理主讲：周有顺第四讲文法和语言与语法分析──上下文无关文法(LL文法和LR文法)与语法分析程序设计8/22/20212编译原理主讲：周有顺回忆语法分析的任务是把词法分析的结果单词符号串进一步分解成各类语法单位(语法范畴),并分析它们之间的层次关系输出语法树。语法分析器由单词符号(终结符)和语法范畴单词符号串──────→(语法变量或称非终结符)构成结点组成的语法树(词法分析)(创建)(语义分析的原始数据)

2、8/22/20213编译原理主讲：周有顺一、文法和形式语言的定义二、上下文无关文法及其语法树三、两种语法分析思想的形成四、自上而下的语法分析方法五、自下而上的语法分析方法*六、语法分析器的自动产生8/22/20214编译原理主讲：周有顺一、文法和形式语言的定义●回忆：程序语言的词法规则是可用表来描述的，而在词法分析器的讨论和自动产生中，词法是用正规式来描述定义的。●现在：程序语言的语法规则的定义和描述用什么呢？------文法！8/22/20215编译原理主讲：周有顺▲文法与语言●文法是描述语言语法结

3、构的一组形式规则。即是定义符号串（程序）集合（语言）的工具。它必须具备如下特点：①准确又易于理解；②由它定义形成的语言有利于句子分析和翻译；③通过它能自动产生有效的语法分析程序。8/22/20216编译原理主讲：周有顺▲文法与语言●(形式)语言：若Lㄈ∑*则称L是∑上的一个形式语言。其中,∑是基本符号集(有限集)，∑*是∑上基本符号串集(一般为无限集)，●例子：①C语言是基本符号字母表上符号串集的子集合，每个C程序都是基本符号字母表上的符号串，是C语言中的一个元素。②假定∑={a,b,c}则L1={a

4、,b,c},L2={a,aa,ab},L3={c,cc}可表示字母表∑上的三个不同的形式语言。这里描述语言的方法是用枚举法。③若∑={a,b}，∑上的一个形式语言为∑上所有可能的符号串集。即L={a,b,ab,ba,aa,bb,……},此时用枚举法已经无法表示该语言了。8/22/20217编译原理主讲：周有顺▲文法与语言●文法(形式)定义:我们用四元式来作为描述一个语言L的工具(会发生什么),用G表示。即G≡(Vt,Vn,P,S)其中:Vt是终结符集合(有限集)----单词符号集合即组成语言的不可再分

5、的基本符号。元素一般用小写英文字母表示。如常量、基本字等。Vn是非终结符集合(有限集)----用来表示语法范畴的语法变量。往往由它可以生成多个单词符号和其它非终结符等序列。元素一般用大写英文字母表示。如表达式、语句、分程序、过程等。Vn∩Vt=φS是文法开始符号∈Vn----特殊非终结符号，它必须至少在某个产生式左端出现一次。它代表所定义语言中我们最终感兴趣语法范畴。P是产生式(规则式)集合(有限集)----定义语法范畴的一种书写规则。形式：xAyxαyA∈Vn,x,y,α∈(Vt∪Vn)*某即关于

6、A的一条产生规则。8/22/20218编译原理主讲：周有顺▲文法与语言●例子：定义一个语法范畴，有时需要好几个产生式，有时还需要含有递归的产生式。如定义一个算术表达式的产生式如下：G:EiEE+EEE*EE(E)其中：i代表单词符号即变量或常数，另+、*、(、)也是单词符号。+可见，文法定义了一个语言。记为L(G)={α

7、S==>α,α∈Vt+},PVt={i,+,*,(,)}ㄈ∑,Vn={E}S=E∈VnP={左边列出的产生规则序列}E语言元素i+i的推导过程E+ES=E=>E+E=>E+i

8、=>i+iii语法单位：i(1),i(1),E(1),E(2),E+E,E8/22/20219编译原理主讲：周有顺●文法是定义语言的好工具：只要定义它含哪些语法范畴(Vn),每个语法范畴所含语法单位之间的关系(P),还有基本单词符号集(Vt)，最大的语法范畴是谁(S)。这四元一定，则文法就定义了一个语言----由S和P所能产生出的终结符串集。记为L(G)。即+L(G)={α

9、S====>α,α∈Vt*}P?假定∑={a,b},而∑上的一个形式语言L为∑上所有可能的非空符号串集，则该语言L用文法G怎样来

10、描述。答：G≡(Vt={a,b},Vn={A},S≡A,P={Aa,Ab,AAa,AAb})则，L=L(G)证：A=>a

11、b

12、Aa

13、Ab=>(a

14、b)

15、A(a

16、b)=>(a

17、b)(a

18、b)*8/22/202110编译原理主讲：周有顺▲文法性质类型与语言●一个文法G,若P中任一产生式形如Aα,有A∈Vn,α∈(Vn∪Vt)+(或α∈(Vn∪Vt)*),则G为(扩充)上下文无关文法。(2型)●一个文法G，若P中任一产生式形如AαB或Aα有A,B