编译原理优先函数表怎么画
Ⅰ 优先函数是什么编译原理
构造算符优先分析表时使用的优先函数,其等价于矩阵表,但存储量小。
定义两个函数,其对应元素的值为优先值,通过循环比较各元素的两个值,每次将优先级大的值改为小的值+1,若相等则都赋为目前较大的值,循环直至结果没有变化,构造OK
Ⅱ 试述编译原理中优先函数有何好处与不足之处
构造算符优先分析表时使用的优先函数,其等价于矩阵表,但存储量校 定义两个函数,其对应元素的值为优先值,通过循环比较各元素的两个值,每次将优先级大的值改为小的值+1,若相等则都赋为目前较大的值,循环直至结果没有变化,构造OK
Ⅲ 编译原理 文法题目
首先扩展文法为:
1) S1->S
2) S->aS
3) S->bS
4) S->a
则:
I0 = Closure({S1->.S})={S1->.S,S->.aS,S->.bS,S->.a}
go(I0,S) = Closure({S1->S.})={S1->S.} = I1
go(I0,a) = Closure({S->a.S,S->a.})={S->a.S,S->.aS,S->.bS,S->.a,S->a.} = I2
go(I0,b) = Closure({S->b.S})={S->b.S,S->.aS,S->.bS,S->.a}=I3
go(I2,S) = closure({S->aS.})={S->aS.}=I4
go(I2,a) = Closure({S->a.S,S->a.}) = I2
go(I2,b) = Closure({S->b.S}) =I3
go(I3,S) = Closure({S->bS.}) = {S->bS.} = I5
go(I3,a) = Closure({S->a.S,S->a.}) = I2
go(I3,b) = Closure({S->b.S}) = I3
由图所示,状态I2,既有归约项目(S->a.)又有移近项目(S->.aS,S->.bS,S->.a),产生冲突。当用SRL分析法时,需向前看一步,即求出:
Follow(S) = Follow(S1) = {#}
则,Follow(S)∩{a,b} =∮
故而Action(I2,a) = s2
Action(I2,b) = s3
Action(I2,#) = r4
则构造出srl分析表如下所示:
Action Goto
a b # S
I0 s2 s3 1
I1 acc
I2 s2 s3 r4 4
I3 s2 s3 5
I4 r2 r2 r2
I5 r3 r3 r3
请采纳。
Ⅳ 编译原理:优先函数 f和g 到底怎么看啊,不懂怎么构造的 求解...
求算符优先函数的方法—迭代法
若已知运算符之间的优先关系,可按如下步骤构造优先函数:
1、对每个运算符a(包括#在内)令f(a)=g(a)=1
2、如果a⋗b且f(a)<=g(b),令f(a)=g(b)+1
3、如果a⋖b且f(a)>=g(b),令g(b)= f(a)+1
4、如果a≐b而f(a) ≠g(b),令min{f(a),g(b)}=max{f(a),g(b)}
5、重复2~4,直到过程收敛。如果重复过程中有一个值大于2n,则表明不存在算符优先函数。
Ⅳ 谁能够解释下编译原理中什么是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的箭弧。