Объяснение на этой первой функции

Question

LL (1) Грамматика:

(1) Var -> ID DimList 
(2) DimList -> ε DimList' 
(3) DimList' -> Dim DimList' 
(4) DimList' -> ε 
(5) Dim -> [ CONST ] 

И, в сценарии, что я читал, это говорит о том, что функция FIRST(ε DimList') дает {#, [}. Но как?

Я думаю, что, так как правая часть (2) начинается с ε, он пропускает эпсилон и принимает FIRST(DimList') что, учитывая (3) и (5), равный {[}, но и, в силу (4) , принимает FOLLOW(DimList'), который составляет {#}.

Другой способ это может быть в том, что, так как (2) начинается с ε он пропускает эпсилон и принимает FIRST(DimList') НО принимает FOLLOW (DimList) из (2) ...

Первый один имеет больше смысла для меня , хотя я все еще в процессе изучения основ грамматики LL (1), поэтому я был бы признателен, если кто-то найдет время, чтобы сделать это ясно, спасибо.

EDIT: И, конечно, это может быть так, что ни одно из них не является истинным.

Answer 1

Обычное определение первой функции приведет к FIRST(Dimlist) (или, если угодно, FIRST(ε Dimlist') быть {ε, [} & эпсилон;. В FIRST(ε Dimlist'), потому что оба & эпсилон;. И Dimlist' являются обнуляемым [ является элементом, потому что это может быть первым символ в выводе ε Dimlist, который является таким же, как говорят, что это может быть первым символом в выводе Dimlist'

Другой способ сказать это, что:.

FIRST(ε Dimlist' #) = {#, [}

Мы обычно затем определим функцию PREDICT:

PREDICT(ω) = FIRST(ω FOLLOW(ω))

и мы можем видеть, что

PREDICT(Dimlist) = FIRST(Dimlist FOLLOW(Dimlist)) = {#, [}

Здесь FIRST(ω) есть множество строк терминалов (длины ≤ 1) который может появиться в начале вывода ω, тогда как PREDICT(ω) представляет собой набор строк терминалов (от len gth ≤ 1), который может присутствовать на входе, когда возможен вывод ω.

Это не редкость путать FIRST и PREDICT, но лучше держать разницу прямо.

Обратите внимание, что все эти функции могут быть обобщены в строки максимальной длины k, которые, как правило, написанные FIRSTk, FOLLOWk и PREDICTk, а также определение PREDICTk аналогичен приведенному выше:

PREDICTk(ω) = FIRSTk(ω FOLLOWk(ω))