Построение множества ВЫБОР(n)

 

Построение множества ПЕРВ(n). Шаг 0. Для построения множества ПЕРВ(n) = FIRST(1, A), где А - нетерминал в правой части n – го правила, определим множества первых символов, стоящих в начале правых частей правил, для каждого нетерминала в левой части правил.

 

ПЕРВ(<S>)	using public
ПЕРВ(<NEXT>)	;
ПЕРВ(<USING_LIST>)	ID
ПЕРВ(<NEXT_USING>)	.
ПЕРВ(<CLASS>)	class
ПЕРВ(<CLASS_BODY>)	public
ПЕРВ(<NEXT_BODY>)	;
ПЕРВ(<DEF>)	uint bool const
ПЕРВ(<DEF_LIST>)	ID
ПЕРВ(<NEXT_DEF>)	(, =
ПЕРВ(<VAR_LIST>)	ID
ПЕРВ(<NEXT_VAR>)	, =
ПЕРВ(<OPER_LIST>)
ПЕРВ(<NEXT_OPER>)	;
ПЕРВ(<OPERATOR>)	for break continue write read ID
ПЕРВ(<LET>)	= * /
ПЕРВ(<EXPR>)	(ID NUM
ПЕРВ(<OPERATION>)	+ -
ПЕРВ(<COND>)	(
ПЕРВ(<RELATION>)	> < =

 

Шаг 1. Внесем во множество первых символов ПЕРВ(n)i для каждого правила символы, стоящие в начале правых частей правил. Индекс i = 0 – номер итерации.

 

ПЕРВ(1) 0	using
ПЕРВ(2) 0	public
ПЕРВ(3) 0	;
ПЕРВ(4) 0
ПЕРВ(5) 0	ID
ПЕРВ(6) 0	.
ПЕРВ(7) 0
ПЕРВ(8) 0	class
ПЕРВ(9) 0	public
ПЕРВ(10) 0	;
ПЕРВ(11) 0
ПЕРВ(12) 0	uint
ПЕРВ(13) 0	bool
ПЕРВ(14)	const
ПЕРВ(15) 0	ID
ПЕРВ(16) 0	(
ПЕРВ(17) 0	,
ПЕРВ(18)	=
ПЕРВ(19) 0
ПЕРВ(20) 0	ID
ПЕРВ(21) 0	,
ПЕРВ(22)	=
ПЕРВ(23) 0
ПЕРВ(24) 0	<OPERATOR>
ПЕРВ(25) 0	;
ПЕРВ(26) 0
ПЕРВ(27) 0	for
ПЕРВ(28) 0	break
ПЕРВ(29) 0	continue
ПЕРВ(30) 0	write
ПЕРВ(31) 0	read
ПЕРВ(32) 0	ID
ПЕРВ(33) 0	=
ПЕРВ(34) 0	*
ПЕРВ(35) 0	/
ПЕРВ(36) 0	(
ПЕРВ(37) 0	ID
ПЕРВ(38)	NUM
ПЕРВ(39) 0	+
ПЕРВ(40) 0	-
ПЕРВ(41) 0
ПЕРВ(42) 0	(
ПЕРВ(43) 0	<EXPR>
ПЕРВ(44) 0	>
ПЕРВ(45) 0	<
ПЕРВ(46) 0	=
ПЕРВ(47) 0

 

Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), определенное на шаге 0.

ПЕРВ(1) 1	using
ПЕРВ(2) 1	public
ПЕРВ(3) 1	;
ПЕРВ(4) 1
ПЕРВ(5) 1	ID
ПЕРВ(6) 1	.
ПЕРВ(7) 1
ПЕРВ(8) 1	class
ПЕРВ(9) 1	public
ПЕРВ(10) 1	;
ПЕРВ(11) 1
ПЕРВ(12) 1	uint
ПЕРВ(13) 1	bool
ПЕРВ(14) 1	const
ПЕРВ(15) 1	ID
ПЕРВ(16) 1	(
ПЕРВ(17) 1	,
ПЕРВ(18) 1	=
ПЕРВ(19) 1
ПЕРВ(20) 1	ID
ПЕРВ(21) 1	,
ПЕРВ(22) 1	=
ПЕРВ(23) 1
ПЕРВ(24) 1	for break continue write read ID <OPERATOR>
ПЕРВ(25) 1	;
ПЕРВ(26) 1
ПЕРВ(27) 1	for
ПЕРВ(28) 1	break
ПЕРВ(29) 1	continue
ПЕРВ(30) 1	write
ПЕРВ(31) 1	read
ПЕРВ(32) 1	ID
ПЕРВ(33) 1	=
ПЕРВ(34) 1	*
ПЕРВ(35) 1	/
ПЕРВ(36) 1	(
ПЕРВ(37) 1	ID
ПЕРВ(38) 1	NUM
ПЕРВ(39) 1	+
ПЕРВ(40) 1	-
ПЕРВ(41) 1
ПЕРВ(42) 1	(
ПЕРВ(43) 1	(ID NUM <EXPR>
ПЕРВ(44) 1	>
ПЕРВ(45) 1	<
ПЕРВ(46) 1	=
ПЕРВ(47) 1

 

Шаг 3. Если ПЕРВ(n)i+1 ≠ ПЕРВ(n)i, то i = i + 1 и перейти к шагу 2, иначе закончить.

Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), определенное на шаге 0.

 

ПЕРВ(1) 2	using
ПЕРВ(2) 2	public
ПЕРВ(3) 2	;
ПЕРВ(4) 2
ПЕРВ(5) 2	ID
ПЕРВ(6) 2	.
ПЕРВ(7) 2
ПЕРВ(8) 2	class
ПЕРВ(9) 2	public
ПЕРВ(10) 2	;
ПЕРВ(11) 2
ПЕРВ(12) 2	uint
ПЕРВ(13) 2	bool
ПЕРВ(14) 2	const
ПЕРВ(15) 2	ID
ПЕРВ(16) 2	(
ПЕРВ(17) 2	,
ПЕРВ(18) 2	=
ПЕРВ(19) 2
ПЕРВ(20) 2	ID
ПЕРВ(21) 2	,
ПЕРВ(22) 2	=
ПЕРВ(23) 2
ПЕРВ(24) 2	for break continue write read ID
ПЕРВ(25) 2	;
ПЕРВ(26) 2
ПЕРВ(27) 2	for
ПЕРВ(28) 2	break
ПЕРВ(29) 2	continue
ПЕРВ(30) 2	write
ПЕРВ(31) 2	read
ПЕРВ(32) 2	ID
ПЕРВ(33) 2	=
ПЕРВ(34) 2	*
ПЕРВ(35) 2	/
ПЕРВ(36) 2	(
ПЕРВ(37) 2	ID
ПЕРВ(38) 2	NUM
ПЕРВ(39) 2	+
ПЕРВ(40) 2	-
ПЕРВ(41) 2
ПЕРВ(42) 2	(
ПЕРВ(43) 2	(ID NUM
ПЕРВ(44) 2	>
ПЕРВ(45) 2	<
ПЕРВ(46) 2	=
ПЕРВ(47) 2

 

Шаг 3. Если ПЕРВ(n)_i+1 ≠ ПЕРВ(n)_i, то i = i + 1 и перейти к шагу 2, иначе закончить.

Построение множества ПЕРВ(А). Множества ПЕРВ(А) необходимо для определения множеств СЛЕД(А).

Шаг 1. Для построения множества ПЕРВ(А) = FIRST(1, A), где А - нетерминал в правой части правил, определим множества первых символов, стоящих в начале правых частей правил, для каждого нетерминала в левой части правил.

 

ПЕРВ(<S>)	using public
ПЕРВ(<NEXT>)	;
ПЕРВ(<USING_LIST>)	ID
ПЕРВ(<NEXT_USING>)	.
ПЕРВ(<CLASS>)	class
ПЕРВ(<CLASS_BODY>)	public
ПЕРВ(<NEXT_BODY>)	;
ПЕРВ(<DEF>)	uint bool const
ПЕРВ(<DEF_LIST>)	ID
ПЕРВ(<NEXT_DEF>)	(, =
ПЕРВ(<VAR_LIST>)	ID
ПЕРВ(<NEXT_VAR>)	, =
ПЕРВ(<OPER_LIST>)	<OPERATOR>
ПЕРВ(<NEXT_OPER>)	;
ПЕРВ(<OPERATOR>)	for break continue write read ID
ПЕРВ(<LET>)	= * /
ПЕРВ(<EXPR>)	(ID NUM
ПЕРВ(<OPERATION>)	+ -
ПЕРВ(<COND>)	<EXPR> (
ПЕРВ(<RELATION>)	> < =

Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), i=0.

 

ПЕРВ(<S>)0	using public
ПЕРВ(<NEXT>)0	;
ПЕРВ(<USING_LIST>)0	ID
ПЕРВ(<NEXT_USING>)0	.
ПЕРВ(<CLASS>)0	class
ПЕРВ(<CLASS_BODY>)0	public
ПЕРВ(<NEXT_BODY>)0	;
ПЕРВ(<DEF>)0	uint bool const
ПЕРВ(<DEF_LIST>)0	ID
ПЕРВ(<NEXT_DEF>)0	(, =
ПЕРВ(<VAR_LIST>)0	ID
ПЕРВ(<NEXT_VAR>)0	, =
ПЕРВ(<OPER_LIST>)0	for break continue write read ID
ПЕРВ(<NEXT_OPER>)0	;
ПЕРВ(<OPERATOR>)0	for break continue write read ID
ПЕРВ(<LET>)0	= * /
ПЕРВ(<EXPR>)0	(ID NUM
ПЕРВ(<OPERATION>)0	+ -
ПЕРВ(<COND>)0	(ID NUM
ПЕРВ(<RELATION>)0	> < =

 

Шаг 3. Выполнение шага 2 привело к изменению множеств ПЕРВ(А), поэтому повторим шаг 2.

Шаг 2. Если множество первых символов содержит нетерминал В, то включить в него символы множества ПЕРВ(В), i=1.

 

ПЕРВ(<S>)1	using public
ПЕРВ(<NEXT>)1	;
ПЕРВ(<USING_LIST>)1	ID
ПЕРВ(<NEXT_USING>)1	.
ПЕРВ(<CLASS>)1	class
ПЕРВ(<CLASS_BODY>)1	public
ПЕРВ(<NEXT_BODY>)1	;
ПЕРВ(<DEF>)1	uint bool const
ПЕРВ(<DEF_LIST>)1	ID
ПЕРВ(<NEXT_DEF>)1	(, =
ПЕРВ(<VAR_LIST>)1	ID
ПЕРВ(<NEXT_VAR>)1	, =
ПЕРВ(<OPER_LIST>)1	for break continue write read ID
ПЕРВ(<NEXT_OPER>)1	;
ПЕРВ(<OPERATOR>)1	for break continue write read ID
ПЕРВ(<LET>)1	= * /
ПЕРВ(<EXPR>)1	(ID NUM
ПЕРВ(<OPERATION>)1	+ -
ПЕРВ(<COND>)1	(ID NUM
ПЕРВ(<RELATION>)1	> < =

 

Шаг 3. Дальнейшее выполнения шага 2 не приведет к изменению множеств ПЕРВ(А), поэтому закончим.

Построение множества СЛЕД(А). Множества СЛЕД(А) строятся для всех нетрминальных символов грамматики методом последовательного приближения.

Шаг 1. Внесем во множество последующих символов СЛЕД(А) = FOLLOW(1, A) для каждого нетерминала А все символы, которые в правых частях правил встречаются непосредственно за символом А; i=0.

 

СЛЕД(<S>)0
СЛЕД(<NEXT>)0
СЛЕД(<USING_LIST>)0	<NEXT>
СЛЕД(<NEXT_USING>)0
СЛЕД(<CLASS>)0	<NEXT>
СЛЕД(<CLASS_BODY>)0	}
СЛЕД(<NEXT_BODY>)0
СЛЕД(<DEF>)0	<NEXT_BODY>
СЛЕД(<DEF_LIST>)0
СЛЕД(<NEXT_DEF>)0
СЛЕД(<VAR_LIST>)0	)
СЛЕД(<NEXT_VAR>)0
СЛЕД(<OPER_LIST>)0	}
СЛЕД(<NEXT_OPER>)0
СЛЕД(<OPERATOR>)0	<NEXT_OPER>
СЛЕД(<LET>)0	)
СЛЕД(<EXPR>)0	<VAR_LIST>;) <RELATION>
СЛЕД(<OPERATION>)0
СЛЕД(<COND>)0	;)
СЛЕД(<RELATION>)0

 

Шаг 2. Внесем пустую цепочку (или символ конца строки) во множество последующих символов для целевого символа <S>.

 

СЛЕД(<S>)0	#
СЛЕД(<NEXT>)0
СЛЕД(<USING_LIST>)0	<NEXT>
СЛЕД(<NEXT_USING>)0
СЛЕД(<CLASS>)0	<NEXT>
СЛЕД(<CLASS_BODY>)0	}
СЛЕД(<NEXT_BODY>)0
СЛЕД(<DEF>)0	<NEXT_BODY>
СЛЕД(<DEF_LIST>)0
СЛЕД(<NEXT_DEF>)0
СЛЕД(<VAR_LIST>)0	)
СЛЕД(<NEXT_VAR>)0
СЛЕД(<OPER_LIST>)0	}
СЛЕД(<NEXT_OPER>)0
СЛЕД(<OPERATOR>)0	<NEXT_OPER>
СЛЕД(<LET>)0	)
СЛЕД(<EXPR>)0	<VAR_LIST>;) <RELATION>
СЛЕД(<OPERATION>)0
СЛЕД(<COND>)0	;)
СЛЕД(<RELATION>)0

 

Шаг 3. Для всех нетерминальных символов A включить во множества СЛЕД(A) множества ПЕРВ(В), где B Î СЛЕД(A).

СЛЕД(<S>)1	#
СЛЕД(<NEXT>)1
СЛЕД(<USING_LIST>)1	;
СЛЕД(<NEXT_USING>)1
СЛЕД(<CLASS>)1	;
СЛЕД(<CLASS_BODY>)1	}
СЛЕД(<NEXT_BODY>)1
СЛЕД(<DEF>)1	;
СЛЕД(<DEF_LIST>)1
СЛЕД(<NEXT_DEF>)1
СЛЕД(<VAR_LIST>)1	)
СЛЕД(<NEXT_VAR>)1
СЛЕД(<OPER_LIST>)1	}
СЛЕД(<NEXT_OPER>)1
СЛЕД(<OPERATOR>)1	;
СЛЕД(<LET>)1	)
СЛЕД(<EXPR>)1	ID;) < > =
СЛЕД(<OPERATION>)1
СЛЕД(<COND>)1	;)
СЛЕД(<RELATION>)1

 

Шаг 4. Для всех нетерминальных символов A включить во множества СЛЕД(A) множества СЛЕД (В), где B Î СЛЕД(A), если существует правило B=e.

 

СЛЕД(<S>)2	#
СЛЕД(<NEXT>)2
СЛЕД(<USING_LIST>)2	;
СЛЕД(<NEXT_USING>)2
СЛЕД(<CLASS>)2	;
СЛЕД(<CLASS_BODY>)2	}
СЛЕД(<NEXT_BODY>)2
СЛЕД(<DEF>)2	;
СЛЕД(<DEF_LIST>)2
СЛЕД(<NEXT_DEF>)2
СЛЕД(<VAR_LIST>)2	)
СЛЕД(<NEXT_VAR>)2
СЛЕД(<OPER_LIST>)2	}
СЛЕД(<NEXT_OPER>)2
СЛЕД(<OPERATOR>)2	;
СЛЕД(<LET>)2	)
СЛЕД(<EXPR>)2	ID;) < > =
СЛЕД(<OPERATION>)2
СЛЕД(<COND>)2	;)
СЛЕД(<RELATION>)2

 

Шаг 5. Для всех нетерминальных символов A во множество СЛЕД(A) включить множества СЛЕД (В), если существует правило B=aA, a Î (VT È VN).

 

СЛЕД(<S>)3	#
СЛЕД(<NEXT>)3	#
СЛЕД(<USING_LIST>)3	;
СЛЕД(<NEXT_USING>)3	;
СЛЕД(<CLASS>)3	;
СЛЕД(<CLASS_BODY>)3	}
СЛЕД(<NEXT_BODY>)3	}
СЛЕД(<DEF>)3	;
СЛЕД(<DEF_LIST>)3	;
СЛЕД(<NEXT_DEF>)3	;
СЛЕД(<VAR_LIST>)3	)
СЛЕД(<NEXT_VAR>)3	)
СЛЕД(<OPER_LIST>)3	}
СЛЕД(<NEXT_OPER>)3	}
СЛЕД(<OPERATOR>)3	;
СЛЕД(<LET>)3	)
СЛЕД(<EXPR>)3	ID;) < > =
СЛЕД(<OPERATION>)3	ID;) < > =
СЛЕД(<COND>)3	;)
СЛЕД(<RELATION>)3	;)

 

Шаг 6 Так как множества СЛЕД(А) не изменились на шагах 3,4,5, то закончим.

Построение множества ВЫБОР(n). Для формирования множеств ВЫБОР требуется определить аннулирующие правила. Для этого из общего списка правил исключают правила, содержащие в правых частях хотя бы один терминал. Из оставшихся правил исключают непродуктивные правила, т.е. те правила, которые не порождают цепочки терминалов. Оставшиеся правила будут аннулирующими.

Таблица 3 содержит правила, которые не содержат терминальные символы. Слева – непродуктивные правила. Справа – аннулирующие правила.

 

Таблица 3 – Непродуктивные и аннулирующие правила.

Непродуктивные правила	Аннулирующие правила
(24) <OPER_LIST> -> <OPERATOR> <NEXT_OPER> (43) <COND> -> <EXPR> <RELATION>	(4) <NEXT> -> e (7) <NEXT_USING> -> e (11) <NEXT_BODY> -> e (19) <NEXT_DEF> -> e (23) <NEXT_VAR> -> e (26) <NEXT_OPER> -> e (41) <OPERATION> -> e (47) <RELATION> -> e

 

Множества ВЫБОР определим на основании следующих выражений: для не аннулирующих правил - ВЫБОР(n) = ПЕРВ(n), для аннулирующих правил - ВЫБОР(n) = СЛЕД(A), где А – нетерминальный символ в левой части правила n.

 

ВЫБОР(1)	using
ВЫБОР(2)	public
ВЫБОР(3)	;
ВЫБОР(4)	#
ВЫБОР(5)	ID
ВЫБОР(6)	.
ВЫБОР(7)	;
ВЫБОР(8)	class
ВЫБОР(9)	public
ВЫБОР(10)	;
ВЫБОР(11)	}
ВЫБОР(12)	uint
ВЫБОР(13)	bool
ВЫБОР(14)	const
ВЫБОР(15)	ID
ВЫБОР(16)	(
ВЫБОР(17)	,
ВЫБОР(18)	=
ВЫБОР(19)	;
ВЫБОР(20)	ID
ВЫБОР(21)	,
ВЫБОР(22)	=
ВЫБОР(23)	)
ВЫБОР(24)	for break continue write read ID
ВЫБОР(25)	;
ВЫБОР(26)	}
ВЫБОР(27)	for
ВЫБОР(28)	break
ВЫБОР(29)	continue
ВЫБОР(30)	write
ВЫБОР(31)	read
ВЫБОР(32)	ID
ВЫБОР(33)	=
ВЫБОР(34)	*
ВЫБОР(35)	/
ВЫБОР(36)	(
ВЫБОР(37)	ID
ВЫБОР(38)	NUM
ВЫБОР(39)	+
ВЫБОР(40)	-
ВЫБОР(41)	ID;) < > =
ВЫБОР(42)	(
ВЫБОР(43)	(ID NUM
ВЫБОР(44)	>
ВЫБОР(45)	<
ВЫБОР(46)	=
ВЫБОР(47)	;)