资源描述：
《编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 202编译程序构造与实践教程第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2.2.3文法和语言的分类1.Chomsky文法类与语言类对文法四要素概括与抽象。定义：Chomsky文法G=（VN,VT,P,Z)其中:VNVTPZ文法及例：L={aibjck
2、i,j,k≥1}G[S]:S::=Sc
3、BcB::=Bb
4、AbA::=Aa
5、aG'[S]:S::=ABCA::=Aa
6、aB::=Bb
7、bC::=Cc
8、cG1=(VN,VT,P1,S1)VN={S1,A,B}VT={a,b,c}P1:S1::=S1c
9、BcB::=Bb
10、AbA::=Aa
11、aL(G1)={aibjck
12、i,j,k≥1}G2=({S2,A},{a,b,c
13、},P2,S2)P2:S2::=S2c
14、AcA::=aAb
15、abL(G2)={aibick
16、i,k≥1}G3=({S3,B,C,D},{a,b,c},P3,S3)P3:S3::=abC
17、aS3BCCB::=CDCD::=BDBD::=BCbB::=bbbC::=bccC::=ccL(G3)={aibici
18、i≥1}G4=({S4,A,B,C,D,E},{a},P4,S4)P4:S4::=ACaBCa::=aaCCB::=DBCB::=EaD::=DaAD::=ACaE::=EaAE::=εL(G4)={a2i
19、i≥1}分类：按规则的定义形式
20、对Chomsky文法分类(1)0型文法（短语结构文法PSG）：u::=vu∈(VN∪VT)+,v∈(VN∪VT)*(2)1型文法（上下文有关文法CSG）：xUy::=xuyU∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+(3)2型文法（上下文无关文法CFG）：U::=uU∈VN,u∈(VN∪VT)+(4)3型文法（正则文法RG）：U::=VT或U::=TU,V∈VN,T∈VT相应地有4类Chomsky语言：0型语言（短语结构语言PSL）1型语言（上下文有关语言CSL）2型语言（上下文无关语言CFL）3型语言（正则语言RL）注意：a.
21、一般，程序设计语言都用上下文无关文法定义。b.2型文法规则U::=u中，u∈(VN∪VT)+有时对2型文法，扩充有ε规则与ε句子:ε规则：U::=εε句子：Z=>*ε因此，u∈(VN∪VT)*。例如，::=if(<表达式>)<语句>::=else<语句>::=ε2.Chomsky文法类与程序设计语言(1)程序设计语言一般用上下文无关文法定义：U::=u(2)但语言一般是上下文有关的a.<标号>::=<标识符><变量>::=<标识符>goto<标号>::=goto<标识符><标号>:
22、<语句>::=<标识符>:<语句>(标识符由所在上下文确定是否标号)b.<函数标识符>(<实在参数表>)<数组变量>[<下标表达式表>]<变量>=<表达式>(标识符由后跟符号确定是函数标识符、数组变量还是变量)(3)通常：词法分析，基于正则文法进行讨论语法分析，基于上下文无关文法进行讨论语义，则用口语描述。2.3句型分析2.3.1句型分析与语法分析树句型分析：关于某个文法，识别一个输入符号串是否其句子的过程称为句型分析。对于程序设计语言，句子是程序，句型分析的问题就是识别输入符号串是否是语法上正确无误的程序。为了有利于句型分析，引进一种辅助
23、工具语法分析树，简称语法树。语法分析树是句型分析的好工具。1.语法分析树借用英语等课程的语法分解图，引进语法分析树。语法分析树由边和结点组成。<句子>术语：结点<主语><复合谓语>根结点末端结点边<名词><系动词><表语>分支分支名字结点<冠词><形容词><名词>分支结点分支结点符号串Nanjingisabeautifulcity末端分支子树子树末端结点符号串树末端结点符号串注意：结点用小圆表示，但为简单起见，一般不画小圆。从该语法分析树可明显看出：Nanjing是名词作主语,is是系动词，与后面的表语构成复合谓语，等等。可写出 相应的文
24、法规则如下：<句子>::=<主语><复合谓语> <主语>::=<名词> <名词>::=Nanjing
25、Hangzhou
26、Beijing
27、city <复合谓语>::=<系动词><表语> <系动词>::=is
28、was <表语>::=<冠词><形容词><名词> <冠词>::=a
29、an
30、the <形容词>::=beautiful
31、great
32、wonderful2.从推导构造语法分析树句子Nanjingisabeautifulcity的推导：<句子>=><主语><复合谓语>=><名词><复合谓语>=>Nanjing<复合谓语>=>Nanjing<系动
33、词><表语>=>Nanjingis<表语>=>Nanjingis<冠词><形容词><名词>=>Nanjingisa<形容词><名词>=>Nanjingisabeautiful<名
