Объяснение этой ПЕРВОЙ функции

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), поэтому я был бы признателен, если бы кто-то нашел время, чтобы прояснить это, спасибо.

РЕДАКТИРОВАТЬ: И, конечно, может быть, что ни то, ни другое не верно.


parsing grammar ll programming-languages context-free-grammar
person TedK.    schedule 12.08.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

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

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

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

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

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

person rici    schedule 13.08.2013