搜索
alphabet字母表symbol符号string串length长度catenation连接power方幂gather集合product乘积emptyset空集closure闭包program程序logicstructure逻辑结构generating产生executing执行machinelanguage机器语言instruction指令function函数assembler汇编程序interpreter解释程序translator翻译程序sourcelanguage源语言finite有穷的sourceprogram源程序targetlanguage目标语言attribute属性possess占有preprocess预处理compiler编译程序break中断Intermediatelanguage中间语言definition定义reconstructed重构normal正规charactersequences符号序列programminglanguage程序设计语言operand操作数instead替换memory内存element元素high-levellanguage高级语言objectprogram目标程序address地址input输入output输出terminal终结符compilation编辑equivalence等价nonterminal非终结符recursion递归deterministic确定的nondeterministic非确定的Backus-NormalForm巴科斯范式syntax语法tree树expression表达式grammar文法automata自动机prefix前缀suffix后缀infix中缀identify识别identifier标识符analyses分析predigest化简symbolset符号集performed执行forecast预测state状态formula产生式conversion变换precedence优先simple简单handle句柄operator算符terminalstate终态firststate初态optimizer优化程序concatenation连接word单词alphabet字母表lexical词法scanner扫描器analyzer分析器syntaxtree语法树symboltable符号表pass趟，遍regularexpression正规表达式codegenerator代码生成器backdate回溯derivation推导educe推导derivationtree推导树path路径ambiguous二义性simplephrase简单短语context-sensitive上下文有关context-free上下文无关right-linear右线形phrase-structured短语结构regulargrammar文法directderivation直接推导sentence句子sententialform句型rootnode根结点subtree子树semantic语义的terminalnode端末结点attributegrammar属性文法canonicalderivation规范推导top-down自上而下bottom-up自下而上viableprefix活前缀nondeterminatefiniteautomata非确定的有穷自动机总复习一、基本概念：1、请简单解释编译程序的概念。答：编译程序是现代计算机系统的基本组成部分之一。简而言之,编译程序就是一种语言翻译程序。所谓翻译程序，是指这样一个程序，它能将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序。编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理程序和出错处理程序等成分构成。2、请解释编译程序的前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？(10分)答：编译程序的前端只依赖于源语言，由几乎独立于目标机器的阶段或阶段的一部分组成。编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。编译程序的后端是指编译器中依赖于目标机器的部分,它们一般独立于源语言，而与中间代码有关。通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。3、语言的语法描述方法有其三，请列举出来。答：用自然语言描述语言的语法，用语法图描述语言的语法和用巴科斯-瑙尔范式及扩充的巴科斯-瑙尔范式(EBNF)两种形式给出语言的语法描述。答：根据Chomcky文法的定义，该文法是2类文法，即上下文无关文法。4、请写出Chomcky关于文法的定义。答：Chomcky文法的定义：文法G定义为四元组,记为:G=(VN,VT,P,S)其中：VN—非空有限的非终结符号集VT—非空有限的终结符号集P—产生式集S—开始符号/识别符号5、已知文法：（20分）E→X|E+XX→Y|X*YY→（E）|i请判定该文法是那类文法？5、简单说明词法分析程序的主要任务。答：词法分析程序是编译程序的一个构成成分，它的主要任务是扫描源程序，按构词规则识别单词，并报告发现的词法错误。6、请简单介绍确定的有穷自动机。答：确定的有穷自动机也称有限自动机，它是作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。具体而言，一个确定的有穷自动机可以用一个五元组表示，即M=(K,Σ,f,S,Z)。K是一个有穷状态集，Σ是一个有穷字母表，f是转换函数，S是初态，Z是一个终态集。7、简单说明语法分析程序。答：语法分析程序是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序)，目前语法分析常用的方法有自顶向下（自上而下）分析和自底向上（自下而上）分析两大类。8、请说明有关句型、句子、句柄概念？（10分）答：设G[S]是一文法，如果符号串x是从文法的识别符号推导出来的，则称符号串x是文法G[S]的句型。若符号串x还满足仅由终结符号组成的条件，则称x为G[S]的句子。一个句型的最左直接短语称为该句型的句柄。9、请说明有关规范句型的概念？答：最右推导，即推导的每一步都是替换当前句型最右边的非终结符，被称为规范推导，由规范推导得到的句型称为规范句型。10、请说明有关预测符号集的概念？答：产生式A→α预测符号集表示：在确定的自上而下的语法分析过程中，当需要替换的非终结符是A时，而当前需要匹配的终结符属于产生式A→α预测符号集中的符号，则能够采用该产生式进行推导。当α不能推出ε时，产生式A→α预测符号集是α的首符号集；当α能推出ε时，产生式A→α预测符号集是α的首符号集与A的后跟符号集的并集，但是不包括ε。11、简单说明LR分析器由那几部分组成？答：简单而言LR分析器由3部分组成，它们是：总控程序、分析表（ACTION表和GOTO表）和分析栈（符号栈和状态栈）。12、简单说明拓广文法、活前缀和可归前缀的概念？答：拓广文法：在原文法中增加一个产生式，Ｓ′→Ｓ，得到的新文法称之为原文法的拓广文法；活前缀：在规范句型中，不包括该句型句柄右边符号的前缀称之为活前缀；可归前缀：活前缀与句柄有3种关系，：活前缀不含句柄的任何符号；：活前缀含有句柄的部分符号；：活前缀包含句柄的全部符号。包含句柄的全部符号的活前缀称之为可归前缀。13、请简单说明编译中的语义处理。答：编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。14、编译程序所使用的中间代码经常见的有那几种形式？答：编译程序所使用的中间代码常见的有逆波兰记号、三元式、四元式和树形表示。15、简单说明代码优化的概念。答：所谓代码优化，实质上是对代码进行等价变换，使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。16、简单说明代码生成器的概念。答；代码生成器是把某种高级程序设计语言编写的程序经过语法、语义分析，或再经过优化后的中间代码作为输入，将其转换成特定机器的机器语言或汇编语言作为输出，这样的转换程序称为代码生成器。二、应用题（每题10分，共40分）1、文法G（S）的产生式为：S→aAS,A→SbA,A→aA,A→b,S→a,请写出该文法的非终结符号集、终结符号集及文法的开始符号，根据文法画出句型aSbSbaAa的语法树，并且指出该句型的短语、直接短语和句柄？答：该文法的非终结符号集是{S,A}、终结符号集是{a,b}及文法的开始符号是{S}句型aSbSbaAa的语法树为：该句型的短语为：aA,SbaA,SbSbaAa,aSbSbaAa,a直接短语为：aA,a句柄为：aA2、正规式为：b((ab)*|bb)ba，请根据所列正规式，画出对应的NFA的状态转换图，并且将NFA确定化，画出对应的DFA的状态转换图。答：（1）正规式为：b((ab)*|bb)ba对应的NFA的状态转换图如下：（2）利用转换矩阵将以上NFA确定化，转换矩阵如下：IIaIb{1}{2,3,4,7}{2,3,4,7}{5}{6,8}{5}{4,7}{6,8}{9}{7}{4,7}{5}{8}{7}{8}{8}{9}{9}（3）将状态重新编号，NFA确定化后，生成DFA状态转换矩阵如下：ab011232437542656677（4）DFA状态转换图如下：3、请根据文法G写出所有产生式的预测符号集，并且判定该文法是否是LL(1)文法，如果是，请画出对应的预测符号表。文法G(S)：S→aBAA→Ba|εB→bB|a答：（1）求出各个产生式的预测符号集：Select(S→aBA)={a}Select(A→Ba)={b,a}Select(A→ε)={#}Select(B→bB)={b}Select(B→a)={a}(2)由于Select(A→Ba)∩Select(A→ε)=ΦSelect(B→bB)∩Select(B→a)=Φ所以该文法是LL(1)文法。(3)该文法对应的LL(1)预测符号表如下：ab#S→aBAA→Ba→Ba→εB→a→bB4、写出下面所列的文法的拓广文法，并且找出该拓广文法所有的项目，请构造识别该文法所有活前缀的NFA。文法G(S)：S→SbBa|BB→a|ε答：（1）该文法的拓广文法是：S´→SS→SbBa|BB→a|ε(2)该拓广文法所有的项目为：(0)S´→.S①S´→S.②S→.SbBa③S→S.bBa④S→Sb.Ba⑤S→SbB.a⑥S→SbBa.⑦S→.B⑧S→B.⑨B→.a⑩B→a.⑾B→.(3)识别该文法所有活前缀的NFA如下：5、根据以下文法，直接写出该文法的拓广文法和所有项目，构造项目集规范族及识别该文法所有活前缀的DFA，由识别该文法所有活前缀的DFA，判定该文法是否是LR(0)文法，如果是请构造相应的LR（0）分析表，通过查找LR（0）分析表写出对于输入串ade#的分析过程。文法G(S)：①S→ABC②A→a③B→b④B→d⑤C→e答：（1）该文法的拓广文法是：S´→SS→ABCA→aB→bB→dC→e该文法的所有项目：共计14个S´→.SS´→S.S→.ABCS→A.BCS→AB.CS→ABC.A→.aA→a.B→.bB→b.B→.dB→d.C→.eC→e.（2）直接构造项目集规范族及识别该文法所有活前缀的DFA，如下图所示：从DFA可以看出项目集规范族中不存在移进与归约的冲突，也不存在归约与归约的冲突，所以可以判定该文法属于LR(0)文法(3)由DFA直接构造相应的LR（0）分析表如下：状态ACTIONGOTOabde#SABC0S5121ACC2S6S733S844r1r1r1r1r15