2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Приведение КС-грамматики.
Сообщение11.02.2015, 15:44 
Насколько я помню, просто подставляем эту пустую цепочку, да и всё.
$E \to (E)E \; | \; \{E\}E \; | \;()E \; | \;(E) \; | \;() \; | \; \{\}E \; | \; \{E\} \; | \; \{\}$

 
 
 
 Re: Приведение КС-грамматики.
Сообщение11.02.2015, 16:06 
iifat в сообщении #976807 писал(а):
Насколько я помню, просто подставляем эту пустую цепочку, да и всё.
$E \to (E)E \; | \; \{E\}E \; | \;()E \; | \;(E) \; | \;() \; | \; \{\}E \; | \; \{E\} \; | \; \{\}$

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

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

 
 
 
 Re: Приведение КС-грамматики
Сообщение11.02.2015, 16:20 
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$

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

 
 
 
 Re: Приведение КС-грамматики.
Сообщение11.02.2015, 16:33 
Точно, одно правило таки остаётся.
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$

 
 
 
 Re: Приведение КС-грамматики.
Сообщение11.02.2015, 17:43 
Может я бьюсь головой об стенку? :? Для правильного скобочного выражения можно построить LL(1)-грамматику или нет?

 
 
 
 Re: Приведение КС-грамматики.
Сообщение11.02.2015, 17:47 
Разумеется. Вы хотите скобочное с двумя видами скобок? А кроме скобок чего-нить будет?

 
 
 
 Re: Приведение КС-грамматики.
Сообщение11.02.2015, 18:08 
iifat в сообщении #976874 писал(а):
Разумеется. Вы хотите скобочное с двумя видами скобок? А кроме скобок чего-нить будет?

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

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group