编译原理温习_

  1、文法G（S）的发生式为：S→aAS,A→SbA,A→aA,A→b,S→a,请写出该文法的非完结符号集、完结符号集及文法的开始符号，依据文法画出句型aSbSbaAa的语法树，而且指出该句型的短语、直接短语和句柄？

  答：语法剖析程序是编译程序的中心部分。语法剖析的作用是辨认由词法剖析给出的单词符号序列是否是给定文法的正确语句(程序)，现在语法剖析常用的办法有自顶向下（自上而下）剖析和自底向上（自下而上）剖析两大类。

  答：设G[S]是一文法，长风万里符号串x是从文法的辨认符号推导出来的，则称符号串x是文法G[S]的句型。若符号串x还满意仅由完结符号组成的条件，则称x为G[S]的语句。一个句型的最左直接短语称为该句型的句柄。

  答：编译中的语义处理是指两个功用：榜首，检查每个语法结构的静态语义，即验证语法结构合法的程序是否真实有意义。有时把这个作业称为静态语义剖析或静态检查。第二，长风万里静态语义正确，语义处理则要履行真实的翻译，即，或许将源程序翻译成程序的一种中心表明方式（中心代码），或许将源程序翻译成方针代码。

  答：最右推导，即推导的每一步都是替换当时句型最右边的非完结符，被称为标准推导，由标准推导得到的句型称为标准句型。

  答：发生式A→α猜测符号集表明：在确认的自上而下的语法剖析进程中，当需求替换的非完结符是A时，而当时需求匹配的完结符唱腔发生式A→α猜测符号会集的符号，则可以选用该发生式进行推导。当α不能推出ε时，发生式A→α猜测符号集是α的首符号集；当α能推出ε时，发生式A→α猜测符号集是α的首符号集与A的后跟符号集的并集，可是不包含ε。

  3、请依据文法G写出一切发生式的猜测符号集，而且断定该文法是否是LL(1)文法，长风万里是，请画出对应的猜测符号表。

  答：（1）正规式为：b((ab)*bb)ba对应的NFA的状况转化图如下：

  答：词法剖析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规矩辨认单词，并报告发现的词法过错。

  答：编译程序所运用的中心代码常见的有逆波兰记号、三元式、四元式和树形表明。

  答：所谓代码优化，实质上是对代码进行等价改换，使得改换后的代码运转成果与改换前代码运转成果相同，而作业速度加大或占用存储空间少，或两者都有。

  4、写出下面所列的文法的拓广文法，而且找出该拓广文法一切的项目，请结构辨认该文法一切活前缀的NFA。

  从DFA可以精确的看出项目集标准族中不存在移进与归约的抵触，也不存在归约与归约的抵触，所以能断定该文法唱腔LR(0)文法

  答：确认的有穷自动机也称有限自动机，它是作为一种辨认设备，它能精确地辨认正规集，即辨认正规文法所界说的言语和正规式所表明的调集。详细而言，一个确认的有穷自动机可以用一个五元组表明，即M=(K,Σ,f, S,Z)。K是一个有穷状况集，Σ是一个有穷字母表，f是转化函数，S是初态，Z是一个终态集。

  5、依据以下文法，直接写出该文法的拓广文法和一切项目，结构项目集标准族及辨认该文法一切活前缀的DFA，由辨认该文法一切活前缀的DFA，断定该文法是否是LR(0)文法，长风万里是请结构相应的LR（0）剖析表，经过查找LR（0）剖析表写出关于输入串ade#的剖析进程。

  答：（1）该文法的拓广文法是：S´→S S→ABC A→a B→b B→d C→e

  答：该文法的非完结符号集是{S,A}、完结符号集是{a,b}及文法的开始符号是{S}

  2、正规式为：b((ab)*bb)ba，请依据所列正规式，画出对应的NFA的状况转化图，而且将NFA确认化，画出对应的DFA的状况转化图。

  答：用自然言语描绘言语的语法，用语法图描绘言语的语法和用巴科斯-瑙尔范式及扩大的巴科斯-瑙尔范式(EBNF)两种方式给出言语的语法描绘。

  答：简略而言LR剖析器由3部分所组成，它们是：总控程序、剖析表（ACTION表和GOTO表）和剖析栈（符号栈和状况栈）。

  答：拓广文法：在原文法中添加一个发生式，Ｓ′→Ｓ，得到的新文法称之为原文法的拓广文法；活前缀：在标准句型中，不包含该句型句柄右边符号的前缀称之为活前缀；可归前缀：活前缀与句柄有3种联系，：活前缀不含句柄的任何符号；：活前缀含有句柄的部分符号；：活前缀包含句柄的悉数符号。包含句柄的悉数符号的活前缀称之为可归前缀。

  答：编译程序是现代计算机体系的根本组成部分之一。简而言之,编译程序便是一种言语翻译程序。所谓翻译程序，是指这样一个程序，它能将高档程序设计言语程序翻译成逻辑上等价的低级言语(汇编言语,机器言语)程序。编译程序一般由词法剖析程序、语法剖析程序、语义剖析程序、中心代码生成程序、方针代码生成程序、代码优化程序、表格管理程序和犯错处理程序等成分构成。

  2、请解说编译程序的前端和后端的概念，试问前端一般包含那些阶段，后端包含那些阶段？(10分)

  答：编译程序的前端只依赖于源言语，由简直独立于方针机器的阶段或阶段的一部分组成。编译程序的前端一般包含词法剖析程序、语法剖析程序、语义剖析程序、中心代码生成程序及相关的表格管理程序和犯错处理程序。编译程序的后端是指编译器中依赖于方针机器的部分,它们一般独立于源言语，而与中心代码有关。一般包含方针代码生成程序、代码优化程序和相关的表格管理程序和犯错处理程序。