Приведение КС-грамматики.

[main.c]

Есть вот такая грамматика:
$E \to (E)E \; | \; \{E\}E \; | \;\varnothing$
Насколько я знаю, есть теорема, что любая КС-грамматика пожет быть приведена к эквивалентной КС-грамматике не содержащей правил, порождающих пустую цепочку. Но я никак не могу разобраться в алгоритме приведения. Просьба объяснить на этом пример, как это делается.

[iifat]

Насколько я помню, просто подставляем эту пустую цепочку, да и всё.
$E \to (E)E \; | \; \{E\}E \; | \;()E \; | \;(E) \; | \;() \; | \; \{\}E \; | \; \{E\} \; | \; \{\}$

[main.c]

iifat в сообщении #976807 писал(а):

Насколько я помню, просто подставляем эту пустую цепочку, да и всё.
$E \to (E)E \; | \; \{E\}E \; | \;()E \; | \;(E) \; | \;() \; | \; \{\}E \; | \; \{E\} \; | \; \{\}$

Я немного не так грамматику составил, надо было вот так:
$E \to (E) \; | \; \{E\} \; | \; EE \; | \; \varnothing$
Итак, подставляю и получается:
$E \to (E) \; | \; \{E\} \; | \; () \; | \; \{\} \; | \; EE$
Так, остаётся избавиться от левой рекурсии.

[iifat]

Хм. А вот это уже на редкость неоднозначная грамматика. $E \to EE \; | \; \varnothing$ даёт бесконечное число деревьев вывода пустой строки (да и любой другой).
Вообще, я, кажется, несколько подзабыл, либо полностью избавиться таки не удастся, либо не полное избавление от правил достигается. Если приведённые правила — это вся грамматика, то уж хоть одно $E\to\varnothing$ останется, поскольку иначе пустой строки не получить. Напомните название алгоритма либо дайте ссылку, пожалуйста. Гляну поконкретнее.

[main.c]

iifat в сообщении #976828 писал(а):

Хм. А вот это уже на редкость неоднозначная грамматика. $E \to EE \; | \; \varnothing$ даёт бесконечное число деревьев вывода пустой строки (да и любой другой).
Вообще, я, кажется, несколько подзабыл, либо полностью избавиться таки не удастся, либо не полное избавление от правил достигается. Если приведённые правила — это вся грамматика, то уж хоть одно $E\to\varnothing$ останется, поскольку иначе пустой строки не получить. Напомните название алгоритма либо дайте ссылку, пожалуйста. Гляну поконкретнее.

http://mathhelpplanet.com/static.php?p=privedennaya-forma-ks-grammatiki

-- 11.02.2015, 16:27 --

Кажется разобрался:
$E \to (E) \; | \; \{E\} \; | \; () \; | \; \{\} \; | \; EE$
Эту грамматику мы заменяем этой:
$E \to (E) \; | \; \{E\} \; | \; () \; | \; \{\}$
$E \to (E)D \; | \; \{E\}D \; | \; ()D \; | \; \{\}D \;$
$D \to ED \; | \; E$

Или я что-то напутал?

[iifat]

Точно, одно правило таки остаётся.

main.c в сообщении #976821 писал(а):

остаётся избавиться от левой рекурсии

Опять же, подстановка, помнится.
$E \to (E) \; | \; \{E\} \; | \; () \; | \; \{\} \; | \; (E)E \; | \; \{E\}E \; | \; ()E \; | \; \{\}E$

-- 12.02.2015, 00:40 --

main.c в сообщении #976830 писал(а):

Или я что-то напутал?

По-моему, да. ()()(), например, в исходной не выводится, в отличие от. Ну и, напоминаю, одно правило $E\to\varnothing$ остаётся. Например, в форме $S\to\;E|\varnothing$ плюс правило $E\to\dots$

[main.c]

Может я бьюсь головой об стенку? Для правильного скобочного выражения можно построить LL(1)-грамматику или нет?

[iifat]

Разумеется. Вы хотите скобочное с двумя видами скобок? А кроме скобок чего-нить будет?

[main.c]

iifat в сообщении #976874 писал(а):

Разумеется. Вы хотите скобочное с двумя видами скобок? А кроме скобок чего-нить будет?

Я ходил вокруг да около)) Вот же она:
$E \to (E)E \; | \; \{E\}E \; | \; \varnothing$
На пустой терминальный символ переходим во всех оставшихся случаях. Я парсить программой собираюсь и меня почему-то переклинило, что грамматика не должна порождать пустую цепочку. Ну разве что только в начале. Ну ладно, зато немного освежил в памяти теорию формальных языков. Спасибо.

[iifat]

Подозреваю, не совсем ещё.
ll(1) — это для нисходящего метода. То бишь, есть нетерминал в частично разобранной строке, есть начало соответствующей подстроки и по первому символу должно однозначно определяться правило, по которому его раскрывать. То бишь, вот такое
$E\to()|(E)$
надо преобразовывать. Например, вот так:
$E\to(F$
$F\to)\;|\;E)$