编译原理中的候选式

⑴ 关于LL(1)文法的编译原理题目

判断是不是LL(1)，首先看候选式的首字符有没有相同的，第二判断首字符迭代进去是否会构成左递归。
如果首字符不相同，也没用左递归就说明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一个产生式中存在左递归:M->MaH
第二个产生式中存在首字符相同:H->b(M) ,
H->b
怎么改呢？
对第一个产生式，消除左递归就是要变成右递归，把右边剩下的符号提到前面:
M->aHM'

M'->aHM'
对第二个产生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'

H'->(M)|ε

⑵ 编译原理问题--优先关系表怎么画

先求出FIRSTVT和LASTVT。

找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现：

A->a.......，即以终结符开头，该终结符入Firstvt

A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt

A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现：

A->.......a，即以终结符结尾，该终结符入Lastvt

A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt

A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt

然后逐条扫描文法规则。例题如下，参考这个例题能很好地理解如何构造优先关系表。

《编译原理》(第4版)第三章例题4.12

⑶ 编译原理中FIRSTVT和LASTVT是什么意思

Firstvt和Lastvt是为了画算符优先关系表的（就是表里面填优先大于小于等于的那个）。
然后要注意他们可都是终结符的集合。
Firstvt
找Firstvt的三条规则：如果要找A的Firstvt，A的候选式中出现：
A->a.......，即以终结符开头，该终结符入Firstvt
A->B.......，即以非终结符开头，该非终结符的Firstvt入A的Firstvt
A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

Lastvt
找Lastvt的三条规则：如果要找A的Lastvt，A的候选式中出现：
A->.......a，即以终结符结尾，该终结符入Lastvt
A->.......B，即以非终结符结尾，该非终结符的Lastvt入A的Lastvt
A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Firstvt

⑷ 编译原理问题，高手进。

回答下列问题：(30分)
(6分)对于下面程序段
program test (input, output)
var i, j: integer;
procere CAL(x, y: integer);
begin
y:=y*y; x:=x-y; y:=y-x
end;
begin
i:=2; j:=3; CAL(i, j)
writeln(j)
end.
若参数传递的方法分别为(1)传值、(2)传地址，(3)传名，请写出程序执行的输出结果。
答： (1) 3 (2) 16 (3) 16 (每个值2分)

(6分)计算文法G(M)的每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。
G(M)：
M → TB
T → Ba |
B → Db | eT |
D → d |

解答：
计算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， }
FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#}
FOLLOW (B) = {a，# } FOLLOW (D) = { b}

检查文法的所有产生式，我们可以得到：
1. 该文法不含左递归，
2. 该文法中每一个非终结符M，T，B，D的各个产生式的候选首符集两两不相交。
3. 该文法的非终结符T、B和D，它们都有候选式，而且
FIRST(T)∩FOLLOW(T)={ a，b，e，d }≠
所以该文法不是LL(1)文法。(2分)

(4分)考虑下面的属性文法
产 生 式 语 义 规 则
S→ABC

A→a
B→b
C→c B.u := S.u
A.u := B.v + C.v
S.v := A.v
A.v :=3*A.u
B.v := B.u
C.v := 1
画出字符串abc的语法树;
对于该语法树，假设S.u的初始值为5，属性计算完成后，S.v的值为多少。
答：(1) (2分)

(2) S.v的值为18 (2分)

(4分)运行时的DISPLAY表的内容是什么？它的作用是什么？
答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。

(5分)对下列四元式序列生成目标代码：
A:=B*C
D:=E+A
G:=B+C
H:=G*D
其中，H在基本块出口之后是活跃变量， R0和R1是可用寄存器。
答: 目标代码序列
LD R0 B
MUL R0 C
LD R1 E
ADD R1 R0
LD R0 B
ADD R0 C
MUL R0 R1
ST R0 H

(5分)写出表达式a+b*(c-d)对应的逆波兰式、三元式序列和抽象语法树。
答：
逆波兰式：(abcd-*+) (1分)
三元式序列: (2分)
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
抽象语法树：(2分)

(8分)构造一个DFA，它接受={a，b}上所有包含ab的字符串。
答：
(2分)构造相应的正规式：(a|b)*ab(a|b)*

(3分)
a a

a b
b b

(3分)确定化：
I
{0,1,2} {1,2,3} {1,2}
{1,2,3} {1,2,3} {1,2,4,5,6}
{1,2} {1,2,3} {1,2}
{1,2,4,5,6} {1,2,3,5,6} {1,2,5,6}
{1,2,3,5,6} {1,2,3,5,6} {1,2,4,5,6}
{1,2,5,6} {1,2,3,5,6} {1,2,5,6}
b b
b a
a a a a

a b b
b

最小化：
{0，1，2} {3，4，5}
{0， 2}，1， {3，4，5}

(6分)写一个文法使其语言为L(G)={anbncm| m,n≥1，n为奇数，m为偶数}。
答：
文法G(S):

(8分)对于文法G(S):

1. 写出句型b(Ma)b的最右推导并画出语法树。
2. 写出上述句型的短语，直接短语和句柄。
答：
1. (4分)

2. (4分)
短语: Ma)， (Ma)， b(Ma)b
直接短语: Ma)
句柄: Ma)

(12分)对文法G(S)：
S → a | ^ | (T)
T → T，S | S
(1) 构造各非终结符的FIRSTVT和LASTVT集合;
(2) 构造算符优先表;
(3) 是算符优先文法吗?
(4) 构造优先函数。
答：
(1) (4分)

(2) (4分)
a ^ ( ) ,
a > >
^ > >
( < < < = <
) > >
, < < < > >

(3) 是算符优先文法，因为任何两个终结符之间至多只有一种优先关系。 (1分)

(4) 优先函数(3分)
a ^ ( ) ,
F 4 4 2 4 4
G 5 5 5 2 3

(8分)设某语言的do-while语句的语法形式为
S do S(1) While E
其语义解释为：

针对自下而上的语法分析器，按如下要求构造该语句的翻译模式，将该语句翻译成四元式：
(1) 写出适合语法制导翻译的产生式；
(2) 写出每个产生式对应的语义动作。
答：(1). 适合语法制导翻译的文法(4分)
G(S):
R do
UR S(1) While
SU E
(2). (4分)
R do
{ R.QUAD:=NXQ }

UR S(1) While
{ U.QUAD:=R.QUAD;
BACKPATCH(S.CHAIN, NXQ) }

SU E
{ BACKPATCH(E.TC, U.QUAD);
S.CHAIN:=E.FC }

答案二：
(1) S do M1 S(1) While M2 E
M ε (4分)
(2) M ε { M.QUAD := NXQ } (4分)
S do M1 S(1) While M2 E
{
BACKPATCH(S(1).CHAIN, M2.QUAD);
BACKPATCH(E.TC, M1.QUAD);
S.CHAIN:=E. FC
}

(10分)将语句
while C>0 do if A B=0 then C:=C+D else C:=C*D
翻译成四元式。
答：
100 (j>， C， 0， 102)
101 (j， -， -， 112)
102 (jnz， A， -， 106)
103 (j， -， -， 104)
104 (j=， B， 0， 106)
105 (j， -， -， 109)
106 (+， C， D， T1)
107 (:=， T1， -， C)
108 (j， -， -， 100)
109 (*， C， D， T2)
110 (:=， T2， -， C)
111 (j， -， -， 100)
112

(10分)设有基本块如下：
T1:=3
T2:=A*B
T3:=9+T1
M:=A*B
T4:=C-D
L:=T3*T4
T2:=C+D
N:=T2
画出DAG图；
设L，M，N 是出基本块后的活跃变量，请给出优化后的四元式序列。
答：

1. (6分)
L

*
T2,M T4 T2,N

* - +

T1 T3
3 A B 12 C D

2. (4分)
M:=A*B
S1:=C-D
L:=12*S1
N:=C+D

(8分)文法G(S)及其LR分析表如下，请给出串baba#的分析过程。
(1) S → DbB (2) D → d (3) D → ε
(4) B → a (5) B → Bba (6) B → ε
LR分析表
ACTION GOTO
b D a # S B D
0 r3 s3 1 2
1 acc
2 s4
3 r2
4 r6 S5 r6 6
5 r4 r4
6 s7 r1
7 S8
8 r5 r5
解答：
步骤 状态 符号 输入串
0 0 # baba#
1 02 #D baba#
2 024 #Db aba#
3 0245 #Dba ba#
4 0246 #DbB ba#
5 02467 #DbBb a#
6 024678 #DbBba #
7 0246 #DbB #
8 01 #S # acc
哈哈，估计认识！！

⑸ 在编译原理中： 文法S——>SS+|SS*|a能产生什么语言，并验证！ 求高人指导！

为了使问题简化，我们考虑文法S->ss+|a，考虑s->ss*时，只要把+换成*即可。
0层递归是，s->a,文法的语言是{a}。是后缀表达式。
1层以内递归时，文法语言是{a,aa+}。是后缀表达式。
2层以内递归时，文法语言是{a,aa+}.{a,aa+}.{+}。其中.表示连接，是后缀表达式。
依此类推，多少层的递归都是后缀表达式。
把表达式的+换成*后依然为后缀表达式。
下面证明文法产生的语言是所有的以a为变量，以+和*为运算符的后缀表达式。
因为每个表达式都对应一个常规的表达式（如1*2+3就是常规表达式），下面只需证明语言能产生的后缀表达式对应所有的常规表达式。当常规表达式只有一个运算符，对应aa+或aa*。当常规表达式有两个运算符，可写成(表达式1）.{+|*}.(表达式2），因为表达式1和2都只含一个运算符，所以可以用语言表示，上述常规表达式可用后缀表达式（表达式1）.（表达式2）.{+l*}表示。所以不管常规表达式有多少个运算符，都可以由语言的后缀表达式对应。

⑹ 谁能够解释下编译原理中什么是FIRSTVT,和LASTVT，尽量浅显易懂点谢谢

给你COPY一个看管用不,虽然不懂你在问什么...

算符优先分析 [上一节] [下一节]

5.2.1 算符优先文法及其优先表构造

一个文法，如果它的任一产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：

…QR…

则我们称该文法为算符文法。

在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表由终结符和非终结符组成的任意序列，包括空字。

假定G是一个不含e-产生式的算符文法。对于任何一对终结符a、b，我们说：

1. a�6�7b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；

2. a�6�3b当且仅当G中含有形如P→…aR…的产生式，而Rb…或RQb…；

3. a�6�4b当且仅当G中含有形如P→…Rb…的产生式，而R…a或R…aQ。

如果一个算符文法G中的任何终结符对（a，b）至多只满足下述三关系之一：

a�6�7b，a�6�3b， a�6�4b

则称G是一个算符优先文法。

现在来研究从算符优先文法G构造优先关系表的算法。

通过检查G的每个产生式的每个候选式，可找出所有满足a�6�7b的终结符对。为了找出所有满足关系�6�3和�6�4的终结符对，我们首先需要对G的每个非终结符P构造两个集合FIRSTVT（P）和LASTVT（P）：

FIRSTVT（P）＝{a | Pa…或PQa…，a�0�2VT而Q�0�2VN}

LASTVT（P）＝{a | P…a或P…aQ，a�0�2VT而Q�0�2VN}

5.2.2 算符优先分析算法

所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。所谓最左素短语是指处于句型最左边的那个素短语。如上例，P*P和i是句型P*P+i的素短语，而P*P是它的最左素短语。

现在考虑算符优先文法，我们把句型（括在两个＃之间）的一般形式写成：

#N1a1N2a2…NnanNn+1# (5.4)

其中，每个ai都是终结符，Ni是可有可无的非终结符。换言之，句型中含有n个终结符，任何两个终结符之间顶多只有一个非终结符。必须记住，任何算符文法的句型都具有这种形式。我们可以证明如下定理（证明留给有兴趣的读者作练习）：

一个算符优先文法G的任何句型（5.4）的最左素短语是满足如下条件的最左子串Njaj…NiaiNi+1，

aj-1�6�3aj

aj�6�7 aj+1，…，ai-1�6�7ai

ai�6�4ai+1

根据这个定理，下面我们讨论算符优先分析算法。为了和定理的叙述相适应，我们现在仅使用一个符号栈S，既用它寄存终结符，也用它寄存非终结符。下面的分析算法是直接根据这个定理构造出来的，其中k代表符号栈S的使用深度。

5.2.3 优先函数

在实际实现算符优先分析算法时，一般不用表5.1这样的优先表，而是用两个优先函数f和g。我们把每个终结符q与两个自然数f（q）和g（q）相对应，使得

若q1�6�3q2 则 f（q1）<g（q2）

若q1�6�7q2 则 f（q1）= g（q2） （5.5）

若q1�6�4q2 则 f（q1）>g（q2）

函数f称为入栈优先函数，g称为比较优先函数。使用优先函数有两方面的优点：便于作比较运算，并且节省存储空间，因为优先关系表占用的存储量比较大。其缺点是，原先不存在优先关系的两个终结符，由于与自然数相对应，变成可比较的了。因而，可能会掩盖输入串的某些错误。但是，我们可以通过检查栈顶符号q和输入符号a的具体内容来发现那些原先不可比较的情形。

如果优先函数存在，那么，从优先表构造优先函数的一个简单方法是：

1. 对于每个终结符a（包括＃）令其对应两个符号fa和ga，画一张以所有符号fa和ga为结点的方向图，如果a �6�4�6�7b，那么，就从fa画一箭弧至gb；如果a�6�3�6�7b，就画一条从gb到fa的箭弧。

⑺ 编译原理

编译原理)：利用编译程序从源语言编写的源程序产生目标程序的过程； 用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。

编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成

(7)编译原理中的候选式扩展阅读：

编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。

编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。

而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。

⑻ 编译原理的LL（1）文法是什么意思

1.文法不含左递归，没有公共左因子
2.对于文法中的每个非终结符A的产生式的候选首符集两两不相交。
3.对于文法中的每个非终结符A，它存在某个候选首符集包括ε，则FIRST（A）∩FOLLOW（A）=空
满足以上条件的文法为LL（1）文法