语法分析文法与推导课件.ppt

《语法分析文法与推导课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章语法分析3.1文法和语言3.2推导与语法树3.3自上而下分析方法3.4自下而上分析方法3.5LR分析法3.1文 法 和 语 言文法是程序语言的生成系统;自动机则是程序语言的识别系统用文法可以精确地定义一个语言，并依据该文法构造出识别这个语言的自动机。程序语言的词法可用正规文法描述;语法可用上下文无关文法描述;语义则要借助于上下文有关文法描述。文法文法通常表示成四元组G=(VT，VN，S，P)，其中：(1)VT为终结符号集，这是一个非空有限集，它的每个元素称为终结符号；(2)VN为非终结符集，它也是一个非空有限集

2、，其每个元素称为非终结符号，且有VT∩VN=Φ；(3)S为一文法开始符，是一个特殊的非终结符号，即S∈VN；(4)P是产生式的非空有限集，其中每个产生式(或称规则)是一序偶(α，β)，通常写作α→β或α::=β,α∈(VT∪VN)+且至少有一个非终结符，而β∈(VT∪VN)*例:产生标识符的文法。L:“字母”类非终结符,L→a∣b∣…∣z;D:“数字”类非终结符,D→0∣1∣…∣9;T:“字母或数字”类非终结符，则有：T→L∣D；S:“字母数字串”类，S→T∣ST；I:“标识符”，I→L∣LS；G=({a,b,…,z

3、,0,…,9},{I,S,T,L,D},I,P)P:I→L∣LSS→T∣STT→L∣DL→a∣b∣…∣zD→0∣1∣…∣9例3.2写一文法，使其语言是奇数集合，但不允许出现以0打头的奇数。最高位允许出现1～9，用非终结符B表示；中间部分可出现任意多位数字0～9，每一位用非终结符D表示；最低位只允许出现1、3、5、7、9等奇数，用A表示。由于中间部分可出现任意位，引入了一个非终结符M，它包括最高位和中间位部分。文法为：G=({0,1,…,9},{N,A,M,B,D},N,P)P:N→A∣MA/*一位数字│多位数字*/M

4、→B∣MD/*仅两位数字(无中间位)│多于两位数字*/A→1∣3∣5∣7∣9B→1∣2∣3∣4∣5∣6∣7∣8∣9D→0∣B推导和直接推导直接推导：v=αAβ，w=αγβ，并且A→γ是文法中的一个产生式，那么我们说v可以直接推导到w，或者w可以直接规约到v。记作v⇒w。其中α，β∈(VN∪VT)*推导：若v=α0⇒α1⇒α2⇒…⇒αn=w(n>0),则符号串w为符号串v的一个推导。记为：vW⇒+vW含义:v=w或⇒*vW⇒+例:G=({E},{i,+,*,(,)},P,E)P：EE+E

5、E*E

6、(E)

7、i表达式(i

8、)和(i+i)*i的推导：E(E)(i)EE*E(E)*E(E+E)*E(i+E)*E(i+i)*E(i+i)*iEE0步推导E(i+i)*i6步推导E(i+i)*i6步推导E(E)直接推导句型、句子对于文法G[S]:如果：Sα，则α称为G的一个句型，开始符号是最简单的句型。如果：α是G[S]的一个句型,且αVT*，则α被称为G[S]的一个句子，也就是说句子是全部由终结符号组成的句型。⇒*文法的语言文法的语言：定义为：L(G[S])={α

9、Sα并且αVT*}一个文法的语言就是该文法的所有的句

10、子的集合。文法的语言是所有终结符号串所组成的集合的子集，一般是真子集。文法和语言有如下关系：给定一个文法,就能从结构上唯一的确定其语言,即:G→L(G)给定一种语言,能确定其文法,但不唯一，即:L→G1或G2或…。若文法G1和文法G2所产生的语言相同，即L(G1)=L(G2)，则称文法G1和文法G2等价。⇒+文法与语言举例描述语言L={ban

11、n>=1}的文法：G=({S,A},{a,b},S,P)P:S→bAA→aA

12、a文法G=({S,A,B},{a,b},S,P)P:S→ABA→aA

13、aB→bB

14、b描述的语言

15、是：L={anbm

16、m，n>=1}习题已知文法G[Z]=({Z},{a,b},Z,P)P:Z→aZb

17、ab求该文法确定的语言。已知语言为:L(G)={abna

18、n≥1}，构造产生该语言的文法。文法和语言的分类Chomsky对文法层次化划分，分为四类：0型:无约束文法1型:上下文有关文法2型:上下文无关文法3型:正规文法0型文法0型文法的产生式：α→β，α∈（VN∪VT）+且至少含一VNβ∈（VN∪VT）*相应语言称为0型语言，又称为递归可枚举集合。1型文法1型文法的产生式：γ1Aγ2→γ1δγ2，其中A∈VN，γ1,

19、γ2∈(VN∪VT)*δ∈(VN∪VT)+γ1,γ2为上下文1型文法也可以定义为：所有规则的右部都比左部长。2型文法2型文法的产生式：A→δ，其中A∈VN,δ∈（VN∪VT）*。2型文法又称为上下文无关文法。一般的程序设计语言的语法都使用2型文法描述。2型文法的例子：S→ab

20、aSb3型文法/RG文法产生式：（1）A→a或者A→aB（2）A→a