当前位置:文档之家› 华南师范大学 编译原理期末复习整理 pdf例题

华南师范大学 编译原理期末复习整理 pdf例题

华南师范大学 编译原理期末复习整理 pdf例题
华南师范大学 编译原理期末复习整理 pdf例题

正则表达式:

例2.1 在仅由字母表中的3个字符组成的简单字母表∑={a, b, c}中,考虑在这个字母表上的仅包括一个b的所有串的集合。

( a | c )* b ( a | c )*

例2.2 在与上面相同的字母表中,如果集合是包括了最多一个b的所有串。

( a | c )* b? ( a | c )*

DFA:

例2.6 串中仅有一个b的集合的正则表达式对应的DFA为?

例2.8 科学表示法的数字常量的正则表达式为:

nat = [0-9]+

signedNat = (+|-)? nat

number = signedNat(“.” nat)? (E signedNat)?

如何画对应的DFA?

解:先设digit = [0-9],sig = (+|-),得:

例2.9 非嵌套注释的DFA描述。Pascal注释{ ( ~} )* }对应的DFA为:

C注释/* ...( */不同时出现)... */ 的DFA为:

NFA:

例2.12 根据Thompson方法将正则表达式ab|a转换为NFA。

例2.13 利用Thompson方法画出正则表达式letter(letter| digit)*对应的NFA。

例2.14 与正则表达式a*相对应的NFA为:

NFA转DFA:

例2.15 将下面的NFA转换为DFA:

解:

例2.16 将下面的NFA转换为DFA:

解:

例2.17 正则表达式letter(letter| digit)*对应的NFA转换成DFA:

解:

DFA最小化:

例2.18 将与正则表达式letter(letter| digit)*相对应的DFA最小化:(08级的大三第二学期考这道)

解:状态转换表为

letter digit {1} {2,3,4,5,7,10}

{2,3,4,5,7,10} {4,5,6,7,9,10} {4,5,7,8,9,10} {4,5,6,7,9,10} {4,5,6,7,9,10} {4,5,7,8,9,10} {4,5,7,8,9,10} {4,5,6,7,9,10} {4,5,7,8,9,10} 最小化DFA为:

例2.19 将下面与正则表达式(a| ε) b*对应的DFA进行最小化。

解:状态转换表为

a b

{1} {2} {3}

{2} {3}

{3} {3}

最小化DFA为:

词法分析代码:

state := 1; {start}

while state = 1 or 2 do

case state of

1: case input character of

letter: advance the input;

state := 2;

else state := ... {error or other};

end case;

2: case input character of

letter, digit: advance the input;

state := 2; {actually unnecessary} else state := 3;

end case;

end case;

end while;

if state = 3 then accept else error;

state := 1; {start}

while state = 1, 2, 3 or 4 do

case state of

1: case input character of

“/”: advance the input;

state := 2;

else state := ... ; {error or other}

end case;

2: case input character of

“*”: advance the input;

state := 3;

else state := ... ; {error or other}

end case;

3: case input character of

“*”: advance the input;

state := 4;

else advance the input; {and stay in state 3}

end case;

4: case input character of

“/”: advance the input;

state := 5;

“*”: advance the input; {and stay in state 4}

else advance the input;

state := 3;

end case;

end case;

end while;

if state = 5 then accept else error;

递归子程序分析法

问题1:

G[S] =

{

S →aA | bB

A →cdA | d

B →efB | f

}

试编写一个能分析该文法所对应任何串(如串acdd)的程序。

void match( expectedToken ){

if( token == expectedToken )

getToken();

else

Error();

}

void S(){

if( token == ‘a’ ){

match(‘a’);

A();

}else if( token == ‘b’ ){

match(‘b’);

B();

}else Error();

}//S

void A(){

if( token == ’c’ ){

match(‘c’);

match(‘d’);

A();

}else if( token == ‘d’ ){

match(‘d’);

}else Error();

}//A

void B(){

if( token == ‘e’ ){

match(‘e’);

match(‘f’);

B();

}else if( token == ‘f’ ){

match(‘f’);

}else Error(); }//B

int main(){

getToken();

S();

return 0;

}//main

问题2:

exp →exp addop term | term

addop →+ | -

term →term mulop factor | factor

mulop →* | /

factor →( exp ) | number

请写出递归子程序分析算法。

解:先消除左递归,得到

exp →term { addop term }

addop →+ | -

term →factor { mulop factor }

mulop →* | /

factor →( exp ) | number

程序如下:

void match( expectedToken ){

if( token == expectedToken )

getToken();

else

Error();

}

void exp(){

term();

while( token == ‘+’ || token == ‘-’ ){ match(token);

term();

}

}

void term(){

factor();

while( token == ‘*’ || token == ‘/’ ){ match(token);

factor();

}

}

void factor(){

if( token == ‘(’ ){

match(‘(’);

exp();

match(‘)’);

编译原理(清华大学第2版)课后习题答案

第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题

第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12.

短语: 直接短语: 句柄: 13.(1)最左推导:S => ABS => aBS =>aSBBS => aBBS => abBS => abbS => abbAa => abbaa 最右推导:S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) 文法:S → ABS S → Aa S →ε A → a B → b (3) 短语:a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语: a1 , b1 , b2, a2 , , 句柄:a1 14 (1) S → AB A → aAb | ε B → aBb | ε (2) S → 1S0 S → A A → 0A1 |ε 第四章 1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101 NFA (2) 1(1010*|1(010)*1)*0 NFA

最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)

编译原理考试题及答案汇总一、选择 1.将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2.正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3.中间代码生成时所依据的是 _C_。 A.语法规则 B.词法规则 C.语义规则 D.等价变换规则 4.后缀式 ab+cd+/可用表达式__B_来表示。 A. a+b/c+d B.(a+b)/(c+d) C. a+b/(c+d) D. a+b+c/d 6.一个编译程序中,不仅包含词法分析,_A____,中间代码生成,代码优化,目标代码生成等五个部分。 A.( ) 语法分析 B.( )文法分析 C.( )语言分析 D.( )解释分析 7.词法分析器用于识别__C___。 A.( ) 字符串 B.( )语句 C.( )单词 D.( )标识符 8.语法分析器则可以发现源程序中的___D__。 A.( ) 语义错误 B.( ) 语法和语义错误 C.( ) 错误并校正 D.( ) 语法错误 9.下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A.( ) (1)(2) B.( ) (1) C.( ) (1)(2)(3) D.( ) (2)(3) 10.解释程序处理语言时 , 大多数采用的是__B___方法。 A.( ) 源程序命令被逐个直接解释执行 B.( ) 先将源程序转化为中间代码 , 再解释执行 C.( ) 先将源程序解释转化为目标程序 , 再执行 D.( ) 以上方法都可以 11.编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A.( ) (2)(3) B.( ) (2)(3)(4)C.( ) (1)(2)(3) D.( ) (1)(2)(3)(4) 12.编译程序是一种___C__。 A. ( ) 汇编程序 B.( ) 翻译程序 C.( ) 解释程序 D.( ) 目标程序 13.文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B.( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C.( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14.文法分为四种类型,即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B.( ) 正则文法 C.( ) 上下文有关文法 D.( ) 上下文无关文法15.一个上下文无关文法 G 包括四个组成部分,它们是:一组非终结符号,一组终结符号,一个开始符号,以及一组 __D___。 A.( ) 句子 B.( ) 句型 C.( ) 单词 D.( ) 产生式

十天干类象详解汇总

十天干类象详解: 甲木 1 、滴天髓云: “甲木参天脱胎要火;水荡骑虎,火炽乘龙;地润天合,植立千古。”这几句已经说出了甲木的特性与喜忌,是我们推命时应掌握的一些通用原则 2、甲木为东方木,应震卦,震为雷,古人说甲木为雷,可以看到甲木气质轻清向上,快速积极,刚健的性质.甲木代表阳木,如森林,乔木,大树等.一棵健康的树木是离不开阳光的,也就是良好的光合作用来使其生长成材。 3、春天的甲木一般在雨水前需要丙丁火来驱除寒气,故甲木参天,脱胎要火,在雨水后,要庚金劈甲来引出丁火取贵。 4、夏天的甲木火旺木燥,地支须有水润,使木性不至于焚灭,干支生克则地润天合,植立千古.如果八字中火过多,须辰土来即火炽乘龙.为何是辰而不用丑?因辰为水库,其中乙木可以使甲木盘根,有癸水湿润,比丑土(己,辛,癸)要有效率的多,丑为金库,有损木力。 5、秋天的甲木凋零,一般以水印化官杀为用,另须木来帮助,地支最好有根基,即寅卯且不被冲合.如果是九月霜降后,还须适量的火来温暖。秋月金旺,以丁火制约庚辛为佳,反生之功效。 6、冬天的甲木寒冷,以火反生,即阳光普照则光合作用充分.如水过多漂木,则须寅木扎根,即水荡骑虎,寅木中有戊土止水,丙火温暖,甲木相助,甲、丙、戊联合运用,缺一不可,使寅木虎发挥最佳用神效果.其次可以用未土,未是燥木库,能纳水助甲,调节气温,也很不错。所以命中喜寅的人喜欢养猫,或者遇到属虎的朋友,上司帮助大,或者说缺寅的人带虎生肖饰品,家中挂幅虎画,熊猫画,养猫能改良命运。 7、命局如木火二行,成木火通明时,要看节气的深浅。要防灰飞烟灭之虞,故须看干 支水火体性,木火虽通明,也不可忽略甲木的本质,地润兼要火的认识须深入。 8、六壬中甲木主青龙,木将,主财宝、婚姻、喜庆、增福解祸,吉将。在人为辅弼、 大臣、司金铸之官、高雅端方之士、富户、媒妁、僧道。 在物为财宝、文字、重器、衣服、绢帛、羽毛、文彩、龙鱼、水族、虎豹、猫狸、林木、舟车、棺椁、枷棒、筵宴、酒食、果菜,於祟为木神、司命。 9、在《玉照定真经》中讲到“寅申庚甲,商路吏人”,甲(寅)木可以看做功曹,也就是看日元为庚还是甲,就能明确其从事职业特性了。这和六壬中甲木的形意是密切相关的。

编译原理_第三版_课后答案

编译 原理 课后题答案 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法: E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导:

E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树:/******************************** E E F T E + T F F T +i i i E E F T E -T F F T -i i i E E F T +T F F T i i i *i+i+i i-i-i i+i*i *****************/ P36-9 句子iiiei 有两个语法树: S iSeS iSei iiSei iiiei S iS iiSeS iiSei iiiei ???????? P36-10 /************** ) (|)(|S T T TS S →→ ***************/ P36-11 /*************** L1: ε ||cC C ab aAb A AC S →→→ L2:

编译原理复习题及答案

编译原理复习题及答案 一、选择题 1.一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2.文法G[A]:A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3.下面说法正确的是(A) A 一个SLR(1)文法一定也是LALR(1)文法 B 一个LR(1)文法一定也是LALR(1)文法 4.一个上下文无关文法消除了左递归,提取了左公共因子后是满足LL(1)文法的(A) A 必要条件 B 充分必要条件 5.下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6.算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7.一个LR(1)文法合并同心集后若不是LALR(1)文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8.下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9.下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10.编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11.(A)是一种典型的解释型语言。

A.BASIC B.C C.FORTRAN D.PASCAL 12.把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13.用高级语言编写的程序经编译后产生的程序叫(B) A.源程序 B.目标程序C.连接程序D.解释程序 14.(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15.通常一个编译程序中,不仅包含词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成等六个部分,还应包括(C)。 A.模拟执行器B.解释器 C.表格处理和出错处理D.符号执行器16.编译程序绝大多数时间花在(D)上。 A.出错处理B.词法分析C.目标代码生成D.表格管理 17.源程序是句子的集合,(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18.词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19.词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20.文法:G:S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21.如果文法G是无二义的,则它的任何句子α(A) A.最左推导和最右推导对应的语法树必定相同 B.最左推导和最右推导对应的语法树可能不同 C.最左推导和最右推导必定相同 D.可能存在两个不同的最左推导,但它们对应的语法树相同 22.正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23.(B)这样一些语言,它们能被确定的有穷自动机识别,但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24.给定文法A→bA | ca,为该文法句子的是(C) A. bba B. cab C. bca D. cba

编译原理课后习题答案(第三版)

精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法: E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树:/********************************

最新编译原理复习题(经典)

编译原理复习题 一、是非题 1.计算机高级语言翻译成低级语言只有解释一种方式。(×) 3.每个文法都能改写为 LL(1) 文法。 (×) 4.算符优先关系表不一定存在对应的优先函数。 (√) 5.LR分析方法是自顶向下语法分析方法。 (×) 6.“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。(× ) 7.一个句型的句柄一定是文法某产生式的右部。(√) 8.仅考虑一个基本块,不能确定一个赋值是否真是无用的。(√ ) 9.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(× ) 10.对于数据空间的存贮分配,FORTRAN采用动态贮存分配策略。(×) 11.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× ) 12.递归下降分析法是自顶向下分析方法。(√ ) 13.产生式是用于定义词法成分的一种书写规则。(×) 14.在SLR(1)分析法的名称中,S的含义是简单的。(√) 15.综合属性是用于“ 自上而下” 传递信息。(× ) 16.符号表中的信息栏中登记了每个名字的属性和特征等有关信息,如类型、种属、所占单元大小、地址等等。(×) 17.程序语言的语言处理程序是一种应用软件。(×) 18.解释程序适用于COBOL 和FORTRAN 语言。(×) 19.一个LL(l)文法一定是无二义的。(√) 20.正规文法产生的语言都可以用上下文无关文法来描述。(√) 21.一张转换图只包含有限个状态,其中有一个被认为是初态,最多只有一个终态。(×) 22.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题。(√) 22.逆波兰法表示的表达式亦称后缀式。(√ ) 23.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。(√ ) 24.数组元素的地址计算与数组的存储方式有关。(√) 25.算符优先关系表不一定存在对应的优先函数。(×) 26.编译程序是对高级语言程序的解释执行。(× ) 27.一个有限状态自动机中,有且仅有一个唯一的终态。(×) 28.一个算符优先文法可能不存在算符优先函数与之对应。(√ ) 29.语法分析时必须先消除文法中的左递归。(×) 30.LR分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点。(√) 31.逆波兰表示法表示表达式时无须使用括号。(√ ) 32.静态数组的存储空间可以在编译时确定。(√) 33.进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用。(√) 34.两个正规集相等的必要条件是他们对应的正规式等价。(√) 35.一个语义子程序描述了一个文法所对应的翻译工作。(×) 36.设r和s分别是正规式,则有L(r|s)=L(r)L(s)。(×) 37.确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 38.词法分析作为单独的一遍来处理较好。(× ) 39.构造LR分析器的任务就是产生LR分析表。(√) 40.规范归约和规范推导是互逆的两个过程。(√) 41.同心集的合并有可能产生新的“移进”/“归约”冲突。(× )

广东工业大学数据库原理与应用试卷答案

广东工业大学试卷用纸,共 页,第 页

广东工业大学试卷用纸,共页,第页

广东工业大学试卷用纸,共页,第页

一、填空(每题1分,共10分) 1、层次模型,网状模型,关系模型 2、逻辑结构设计,物理结构设计 3、原子性,持续性 4、并发调度的可串行性 5、闭包 6、描述事物的符号记录 二、选择题(每题2分,共20分) 三、简答题(每题4分,共16分) 1、解释数据库,数据库系统,数据库管理系统三个概念。 数据库是指长期存储于计算机内的、有组织的、可共享的数据集合。(1分) DBMS是指位于用户与OS之间的一层数据管理软件,它位用户或应用程序提供访问DB的方法。(1分) DBS是实现有组织的、动态的存储大量关联数据、方便多用户访问的计算机硬件、软件和数据资源组成的系统,即采用数据库技术的计算机系统。(2分) 2、试述视图和基本表之间的联系和区别? (1)视图和基本表在概念上等同,他们都是关系。(1分) (2)基本表是本身独立存在的表。视图是从一个或几个基本表(或视图)中导出的表,它与基本表不同,是一个 虚表。数据库中只存放视图的定义,而不存放视图对应的数据,这些数据仍然放在原来的基本表中。(3分) 3、数据库的完整性概念与数据库的安全性概念有什么区别和联系? 数据的完整性和安全性是两个不同的概念,但是有一定的联系。 前者是为了防止数据库中存在不符合语义的数据,防止错误信息的输入和输出,即所谓垃圾进垃圾出所造成的无效操作和错误结果。(2分) 后者是保护数据库防止恶意的破坏和非法的存取。也就是说,安全性措施的防范对象是非法用户和非法操作,完整性措施的防范对象是不合语义的数据。(2分) 4、什么是封锁?基本的封锁类型有几种,简要说明它们的含义。 封锁就是事务T在对某个数据对象(例如表、记录等)操作之前,先向系统发出请求,对其加锁。加锁后事务T就对该数据对象有了一定的控制,在事务T释放它的锁之前,其它的事务不能更新此数据对象。(2分)基本封锁类型:排它锁和共享锁。 排它锁又称为写锁:若事务T对数据对象A加上X锁,则只允许T读取和修改A,其它任何事务都不能再对A加任何类型的锁,直到T释放A上的锁(1分) 共享锁又称为读锁:若事务T对数据对象A加上S锁,则其它事务只能再对A加S锁,而不能加X锁,直到T 释放A 上的S锁。(1分) 四、计算(4分) 1、(R÷S)×S={(2,3,4,5),(2,7,2,3)} 2 广东工业大学试卷用纸,共页,第页

编译原理课后习题答案-清华大学-第二版

第1章引论 第1题 解释下列术语: (1)编译程序 (2)源程序 (3)目标程序 (4)编译程序的前端 (5)后端 (6)遍 答案: (1) 编译程序:如果源语言为高级语言,目标语言为某台计算机上的汇编语言或机器语言,则此翻译程序称为编译程序。 (2) 源程序:源语言编写的程序称为源程序。 (3) 目标程序:目标语言书写的程序称为目标程序。 (4) 编译程序的前端:它由这样一些阶段组成:这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段,某些优化工作也可在前端做,也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 (5) 后端:指那些依赖于目标机而一般不依赖源语言,只与中间代码有关的那些阶段,即目标代码生成,以及相关出错处理和符号表操作。 (6) 遍:是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成?各部分的主要功能是什么?并画出编译程序的总体结构图。 答案: 一个典型的编译程序通常包含8个组成部分,它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序:输人源程序,拼单词、检查单词和分析单词,输出单词的机内表达形式。 语法分析程序:检查源程序中存在的形式语法错误,输出错误处理信息。 语义分析程序:进行语义检查和分析语义信息,并把分析的结果保存到各类语义信息表中。

目标代码生成程序:将优化后的中间代码程序转换成目标代码程序。 表格管理程序:负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况,编译的每个阶段所需信息多数都从表格中读取,产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是,这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块,而是指编译程序具有的表格管理功能。 错误处理程序:处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时,错误处理程序负责报告出错的位置和错误性质等信息,同时对发现的错误进行适当的校正(修复),目的是使编译程序能够继续向下进行分析和处理。 注意:如果问编译程序有哪些主要构成成分,只要回答六部分就可以。如果搞不清楚,就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序?它们三者之间有何种关系? 答案: 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序,如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换(加工)成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种:一种方式是,源程序功能的实现完全由解释程序承担和完成,即每读出源程序的一条语句的第一个单词,则依据这个单词把控制转移到实现这条语句功能的程序部分,该部分负责完成这条语句的功

哈工大编译原理习题及答案

1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系? 1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么? 1.3选择一种你所熟悉的程序设计语言,试列出此语言中的全部关键字,并通过上机使用该语言以判明这些关键字是否为保留字。 1.4选取一种你所熟悉的语言,试对它进行分析,以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。 1.5试用你常用的一种高级语言编写一短小的程序,上机进行编译和运行,记录下操作步骤和输出信息,如果可能,请卸出中间代码和目标代码。 第一章习题解答 1.解:源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序(或解释程序)将 源程序处理加工而得的另一种语言(目标语言)的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序,但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码,而是每读入一条高级语言程序语句,就用解释程序将其翻译成一段机器指令并执行之,然后再读入下一条语句继续进行解释、执行,如此反复。即边解释边执行,翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序,将其保存到指定的空间中,在用户需要时再执行之。即先翻译、后执行。 2.解:一般说来,编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成 程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。 3.解:C语言的关键字有:auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。上述关键字在C语言中均为保留字。 4.解:C语言中括号有三种:{},[],()。其中,{}用于语句括号;[]用于数组;()用于函数(定 义与调用)及表达式运算(改变运算顺序)。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符,作为优先级最低的运算符,运算结果为逗号表达式最右侧子表达式的值(如:(a,b,c,d)的值为d)。 5.略 第二章前后文无关文法和语言 21设有字母表A1={a,b,…,z},A2={0,1,…,9},试回答下列问题: (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪A2)*中的全部长度不大于3的符号串。

广工编译原理(精选题集+必考大题

《编译原理》期末试题(二) 1、描述由正规式b*(abb*)*(a| ε)定义的语言,并画出接受该语言的最简DFA。 2、证明文法E → E + id | id是SLR(1)文法。 3、下面是表达式和赋值语句的文法,其中and的类型是bool ? bool → bool,+的类型是int ? int → int,=的类型是int ? int → bool,:= 要求id和E的类型都是int或者都是bool。为该文法写一个语法制导定义或翻译方案,它完成类型检查。 S →id := E E → E and E | E + E | E = E |id 6、描述由正规式b*a(bb*a)*b*定义的语言,并画出接受该语言的最简DFA。 7、下面的文法产生代表正二进制数的0和1的串集: B → B 0 | B 1 | 1 下面的翻译方案计算这种正二进制数的十进制值: B →B1 0 {B.va l := B1.val? 2 } | B1 1 {B.val := B1.val? 2 +1} | 1 {B.val := 1 } 请消除该基础文法的左递归,再重写一个翻译方案,它仍然计算这种正二进制数的十进制值。 编译原理试卷二答案 1、由正规式b*(abb*)*(a| ε)定义的语言是字母表{a, b}上不含子串aa的所有串的集合。最简DFA如下: 2、先给出接受该文法活前缀的DFA如下:

I0和I3都只有移进项目,肯定不会引起冲突;I2和I4都无移进项目并仅含一个归约项目,也肯定不会引起冲突;在I1中,E'的后继符号只有$,同第2个项目的展望符号“+”不一样,因此I1也肯定不会引起冲突。由此可以断定该文法是SLR(1)的。 3、语法制导定义如下。 S →id := E { S.type := if (id.type = bool and E.type = bool) or (id.type = int and E.type = int)then type_ok else type_error } E → E1and E2 { E.type := if E1.type = bool and E2.type = bool then bool else type_error } E → E1 + E2 { E.type := if E1.type = int and E2.type = int then int else type_error } E → E1 = E2{ E.type := if E1.type = int and E2.type = int then bool else type_error } E →id { E.type := lookup(id.entry) } 6、正规式b*a(bb*a)*b*体现的特点是,每个a的左边都有若干b,除非a是第一个字母。该正规式定义的语言是:至少含一个a,但不含子串aa的所有a和b的串集。最简DFA如下: 7、消除左递归后的文法: B → 1 B' B'→ 0 B' | 1 B' | ε 相应的翻译方案如下: B → 1 {B'.i := 1 }B'{B.val := B'.val} B'→ 0 {B'1.i := B'.i? 2 } B'1 {B'.val := B'1.val} | 1 {B'1.i := B'.i? 2 +1} B'1 {B'.val := B'1.val} | ε {B'.val := B'.i} 《编译原理》期末试题(三) 1、从优化的范围的角度,优化可以分哪两类?对循环的优化可以有哪三种?答:从优化的范围的角度,优化可以分为局部优化和全局优化两类; 对循环的优化有三种:循环不变表达式外提、归纳变量删除与计算强度削减。

编译原理教程课后习题答案——第四章

第四章语义分析和中间代码生成 4.1 完成下列选择题: (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表,便于优化处理 b. 节省存储空间,不便于表的修改 c. 便于优化处理,节省存储空间 d. 节省存储空间,不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示: S→bAb {print″1″} A→(B {print″2″} A→a {print″3″} B→Aa) {print″4″} 若输入序列为b(((aa)a)a)b,且采用自下而上的分析方法,则输出序列为。a. 32224441 b. 34242421 c. 12424243 d. 34442212 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”?试给出用语法制导翻译生成中间代码的要点,并用一简例予以说明。 【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序),并且在语法分析的同时执行这些子程序。也即在语法分析过程中,当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时,此产生式相应的语义子程序进入工作,完成既定的翻译任务。 用语法制导翻译(SDTS)生成中间代码的要点如下: (1) 按语法成分的实际处理顺序生成,即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理,如无条件跳转等。 例如下面的程序段: if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时,条件“i>0”为假的转移地址无法确定,而要等到处理“else”时方可确定,这时就存在一个地址返填问题。此外,按语义要求,当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时,则应转出当前的if语句,也即此时应加入一条无条件跳转指令,并且这个转移地址也需要待处理完else之后的语句后方可获得,就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d,其处理顺序(也即生成中间代码顺序)是先生成i+e的代码,再生成b*d的中间代码,最后才产生“-”运算的中间代码,这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值,例如对输入串101.101,则S.val= 5.625。按照语法制导翻译方法的思想,给出计算S.val的相应的语义规则,G(S)如下: G[S]: S→L.L|L

编译原理课后习题答案+清华大学出版社第二版

第 1 章引论 第1 题 解释下列术语: (1)编译程序 (2)源程序 (3)目标程序 (4)编译程序的前端 (5)后端 (6)遍 答案: (1)编译程序:如果源语言为高级语言,目标语言为某台计算机上的汇编语言或机器语言,则此翻译程序称为编译程序。 (2)源程序:源语言编写的程序称为源程序。 (3)目标程序:目标语言书写的程序称为目标程序。 (4)编译程序的前端:它由这样一些阶段组成:这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段,某些优化工作也可在前端做,也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 (5)后端:指那些依赖于目标机而一般不依赖源语言,只与中间代码有关的那些阶段,即目标代码生成,以及相关出错处理和符号表操作。 (6)遍:是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成?各部分的主要功能是什么?并画出编译程序的总体结构图。 答案: 一个典型的编译程序通常包含8个组成部分,它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序:输人源程序,拼单词、检查单词和分析单词,输出单词的机内表达形式。 语法分析程序:检查源程序中存在的形式语法错误,输出错误处理信息。 语义分析程序:进行语义检查和分析语义信息,并把分析的结果保存到各类语义信息表中。 中间代码生成程序:按照语义规则,将语法分析程序分析出的语法单位转换成一定形式的中间语言代码,如三元式或四元式。 中间代码优化程序:为了产生高质量的目标代码,对中间代码进行等价变换处理。目标代码生成程序:将优化后的中间代码程序转换成目标代码程序。

编译原理:学习指导与典型题解析

(1)——不是NFA的成分o A.有穷字母表B.初始状态集合 c.终止状态集合D.有限状态集合 (北京航天航空大学研究生入学考试试题 (2)——不是编译程序的组成部分0 A.词法分析程序B.代码生成程序 c.设备管理程序D.语法分析程序 (北京航天航空大学研究生入学考试试题 解答 (1)B,(2)C 例题2.2 给出下面描述的正规表达式 (1)以0l结尾的二进制数串; (2)能被5整除的十进制整数; (3)包含奇数个t或奇数个0的二进制数串 解题思路 (1)分析题意,要求的是二进制串,即由0和1构成的串,并且必须以ot结尾,所以 本题可以分两部分去完成,一部分实现由o和1构成的任意串,一部分即01,然后将它们连接到一起就可以了,所以本题的解答是:(1|0)*01 (2)分析题意,本题要求是十进制整数,也就是由o09这10个数字组成的字符串, 并且不能以o开头(整数“o”除外),要求能被5整除,则该串必须以0或者5结尾0根据我们的分析,可以把本题分成两种情况考虑:一种情况是该整数只有1位,则该整数有0 和5两种可能;另外一种情况是该整数有多位,则该整数可以分成3部分考虑,一是第l 位必须不为0,二是最后1位必须为0或5,三是中间部分可有可无,并且可以由0…9之间任意数字构或,所以本题的正规表达式为:(1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*(0|5)| (0|5) (3)本题求二进制串,并且要求包含奇数个0或奇数个1,由于o和1都可以在二进制串 中任何地方出现,所以本题只需要考虑一种情况,另外一种情况也可以类似求得0考虑包含奇数个0的字符串:由于只关心0的个数的奇偶数,我们可以把二进制串分成多段来考虑,第1段为二进制串的开始到第1个0为止,这一段包含1个o,并且0的前面有0个或多个l,对于剩下的二进制串按照每段包含两个0的方式去划分,即以o开始,以0结尾,中间可以有0个或多个1,如果一个二进制串被这样划分完后,剩下的部分如果全部是全1串(这些全1串在前面划分的串之间或最后),则该二进制串就具有奇数个o,所以该二进制串可以这样描述:以第1段(1‘o)开始.后面由全1串(1‘)以及包含两个o的串(ol0o)组成,所以包含奇数个0的正规表达式为:100(1[ol’o]‘,本题的解答则是:1*0(1|01*0)*|0*1(0|10*1)*

(精选)广工2014编译原理实验报告

实验报告 课程名称编译原理 题目名称 PL/0编译器的扩充 学生学院计算机学院 专业班级计算机科学与技术12(4) 学号 3112005901 学生姓名柏石先 指导教师李杨 程序功能完成情况 测试用例全面程度 学生对所编程序熟悉程度 报告格式是否与要求相符 报告内容是否准确、全面 2014 年 12 月 20日

一、实验目的与要求 对PL/0作以下修改扩充: (1)增加单词:保留字 ELSE,FOR,STEP,UNTIL,DO,RETURN 运算符 *=,/=,&,||,! (2)修改单词:不等号# 改为 <> (3)增加条件语句的ELSE子句,要求:写出相关文法,语法描述图,语义描述图。 二、实验环境与工具 1、源语言:PL/0语言,PL/0语言是PASCAL语言的子集,它的编译程序是一个编译解 析执行系统,后缀名为.PL0; 2、目标语言:生成文件后缀为*.COD的目标代码 3、实现平台:Borland C++Builder 6 4、运行平台:Windows 8.1 三、结构流程 1、结构设计说明 (1)PL/0 语言编译器 PL/0语言可看成是PASCAL语言的子集,它的编译程序是一个编译解释执行系统。PL/0的目标程序为假想栈式计算机的汇编语言,与具体计算机无关。

2、词法分析程序的设计 四、开发过程 (一)增加单词:保留字 ELSE,FOR,STEP,UNTIL,DO , RETURN 运算符 *=,/=,&,||,! 新增6个保留字和5个运算符,合计11个单词。 其中保留字ELSE,FOR,STEP,UNTIL,DO, RETURN分别对应ELSESYM,FORSYM, STEPSYM, UNTILSYM,DOSYM,RETURNSYM; 运算符 *= ,/= ,& ,|| ,!分别对应TIMESBECOMES, SLASHBECOMES, ANDSYM, ORSYM, NOTSYM。 注:要求只做词法分析部分,不做语义分析处理,实验的结果只是识别新增的保留字和运算 1.首先考虑需要增加保留字的个数,以及如何命名,再将新增的保留字添加对应的保留字的集合中。具体实现的语句如下所示: typedef enum { NUL, IDENT, NUMBER, PLUS, MINUS, TIMES, SLASH, ODDSYM, EQL, NEQ, LSS, LEQ, GTR, GEQ, LPAREN, RPAREN, COMMA, SEMICOLON, PERIOD,

编译原理 龙书 第二版 第4章

第四章 习题4.2.1:考虑上下文无关文法: S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1:下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|,以避免和文法中作为元符号使用的竖线相混淆: rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗? 3)提取公因子之后,原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗? 解 1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以,文法中存在左递归,而自顶向下技术不适合左递归文法 3)消除左递归后的文法

rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归,适合于自顶向下的语法分析 习题4.4.1:为下面的每一个文法设计一个预测分析器,并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③ (5) ①消除该文法的左递归得到文法 S->(L)|a

相关主题
文本预览
相关文档 最新文档