LR(0) граматика

Извор: ВикиЕТФ

LR(0) је скраћеница која значи


Садржај


Дефиниција LR(0) граматика

Безконтексна граматика припада класи LR(0) ако из

Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): 1) <S> \Rightarrow^*_{rm} \quad \alpha <A> a \Rightarrow_{rm} \alpha\beta a


Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): 2) <S> \Rightarrow^*_{rm} \quad \gamma <B> b \Rightarrow_{rm} \alpha\beta c


следи да је Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha <A> c = \gamma <B> b

за произвољне Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.):  \alpha,\beta,\gamma \in V* 
, Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.):  a,b,c \in V_T*
и Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): <A>,<B> \in V_N
крајње десно извођење у нула или више корака (rightmost derivation)

Ако је Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \beta

ручка десне сентенцијалне форме Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta a 
са продукцијом ручке Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): <A> \Rightarrow \beta

, то значи да је Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \beta

ручка са истом продукцијом ручке и за било коју другу десно сентенцијалну форму са истим префиском Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta

.

Овим је обезбеђено да парсер једнозначно одабере редукцију смене Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): <A> \Rightarrow \beta

када се на парсерском стеку нађе префикс Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta
тј. када се на врху стека појави ручка Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \beta

.

Коментар

Кључ за разумевање ове дефиниције је префикс Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta . Ево како.

ручка за десну сентенцијалну форму Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta a 

.

бити ручка и за било коју другу десно сентенцијалну форму са истим префиксом Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta

.

ручка за десно сентенцијалну форму Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta c 

.

Десно сентенцијале форме Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta a

и Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta c 
су у погледу редукције ручке Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \beta
за детектор ручки еквивалентне (када се Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \beta
буде нашло на врху парсерског стека једнозначно се утврђује да треба извршити редукцију без обзира шта је следећи симбол у улазној секвенци).

Како се добија Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha <A>c = \gamma <B> b ?

у Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha\beta c 
добићемо Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha <A>c 

.

. Закључујемо да је Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \alpha <A> c = \gamma <B> b , јер се крајње десним извођењем из обе сентенцијалне форме добијају сентенцијалне форме које су у погледу редукције ручке Рашчлањивање није успело (Недостаје извршна датотека texvc-а. Погледајте math/README за подешавање.): \beta

за детектор ручки еквивалентне.
Личне алатке
Именски простори
Варијанте
Акције
Навигација
Алатке