形式系统

1、       已知文法 G （ S ）
S → *A       A → 0A1 | *
(1)         求文法 G 的各非终结符号的 FIRSTVT 和 LASTVT 集合。
(2)         构造文法 G 的优先关系矩阵，并判断该文法是否算符优先文法。
(3)         分析句子 *0*1 ，并写出分析过程。
   分析：FIRSTVT 及 LASTVT 求法 
            构造集合 FIRSTVT （ P ）的两条规则。 
               （i）   若有产生式 P→a… ，或 P→Qa… ，则 a ∈ FIRSTVT （ P ）。 
               （ii）   若 a ∈ FIRSTVT （ P ），且有产生式 P→Q… ，则 a ∈ FIRSTVT （ P ）。 
            构造集合 FIRSTVT （ P ）的两条规则 
               （i）   有产生式P→…a，或P→…aQ，则a∈LASTVT（P）。
                 (ii)      若 a ∈ LASTVT （ Q ），且有产生式 P→Q… ，则 a ∈ FIRSTVT （ P ）。  

（1）

	FIRSTVT	LASTVT
S	*	1 *
A	0 *	1 *

   分析：   若有产生式的候选形为：            …aPb…       则      a=•b 
                  若有个产生式的候选形为：       …aP…           则     b ∈ FIRSTVT （ P ）     a<•b       
                  若有个产生式的候选形为：         …Pb…         则     a ∈ LASTVT （ P ）       a•>b      

	*	0	1	#
*	<	<	>	>
0	<	<	=
1			>	>
＃	<			=

(3)         符号栈       优先关系       输入 
                 #                  <                     *
                 # *               <                     0
                 # * 0            <                     *
                 # * 0 *          >                    1
                 # * 0 A         =                    1
                 # * 0 A 1      >                    #
                 # * A            >                    #
                 # S               =                    #

2、考虑下列文法G：