Как найти FIRST если справа в правиле нет ничего (эпсилон) в каноническом LR парсере (4.7.2 в драконьей книге) ?
Думал нужно заменить на FOLLOW но после прочтения драконьей книги в обще запутался...

Как я поннял почитав книгу:
Е=e
FIRST(Е)=e
И в пунктах LR парсера терминальный символ становится e ...
и что с этим делать дальше?

А гдебы почитать про LR парсер и пустые элементы?

Есль кто из знатоков кто знает как LR парсер устроен?

Здравствуйте, VVVa, Вы писали:

VVV>Как найти FIRST если справа в правиле нет ничего (эпсилон) в каноническом LR парсере (4.7.2 в драконьей книге) ?
Значит ничего и не будет. Наличие "пустого правила" скорее как флаг работает, чем регулярный терминал.

VVV>Как я поннял почитав книгу:
VVV>Е=e
VVV>FIRST(Е)=e
VVV>И в пунктах LR парсера терминальный символ становится e ...
VVV>и что с этим делать дальше?
А дальше — зависит от того, что именно вы делаете сейчас. Если генерируете таблицу, то у вас всегда есть возможность свертки по пустому правилу. Если генерируете FOLLOW, то у вас получается ветвление. Пусть есть правило S:=ABC. В этом случае FOLLOW(A) == FIRST(B) если 𝜀 ∉ FIRST(B). А когда 𝜀 ∈ FIRST(B), получаем FOLLOW(A) = FIRST(B) ∪ FIRST(C) — {𝜀} (вычитание эпсилона — чтобы не мешался в таблицах). Похожие ветвления и для FIRST. Есть эквивалентная теория. Можно ввести еще один признак CANBEEMPTY(A), где CANBEEMPTY(E)=true тогда и только тогда, когда существует продукция E=𝜀. CANBEEMPTY(ABC) == CANBEEMPTY(A) & CANBEEMPTY(B) & CANBEEMPTY(C). И предыдущее правило для FOLLOW(A) записывается как FOLLOW(A) == FIRST(B) если не CANBEEMPTY(B) иначе FOLLOW(A) == FIRST(B) ∪ FIRST(C). Видимо, с эпсилон в виде элемента множества авторам было удобнее работать.

Здравствуйте, maxkar, Вы писали:

M>Здравствуйте, VVVa, Вы писали:

VVV>>Как найти FIRST если справа в правиле нет ничего (эпсилон) в каноническом LR парсере (4.7.2 в драконьей книге) ?
M>Значит ничего и не будет. Наличие "пустого правила" скорее как флаг работает, чем регулярный терминал.

VVV>>Как я поннял почитав книгу:
VVV>>Е=e
VVV>>FIRST(Е)=e
VVV>>И в пунктах LR парсера терминальный символ становится e ...
VVV>>и что с этим делать дальше?
M>А дальше — зависит от того, что именно вы делаете сейчас. Если генерируете таблицу, то у вас всегда есть возможность свертки по пустому правилу.
А что 𝜀 можно в таблице оставить (есть и такие LR парсеры)?
M>Если генерируете FOLLOW, то у вас получается ветвление. Пусть есть правило S:=ABC. В этом случае FOLLOW(A) == FIRST(B) если 𝜀 ∉ FIRST(B). А когда 𝜀 ∈ FIRST(B), получаем FOLLOW(A) = FIRST(B) ∪ FIRST(C) — {𝜀} (вычитание эпсилона — чтобы не мешался в таблицах). Похожие ветвления и для FIRST. Есть эквивалентная теория. Можно ввести еще один признак CANBEEMPTY(A), где CANBEEMPTY(E)=true тогда и только тогда, когда существует продукция E=𝜀. CANBEEMPTY(ABC) == CANBEEMPTY(A) & CANBEEMPTY(B) & CANBEEMPTY(C). И предыдущее правило для FOLLOW(A) записывается как FOLLOW(A) == FIRST(B) если не CANBEEMPTY(B) иначе FOLLOW(A) == FIRST(B) ∪ FIRST(C). Видимо, с эпсилон в виде элемента множества авторам было удобнее работать.

На примере этой грамматики
S->X E Z
E->
E->E '1'

Если X терминал то всё работает — а если нет то он даже не сварачивается
FIRST пробовал и раньше находить как Вы сказали (Сначала начальные E потом если есть 𝜀 убираем и добавляем начальные следующего за ним символа Z)
В чем косяк не понимаю ...
Может есть где-нибудь пример с 𝜀 с ручной интерпретацией (в драконьей книге куча но с 𝜀 нету)?

блин у себя ошибку нашел ... разбираюсь ...

Да! Заработало! просто немного ошибся ...