Теоретический вопрос про разработку языков программирования

← →
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]

Понял, спасибо

> Почему именно она превой?

Чтобы доказать выводимость выражения, надо предоставить его вывод. Когда ты упрощаешь выражения по математике, тебя же никто не спрашивает, почему ты сгруппировал первое и третье слагаемое, хотя следующее по порядку второе?

Теоретический вопрос про разработку языков программирования Найти похожие ветки