Скачать: CL | DM;

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

← →
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 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.008 c