Форум: "Прочее";
Текущий архив: 2009.05.24;
Скачать: [xml.tar.bz2];
ВнизТеоретический вопрос про разработку языков программирования Найти похожие ветки
← →
Int23 (2009-03-20 09:17) [0]В институте я прогуливал этот курс, а вот недавно купил 2 издание драконов. Во 2 главе описаны контекстно-свободные грамматики и дано упражение. Есть грамматика со след правилами
S->SS+|SS*|a
Нужно доказать, что выражение aa+a* выводимо по данной грамматике. Интуитивно понимаю, что надо брать S->SS*. НО как узнать, что надо брать именно её первый раз. Выражение может быть не столь очевидным и я могу взять S->SS+ ведь она стартовая продукция. Просветите, плиз
← →
oxffff © (2009-03-20 09:33) [1]
> Нужно доказать
Вообще нужно показать, а не доказать. :)
S->SS*-> SS+S*->aa+a*
← →
Int23 (2009-03-20 09:35) [2]Ну я так интуитивно понимаю а почему первой вы берёте S->SS*. Почему именно она превой?
← →
oxffff © (2009-03-20 09:40) [3]
> Почему именно она превой?
Об этом ты узнаешь в следующих главах.
Причина в том,что при выборе любой другой продукции нельзя получить * в конце.
← →
Int23 (2009-03-20 09:49) [4]т.е. перед нами левосторонняя продуктция и мы в выражении всегда смотрим на самый правый символ?
← →
oxffff © (2009-03-20 09:51) [5]
> Int23 (20.03.09 09:49) [4]
Она леворекурсивная.
А терминалы в процессе спуска появляются справа налево.
← →
Int23 (2009-03-20 09:54) [6]Понял, спасибо
← →
Mystic © (2009-03-20 13:27) [7]> Почему именно она превой?
Чтобы доказать выводимость выражения, надо предоставить его вывод. Когда ты упрощаешь выражения по математике, тебя же никто не спрашивает, почему ты сгруппировал первое и третье слагаемое, хотя следующее по порядку второе?
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2009.05.24;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.005 c