大连理工大学--编译原理复习

编译术技命指题导意 见学教容 A内 识点及知型 题()1编译的阶划分段[ 择题 选2 分 ]1] 编译程[序绝大数时间花多( )上在。 .A出 错理 处B .法分析词C .目标码代成生 .D 符号表理 管答：D案[2 ]() 和 码代化部优不是分个每编程译都序必的。 A. 需语法分 析B. 中间代生成码C. 词 分法 析D.代码 生 答案：成B [] 编3程序前译三个段阶成完的工作是 )( 。.A词法 析、语法分分和析码代优化B . 代生成、码代优码和词化法分析C . 法分析、词法语分和语义析分 析. D词法析、语分法分析代码生和 答案成C :()2的遍念 概填[题 空2分 ][1] 编译 阶段的动常用一活扫遍来实现描一遍扫，描包 答案：括读个输一入文件写 个输一文件 出[2]将 译程编分成若干序 个 是为了__遍______

。第一 编章译概述器

和。

答案：程使的序结更构加晰 清[3] 译器编逻辑从可以分为上 个7段，阶其中， 可以 为一作后端遍个是_的__________阶段。答案： 代生码成 3()端前和端的划后 分简答[题 5分] [ ]1什么 是前端 [5 分？] 案：答译编器成分析分综和合大部两分分。析分部示源程揭序的基元素本和它所们成的 形层结次构，决它定的含们义建，起源程立序的中间表示，分部析分常经被称前端为。 2] [么是什端？ [5 分]后 答案：编译分成器分和综析两大部分。综合部合分从源序的程间表中示立建起和源程序 等的价标程目，序它经被称为后常。 [3]端什么 前是端？什么后端是？ [5分] 案答编译：分器成分析和综两大合分。分部析部揭示分程源的基序本素和元们它所形的 层次成结，决构定们的它含义，建立源起程序的中间表示分，部析分经常称被为前端综合 。部分源从程序的间中示建表立起源和程序等的目标价程，它序经被常为称后端 B。( 1词)分析法器的能功 [选题 择 2] 分[]1词法分 析序程输出结的是(果) 。 A. 单的种词编码别 B. 单词在符表中的号置 位C.单 词的别编种码和单属性词值D . 词的单词单属值 性答：案 C[2] 法分析器用于识别__词__。 _A .字符串 B语.句

第章二 .1 2.2 2法记词的号定及义描述

C.单词 D.标符 答案识C :3][扫 器描所成的任务完是从字串形式的源符序中识别出程个一具有个立独含义最的语小 法单位即 ()。 A. 符 字B单. 词C.子 句D句型. 案：答B 2(词法)号概念记及性 [填属题空 分2 []1 ]法词记号由 是 构成和的二元组 。案：答记号 属名性值[ 2 ]词法单元是程序源中匹一配 的个符序字。 列案答记：模号式 []3 影语法分析的决策响，影 记响的翻号译 答案。:号名记属性 (3正规式与语言的)对应关系 [择题 2 分选 ]1[] 下面法(文 和)正表达规式a* b描

述的语相言同。 A.S→ ab| aS b B S.→ b|a SC. S→a |aS b. SDa→| b 答S:案B[ ] 最多2包含两个a 的a,{}b上语言的( ) 。 . (A|εab*)(|εa ). B*abb*b*|b*aa*b

.C *b(|a*)b(ab*)|*bD .b (a*ε|)*b(|b*a)b 答*案D:[3 ](与ab)|*价的正等式是( 规)。 .A(a *b|*)* . (aB|)b C.+ (b)a* D. *|a* b答：案 C A(1)NA F与 DAF的概 念选择题 2[ ]分[1 ]有图如所示有的穷自机动，之等价与正的规为式 ( 。) A. (|1)*00(0|1101)0|(1)B. ( |0)1(00 0|11)1(|0) 1C .(|01)(*00|011)10(1) | D.*A,B C,选 项都正确 不答案：C[ ]2对于 NAF 和DF 模A说型法错的误是( ) 。A. DA 是FNFA 的特殊形式 B. D F 与 NFA A的状转态完换相同全 .C 有唯一的都开始状 D态. 都可以有多接个受态状答 ：B 案3] 对[于 FDA 型模，说法错误是( ) 。 的.A FAD 从何状态出任，发对任于输入符号何可有多，个换转B .任 何态状都有ε转换 C.没D A F唯一的有始状态开

二第章2 .31,..232. FN,AFAD

D. DFA可以 有个接受状态多答案 ：A( 2N)AF 的构 [简答造题 0 1分] 1] 设有非[定的有确限动机 N自AF =M(A,{B,}C,0{1}, ,,{A}{C,},)其中 ： ( ,A0){C=} A,1)({A,B=} (B ,)1=C{} (C1,)={C。}请出画态转换状距阵 状和转换态。 答图：案状 态换距转阵：为 A B C状转换图态为：0 C 1 A, BC C1

A1B 11 C1

0

[]2 构正规造相应的 式FN A 1(:|0)*111。0 案：答

3[] 为 (ε(|ab))* 构*非造确的定有自动机限给出，们它理处输入 串babbab a的换序 转列 。案：答输串入 abbbab a转的换序列 0 :156479 845167 7898 1564789 0 1者 或 01457896 415689 72137689 415769 108(3)NFA 化为 D转F [A答题简1 0]分 [] 1设={ 01,}上正的集 规 由倒数第S二字符为个1 的 有字符所组串，请成给该字出对 集应的规正式并，造构一个识别该规正集的DF 。A答案 构造相：应的规式正(0|1)*1:(01|)N AF:

确定化：I { 01,2} {,,2} 1{,12,3 {}12,,4}{1,2,3, 4}I0{,1} 21,{2 {1},,2}4{1 ,}2{1 2,4,

I1}{12,,3 }{,123}, 1,2{,,4}3 {12,3,} {12,3,4},、

[ 2 构]正造规 1(0|式)*101 相应1 的DA。 F案：先答造构NFA:

定化确：重新命,名 令A 为 B、BCA为 CAB、Y 为 D得

所：,以可 得DA 为：F[3] 对于图下示 所FAN,答回列下问：题

()用1正式规述该有描限自动所机示表的语。 言(2由 N)A F转为D FA。(3 构)最简造DF 。A 答案：( )(a|1)ba*(ab|* )2)(3)((4)DAF 化简 [的答题简10 分][1]

知 已NFA = (x,y{z,},0,1{},,{Mx}{z,} ),中： M其x,0(=){}z, (y,M)0{=xy,} M(,z0)=,{x,z, }Mx(1,)=x{},M y,1() φ ,=M(,z1=){}, y 造相应构 的FA D并小化最 答案：根据题。意有 FA N:图下表由集法将子 NFA 换为转 DF:A面将 该FA D最化小：

1) 首先(将的它态集分成状两子集个：1P{A=,DE},,P2{B=C,F,}( )2 区分P : 由于2 (FF,)1=F(C1),=,F

E(F0,)F= 且 F(并C,)=C0 ,所以 F C 等，价。由 F(B于,)=0F(C0,=C),F (B,)=1,D(C,F)1=,而 D,EE 等不价(见下步 ，)而 从B C与， 可以F区分。有 P21 =C{F,,}22=P{}B。( 3) 分区 P1:于由 ，A E入输 0 到终，而 D 输态入 不0到终，所态 D 以与 A,E可以 区分， P有1={1,E},P1A=2D{。}( ) 由4于F(A ,0=B),FE,0)=(,F B,而 F等不价，以所 A,E可 区分。以( ) 综5上述，DF所A可 区以分 P={为A{},{},BD{},{}E,{C,F}。所以最}化的 DFA 小如下 :[2]给 下列定动机：自此把自动转机为确换自动定机D AF。 案：答有状态矩 阵如：

图从可而 得DF 如图A

[3] (:1)下图中的将NF MA 确定化 DF为A ’M。 ( )将 2DF A’化M。简

a 0a

a b1

案： 答定确: a化 {0}{ }1 {0,} {1} b {10 -}-

-{0

1,} 状编态 0 2号 1

0,{1} a 0 1

11{ b} 2 --2 a->0-1 a b未简化的 FA 最D化：小分为： 终态集0,{}1非终 态{集2}{ ,01}a= {1}{0,1}b = {2} 所：{以,1}0 ={ 0} {2} ={1}2 a ba--

0>b

a1

D

(1)接直语言从构造DFA [简答题 5 分 ]1[ 写]能产生字出表{母,y}上的x含不两相个的邻x,且 含不个两邻相y的全体的符号串 的限有态状自动机。 答：x案 1 0y y 2x[] 2处/* 和于* /之间串的构成注解，注中间解没有/*画。出受接这种解注 的FDA的 状 转态换图 答案。:第章二 .4,225 .法词析器分的生成器 第;章二题习ohtre ssart 1 / 2 t *2* othrs e4* /5 [3 ]语言有 L={|w w∈ 0,1)+(并， 且w中 少至两个有1 ,又 在何任个 1 之间有偶两数 个 },试0构造接该受言语的定有限状态自确动。机答 ：案

2(L)x e的功能 [填空 题 2] [分1 Lex] 是从基于正规的描述式来构造 答案：法词分析 器[2] ex 程 …… 此处隐藏：3371字，全部文档内容请下载后查看。喜欢就下载吧 ……