Exe1-程序语言的基本知识

1•练习:–1.文法:Z→U0|V1U→Z1|1V→Z0|0(1)请写出全部由此文法描述的只含有四个符号的句子.(2)该文法是Chomsky几型文法?2–1.文法:Z→U0|V1U→Z1|1V→Z0|0请写出全部由此文法描述的只含有四个符号的句子:0101,1010,1001,0110.该文法是Chomsky几型文法?3型文法3•2、给定前缀表示的表达式文法G:(1)E→-EE(2)E→-E(3)E→a(4)E→b(5)E→c试问--a-bc是否L(G)的句子?若是,请给出该句子所有可能的分析树;若不是,请说明理由.4E可能的分析树(1):-EE-EEca-Eb5E可能的分析树(2):-EE-E-EabcE6E可能的分析树(3):-E-EEca-EbE7•2.1P26S(L)(a,(a,a))aaSS,L(L)S,LaS最左推导：S(L)(L,S)(S,S)(a,S)(a,(L))(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a))lmlmlmlmlmlmlmlmlm最右推导：S(L)(L,S)(L,(L))(L,(L,S))(L,(L,a))(L,(S,a))(L,(a,a))(S,(a,a))(a,(a,a))rmrmrmrmrmrmrmrmrm8•2.2SbababSSabSaSεεSbSSaaSbSεεεε最左推导：SaSbSabSaSbSabaSbSababSabablmlmlmlmlm最左推导：SaSbSabSabaSbSababSabablmlmlmlmlm9•文法G:P→PaP|PbP|cP|Pe|f证明文法G是二义文法.**通过证明句型fbfbf存在两棵分析树.10PPbPPbPfffPPbPPbPfff最左推导：PPbPPbPbPfbPbPfbfbPfbfbflmlmlmlmlm最左推导：PPbPfbPfbPbPfbfbPfbfbflmlmlmlmlm11•练习:–1.文法:S→(L)|aL→L,S|S分析句型:(L,a,S)求：短语、直接短语、句柄、素短语、最左素短语12S–句型：(L,a,S)–短语：(L,a,S)、L,a,S、L,a、a–直接短语：a–句柄：a–素短语：a–最左素短语：a(L)L,SL,Sa13–2.文法:S→a│^│(T)T→T,S│S分析句型:(T,(^,a))求：短语、直接短语、句柄、素短语、最左素短语14S–句型：(T,(^,a))–短语：(T,(^,a))、^,aT,(^,a)、(^,a)、^、a–直接短语：^、a–句柄：^–素短语：^、a–最左素短语：^(T)T,S(T)aT,S^S