1、画出编译程序的总体结构图，简述其部分的主要功能。[答案]编译程序的总框图见下图。图编译程序的总体结构图其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号。语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语法上正确的“程序语句”。语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。优化器对中间代码进行优化处理。其过程实际上是对中间代码进行等价替换，使程序在执行时能更快，并占用更小的空间。目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能识别的语言，即目标程序，才能在机器上运行。表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格中，所需要的信息也大多从表格中，所需要的信息也大多从表格中获取，整个编译过程都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。编译程序的各个阶段都有可能发现错误，出错处理程序要对发现的错误进行处理、记录，并反映给用户。2.已知文法G：E->E+T|E-T|TT->T*F|T/F|FF->(E)|i试给出下述表达式的推导及分析树(1)i;(2)i*i+i(3)i+i*i(4)i+(i+i)[答案](1)E=>T=>F=>i(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)=>i+(i+T)=>i+(i+F)=>i+(i+i)3.文法G[S]为：S->Ac|aBA->abB->bc该文法是否为二义的？为什么？[答案]对于串abc(1)S=>Ac=>abc(2)S=>aB=>abc即存在两不同的最右推导所以，该文法是二义的。4.令文法G[E]为:E->E+T|E-TT->T*F|T/F|FF->(E)|I对于它的一个句型E+T*F，指出这个句型的所有短语、直接短语、句柄和素短语。[答案]此句型的短语有:E+T*F，T*F,直接短语为：T*F。句柄为：T*F素短语：T*F5.已知文法G[E]:E→ET+|TT→TF*|FF→F^|a试证：FF^^*是文法的句型，指出该句型的短语、直接短语、句柄和素短语.[答案]该句型对应的语法树如下：该句型的短语有FF^^*,F,F^,F^^；直接短语有F;F^；句柄为F；素短语为F^1.已知文法G[S]：S→dABA→aA∣aB→ε∣bB问：相应的正规式是什么？[答案]正规式是daa*b*2.请描述下面正规式定义的串.字母表S={0，1}.a)0*(10+)*0*b)(0|1)*(00|11)(0|1)*c)1(0|1)*0[答案]a)每个1至少有一个0跟在后边的串b)所有含两个相继的0或两个相继的1的串c)必须以1开头和0结尾的串3.写一文法，使其语言是偶正整数集合。要求：(1)不允许0开头；(2)允许0开头。[答案](1)不允许0开头的偶正整数集合的文法E→NT∣DT→FT∣GN→1∣2∣3∣4∣5∣6∣7∣8∣9F→0∣1∣2∣3∣4∣5∣6∣7∣8∣9D→2∣4∣6∣8G→0∣2∣4∣6∣8(2)允许0开头的偶正整数集合的文法E→NT∣G∣SFMT→NT∣GN→0∣1∣2∣3∣4∣5∣6∣7∣8∣9G→2∣4∣6∣8S→NS∣εF→1∣2∣3∣4∣5∣6∣7∣8∣9M→M0∣04.构造正规式1(0∣1)*101相应的DFA.[答案]10先构造NFA确定化:01XAAAABABACABACAABYABYACAB重新命名，令AB为B、AC为C、ABY为D01XAAABBCBCADDCBDFA：C5.将下图确定化：[答案]01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQUZZZZ重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。01SABACBBDECFFDFECEFFFDFA：最小化：01SABACBBDCDCCCC6.已知正规式：(1)((a∣b)*∣aa)*