1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,编译原理练习,第1页,2,文法和语言,符号和符号串,文法类型,文法和语言形式化定义,句型分析,语法树,文法和语言二义性,上下文无关文法,文法定义,推导定义,语言定义,第三章,字母表和符号串,符号串运算,集合闭包运算,第2页,第三章,1,、作业,P48,第,5,题 写一文法，使其语言是偶正整数集合。要求：允许,0,打头。,思绪：,首先依据集合描述设计几个句子，然后从句子中找出规律（或共性），把它们性质用产生式表示出来。,提醒,：（,1,）,生成偶正数应不包含，若干个,0,。,（,2,）将偶正数分为两类：一类为允许
2、若干个,0,（,0,个数,=0,）后跟不以,0,开头偶正数；一类为允许若干个,0,后跟,2|4|6|8,偶正数（如,0002,，即不允许只含有若干,0,）。,2,、为只包含数字、,表示式，比如,9,2,5,等结构一个文法，使得,和,运算满足右结合，,运算优先级高于。,提醒：结合性和运算优先性能够依据语法树层次考虑。进而思索左递归产生式与运算符结合性关系。,3,、一个上下文无关文法生成句子,abbaa,推导树以下：,(1),给出串,abbaa,最左推导、最右推导。,(2),该文法终止符、非终止符、产生式集合,P,可能有哪些元素？,(3),找出该句子全部短语、直接短语、句柄。,提醒：知识点：语法树
3、结构，文法组成，短语等概念。,4,、给出生成下述语言三型文法：,a,n,b,m,c,k,|n,k=1,，,m0,提醒：（,1,）三型文法中产生式特点,（,2,）可参考,P49,第,16,题,第3页,第4页,第5页,第6页,第7页,词法分析,自动结构工具,正规集,正规式,有穷自动机（,NFA DFA),正规文法,第四章 知识结构,第8页,1,、已知正规式,b(ab)*,和,(ba)*b,(1),分别结构上述两个正规式对应,DFA,，,(2),将,(1),结构,DFA,最小化，,(3),利用,DFA,证实,b(ab)*=(ba)*b,(4),结构该语言正规文法。,提醒：,使用知识点：正规式,NFA,，,NFA,DFA,，,DFA,最小化，,DFA,正规文法。,由转化得到相同最小化,DFA,，进而证实两个正规式等价。,2,、,(1),由偶数个,0,和奇数个,1,组成全部,01,串。,（,2,）写出,由,0,和,1,个数都是偶数,01,串正规式。,提醒：见下页,PPT,第9页,第10页,第11页,12,参考课件 例,2,：接收,0,和,1,个数都是偶数字符串,DFA,3,1,2,0,1,1,1,1,0,0,0,0,开始,偶,0,偶,1,奇,0,奇,1,奇,0,偶,1,偶,0,奇,1,第12页,
浙ICP备2021020529号-1 | 浙B2-20240490 
