编译原理文字题

Ⅰ 给力！2011年新年散分啦。高分求助编译原理高手帮忙做几道模拟题

三、（ 8 分）化简文法 G[S] ：
S → ASe | BCaD | aD | AC
A → Cb | DBS
C → bC | d
B → Ac
D → Ad
化简后： S → ASe|AC A → Cb C → bC | d
四、（ 12 分） 设 L í {a,b,c}* 是满足下述条件的符号串构成的语言：
(1)若出现 a ，则其后至少紧跟两个 c ；
(2)若出现 b ，其后至少紧跟一个 c 。
试构造识别 L 的最小化的 DFA ，并给出描述 L 的正规表达式。
答：DFA 如图所示。相应的正规式为 (c|acc|bc)* 。

五、（ 12 分） 已给文法 G[S] ： S → SaP | Sf | P P → qbP | q
将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。
答：改造后的文法： S → PS' S' → aPS'| fS' | e P → qP' P' → bP | e
各候选式的 FIRST 集，各非终结符的 FOLLOW 集为
产生式 FIRST 集 FOLLOW 集
S → PS' {q} {#}
S' → aPS'
→ fS'
→ e {a}
{f}
{ e } {#}
P → qP' {q} {a,f,#}
P' → bP
→ e {b}
{ e } {a,f,#}
LL(1) 分析表为

六、（ 12 分） 给定文法 G[S] ： S → Aa|dAb|Bb|dBa A → c B → c
构造文法 G[S] 的 LR （ 1 ）分析表。
分析表如下图所示

七、（ 8 分） 将下面的条件语句表示成逆波兰式和四元式序列：
if a>b then x:=a+b*c else x:=b-a;
答：（ 1 ）逆波兰式：
,其中， BLE 表示汪或等于时的转向指令； [ … ] 表示标号。
（ 2 ）四元式：
(1) ( j>, a, b, (3))
(2) ( j, , , (7) )
(3) ( *, b, c, T1)
(4) ( +, a, T1, T2)
(5) ( :=, T2, , x)
(6) ( j, , , (9))
(7) ( -, b, a, T3)
(8) ( :=, T3, , x)
(9) ( … … )
八、（ 8 分） 给定基本块：
A:=3*5
B:=E+F
C:=A+12
D:=E+F
A:=D+12
C:=C+1
E:=E+F
假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。
答：化简后的的四元式序列为
A :=D+12
E :=E+F
C :=28

Ⅱ 编译原理实验题，求解！谢谢!

第一问：

state=0;

while(1)

{

switch(state)

{

case 0:

c=nextchar();

if(c=='a')

state=1;

else if(c=='b')

state=2

else

error();

break;

case 1:

c=nextchar();

if(c=='a')

state=3;

else if(c=='b')

state=2;

else

error();

break;

case 2:

c=nextchar();

if(c=='b')

state=3;

else if(c=='a')

state=1;

else

error();

break;

case 3:

c=nextchar();

if(c=='a'||c=='b')

state=3;

else

error();

if(end)

return 1;

break;

}

}

第二问

如果不是dfa，可用子集够造法化为dfa.

Ⅲ 有几道编译原理的题目不知道怎么做了,求教!

1 选A，*与+的区别在于*包含0
2 B
3 D ABb>Abb>abb
4 D
5 B 循环优化的三种重要技术是： 代码外提；删除归纳变量和强度削弱。

1 错
2 对

Ⅳ 请教几个有关编译原理的习题！

答:
一
1. S -> aS | ε
2. S -> aS | Sb | ab
二
设 有字符串序列 abc, 而字符串 abc 符合是文法S.
abc 有两种推导 ① S -> Ac, A -> bc
② S -> aB, B -> bc
有两语法树,二义文法
三
不好意思忘记了短语、直接短语和句柄
课本上应该有

Ⅳ 编译原理文法题

DFA

如果能帮上你，望采纳！

Ⅵ 关于编译原理的问题

1.当然是机器语言了，如果是汇编指令，那还得编译一次！能运行的程序都是机器语言，只有机器语言才能控制CPU，NET或Java这些中间语言，程序在运行时会被CLR或JVM快速编译成机器语言，因此这些程序速度上有损失。

高级语言源代码（文本）-通过编译器（compiler）-程序（二进制机器语言）
汇编代码（文本）-通过汇编器（assembler）-程序（二进制语言）

看到这里，你可能会想那汇编语言到底有什么用呢，编译器完全能代替汇编啊？
（1）.编译器是通过高级语言（c,c++)转到机器语言的。转换过的机器语言受限与高级语言，效率和功能上都有限制。比如c不等过分操作内存。但通过汇编器转化过来的机器语言，效率高，且用汇编语言，直接和CPU对话！
（2）.汇编可以反汇编（逆向编译），而这里高级语言没有发言权，就是：
程序（二进制机器语言）-通过反汇编器（compiler）-可转化为汇编代码（文本）
但永远不能转化为高级语言的源代码，。
以上两点汇编存在的重要性。

2。当然是说移植源代码。windows用x86机器语言，苹果用powerPC机器语言，windows程序当然不能运行在苹果机上，因为程序其实就是一串机器语言！但windows上有c的编译器（vc++），苹果机上也有c编译器（gcc），因此同一个c的源代码，当然就可以通过不同平台的同一种编译器实现平台移植。

3.当然是NASM，我看的所有书都首先说NASM，他是开源的，就像Linux一样，很受欢迎，还有MASN是微软的，borland的也有汇编器，不过都不常见了。

4.这跟CPU有关，一般32位x86兼容的cpu有许多寄存器，多数是32位的，也有16位的。比如CS,ES,DS这些segment寄存器一直是16位的。

5.优势太多了，这和32位和16位存在的优势一样，16位电脑最大内存1MB，寄存器都是16位的。32位，最大内存可以有4GB，整整是16位的4096倍啊！16位多渺小啊，同理64位基本上也可以蔑视32位，64内存最大内存用TB来衡量，寄存器多数是64位！地址总线也是64位。64对32位没有什么优势劣势可言，64位完全就是32位的下一代。

Ⅶ (高分)编译原理的题,求高手,在线等,急急急!!!!!!

太多了，大概看了下考点：

若源程序是用高级语言编写的,目标程序是 机器语言程序或汇编程序 ,则其翻译程序称为编译程序.

何谓优化？按所涉及的程序范围可分为哪几级优化？
答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。
三种级别：局部优化、循环优化、全局优化。

简述常用的优化技术有哪些？
答：编译程序中常用的优化技术有：
（1） 删除公共子表示式；
（2） 复写传播；
（3） 删除无用代码；
（4） 代码外提；
（5） 强度削弱；
（6） 删除归纳变量；
（7） 合并常量。

一个句型中的最左 B 称为该句型的句柄。
可选项有：
A. 短语 B. 简单短语 C. 素短语 D. 终结符号

.递归下降法不允许任一非终极符是直接 左 递归的。

简单优先方法每次归约当前句型的 句柄 ，算符优先方法每次归约当前句型的 最左素短语 ，二者都是不断移进输入符号，直到符号栈顶出现 可归约串 的尾，再向前找到 可归约串 的头，然后归约。

算符优先文法——设有一不含ε产生式的算符文法G，如果对任意两个终结符对a，b之间至多只有 、 和 三种关系中的一种成立，则称G是一个算符优先文法。

常用的中间语言种类有哪几种？
答：有逆波兰式、三地址代码、抽象语法树和DAG。

Ⅷ 编译原理判断题 设M是一个NFA,并且L(M)={x,y,z},则M的状态数至少为4个 请问这句话为什么是错误的呢

M的状态数至少为4个，这句话不正确。

比如下图，同样符合题目条件，但状态只有2个。

Ⅸ 编译原理文法问题，急急急

第一题
S->AB

A->aA'b
A'->aA'b|ε
B->B'
B'->dB'|ε
----------------------
第二题
S->aS'b

S'->aS'b|D
D->dD|ε
----------------------
第三题
最左推导的话，我认为要先消除左递归才行（把左递归转成右递归），消除之后:
N->DN'
N'->DN'|ε
D->0|1|2|...|9
最左推导为 N->DN'->2N'->2DN'->25N'->25DN'->258N'->258
规范推导(最右推导)为N->ND->N8->ND8->N58->D58->258
----------------------
第四题
构造一下语法树就知道了。直接短语是深度为2的节点（根节点是深度0）。短语是深度为2的节点代入深度为1的产生式中。句柄是所有直接短语中最左的那个。
1.baaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
_______|
______a
直接短语为 Aa、a
短语为 Aaa
句柄为 Aa
2.bBaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
直接短语为 Aa、a
短语为 Aaa
句柄为 Aa

Ⅹ 计算机科学与技术中编译原理简答题

时间有点久记得不太真切，用通俗语言说，希望题主尽量查阅书籍参考资料自行验证理解。

1、什么是移进项目，什么是规约项目

这个是自顶向下和自下向上分析时候用到的。所谓移进就是不处理，所谓规约就是处理，合并，替换。比如当前符合某个正规式左部，就用这个正规式右部替换左部，称为规约。两种操作的目的都是为了分析整体是否符合语法树。

2、请给出生成C语言语句序列的文法（假定s表示任意一个语句，它为终结符）

关于这个，我感觉你描述的不是很清楚，因为C语言文法包含的正规式还是挺多的，如果单指statement的话，
statement_listà
statement
| statement_list statement

Statementà
| compound_statement
| expression_statement
| selection_statement
| iteration_statement
| jump_statement
再配合上相应的终结符。

3、能用上下文无关文法生成正规集吗？为什么？

可以。不过无法保证不含冲突。

4、计算first集和follow集对于构造自顶向下的语法分析器有什么作用？

可以用来排除冲突。例如移进-移进冲突，移进-规约冲突。

5、是否可能存在这样一个DFA，它的所有状态都是接受状态，包括其实状态，为什么？

这个爱莫能助，据我的构想是可以的，但是这样的DFA最终都会成为单一状态DFA。