OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 22:53

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8, 9  След.
Автор Сообщение
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 17:22 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Valery Solovey писал(а):
А разве id - нетерминал? Чёрт, забыл.
С точки зрения сканера id - нетерминал, а с точки зрения парсера id - терминал.
Я уже советовал выше, перечитайте страницу 30. :wink:


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 01 Февраль, 2010 18:36 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
igor писал(а):
можно продолжить обсуждение в этой теме (на усмотрение модераторов)
Моё мнение такое: когда товарищ Galkov решил переключиться с лексики Оберона на синтаксис РБНФ, ему стоило создать новую тему.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 13:51 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Valery Solovey писал(а):
Приравнивать входные символы нельзя. Просто, factor - это другой Уровень. Его входными элементами являются сами id. Целиком, а не его составляющие.

Еще как ЗЯ :)
Просто по определению, FIRST и FOLLOW - это множества именно терминальных символов. Попробую подтвердить, что я не одинок в этом мнении: у Вирта в разделе 7.2 (стр.57-58) перечислены эти множества для нетерминалов, невзирая на их уровень.
    [offtop] Правда, первая же строчка: FIRST(selector)={"." "[" "*"} - ставит в тупик. Но, в качестве рабочей гипотезы, я отношу это к опечаткам: вместо звездочки должен быть символ "пустышки"[/offtop]
Да, Вирт не определил толком эти множества. Считая, видимо, это не самым сложным для самостоятельного размышления. И серьезных оснований спорить с ним по этому поводу у меня просто нет.
Ну ладно, попробую (это значит, что излагаю лишь мысли, которые можно критиковать) самостоятельно, не заглядывая в буквари...

FIRST значительно проще, он определен для произвольного выражения (что собственно и нарисовано в правилах генерации кода по регулярным выражениям на стр.29). Будем пробовать "конструктивное" определение:
1) Для терминального символа это просто множество из одного элемента - того самого терминального символа
2) Для круглых скобок тождественное равенство: FIRST((exp)) = FIRST(exp)
3) Для альтернативы: FIRST(exp1|exp2) = FIRST(exp1)+FIRST(exp2)
4) Для "повторения" и "необязательности": FIRST({exp}) = FIRST([exp]) = FIRST(exp)+NULL
5) Для конкатенации: FIRST(exp1 exp2) = FIRST(exp1) + (if NULL in exp1 then FIRST(exp2))
- ну и как бы альтернативы и конкатенации считаем левоассоциативными. Или право... никак пока в толк не возьму разницы...
Ну вот, кто нам мешает определить FIRST для "чего угодно" - спускаемся вниз по уровням до терминалов. А у нас в данный момент это получатся letter, digit и char - которые уже сами определены где-то (нет смысла заморачиваться с конкретными записями, все более или менее очевидно) как множества входных символов. Буковок, грубо говоря

Попробуем поразмышлять про FOLLOW... Тут мне ничего в голову не приходит, как сказать, что сие определено только для нетерминалов, для которых я могу изучить вхождение в наш синтаксис, и там уже смотреть first того, что за ним следует. В общем, ПОЙДЕМ ЛОГИЧЕСКИМ ПУТЕМ (надеюсь: пойдем вместе)
Ну, скажем, нетерминал expression... Видим вхождение его в левую часть определения production, и понимаем, что после epression МОЖЕТ следовать ".". Первое вхождение в левую часть определения factor: может ли входить в FOLLOW(expression) символ ")" ??? Может, ОНИ ОБА МОГУТ ((дальше, как Вы помните, следует торжественное рукопожатие))
Вот так и получается, что если начать с пустого множества FOLLOW, и на каждом шаге добавлять first того, что за ним следует, то получится, что FOLLOW(expression)={"." ")" "]" "}"}
Остался последний вопрос: а если ничего не следует ??? Мне представляется логичным такой ответ: так не бывает, следует, и это множество FOLLOW для того нетерминала, в левой части которого мы и копаемся
Т.е., в отличие от FIRST мы будем подниматься "вверх по уровням", пока не дойдем до стартового символа
Тут для синтаксического анализатора все понятно. Ничего за стартовым символом не следует.
А если мы шутим с написанием такого для лексера (упомянутая igor-ем стр.30), то фигня получается. Фиг его знает, что следует за нетерминалом symbol, следовательно - мы не можем определить множества FOLLOW, следовательно - проверить правила детерминированности Вирта, следовательно - написать код лексера.
Не, написать-то можно. Говорить, что все написано по правилам (типа: "да все следует из синтаксиса!!!") - НЕЛЬЗЯ.
    [offtop] типа: igor, привет! Мы не только перечитали стр.30, но кое-что для нее проверили :D [/offtop]

Ну как, нам удалось пройти до конца логическим путем вместе ??? :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 15:35 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Peter Almazov писал(а):
В общем, тут лексика тоже должна быть отделена, иначе сам черт ногу сломит

Золотые слова :!: :D
Дополнительно отметил бы, что просто добавление {blank} в хвост или начало определиния id - никак не спасут отца русской демократии.
И хотелось бы акцентировать внимание на том, что "тут тоже" - мне не представляется до конца правильным :)
Мне думается, что ВЕЗДЕ. Грубо говоря: мухи - отдельно, котлеты - отдельно.
Иначе - всегда будут такие сюрпризы.
И прежде всего - в определении синтаксиса Оберона. Смотрим, и видим первые две (для Оберон-0) строки
Код:
   ident    = letter {letter | digit}.
   integer  = digit {digit}.
Это же ровно те же яйца, только в профиль!!!
И чего у нас получается ??? Здесь играть, здесь не играть, а здесь рыбу заворачивали ???
Посмотрите на множества FISRT и FOLLOW на стр.57-58 - они там идут ведь как терминалы. И получается все в порядке. Естественно.
И это вовсе не вопрос "студент должен додумать сам", а вопрос аккуратности. Да, пусть (предположим) студент сам додумывает про FIRST и FOLLOW. Но с ними-то все в книге предельно аккуратно (мне пока именно так кажется а опечатки - не считаются).
А здесь - не согласный я :)

А с другой стороны, куды девать эти предложения, если в книге про категорическое (на чем я уже долго настаиваю) выделение лексера из общего синтаксиса - скромно умалчивается :(

Мое предложение такое:
  1. Забыть как страшный сон про объединение патернов лексера с синтаксисом
  2. Пусть даже только для себя, но определить таки, что такое лексер (типа: делает то-то, и то-то), и какими (и как - очень важно) патернами он при этом пользуется.
  3. Записать наконец в этом формализме некий Лексер. Например для Оберон[-0]
  4. И совершенно формальными методами (теми же правилами Вирта, или их адаптацией) проверить наконец-то детерминированность этого несчастного синтаксиса.

А то иначе - сил моих бабских больше нету :lol:
Ну вот Игорь категорически утверждает про то, что лексер в каждый момент знает какую лексему он рассматривает
Мы ему показываем пальцем на разные лексемы, начинающиеся с одинаковых символов
Нет, говорит он, они принадлежат одному классу лексем (не открывая нам глаза на определение класса)
Ну спрошу я его, к примеру, чем же таким этот "класс" отличается от нескольких фишек на диаграмме переходов НКА
А он мне, видимо, скажет, что не видит особого смысла рисовать НКА, когда можно нарисовать ДКА
А единого регулярного выражения (он же - патерн) для лесем integer и CharConstant (начинающихся с одного символа) - так и не нарисовал. А комментарий - так это вообще не лексема, а безобразие какое-то
Потому что тот факт, что мы говорим про Оберон, уже как-то и подзабылся :)

Надо же как-то кончать эту сказку про белого бычка, выходить как-то из замкнутого круга :D


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 16:02 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Согласен со всем.
И даже программа из 4 пунктов совместными усилиями практически выполнена.
А "этот несчастный синтаксис" - недетерминирован.
А дальше-то что?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 17:41 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Peter Almazov писал(а):
Согласен со всем.

не согласен я. С обоими.
Цитата:
А дальше-то что?

Да что тут предлагать?.. А то пишут, пишут... Конгресс, немцы какие-то... Голова пухнет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 18:10 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Давайте разберемся.
Термины "Регулярный язык с детерминированной лексикой" и "Регулярный язык с недетерминированной лексикой" (ужасно выглядит, согласен) принадлежат Вирту.
Первый означает, что при реализации распознающего автомата обязательно получится ДКА.
Второй - все остальное.

Возьмем такой регулярный язык
{ > | >= }

Для него можно построить НКА, т.к. из состояния, где мы принимаем символ > к двум разным вершинам ведут 2 дуги, обе с меткой >.
По определению, это - "Регулярный язык с недетерминированной лексикой".

В чем заключаются возражения?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 18:39 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
Galkov писал(а):
Мне представляется логичным такой ответ: так не бывает
Ничего себе аргумент...

Если для factor и id множество FIRST пересекается (на основании того, что factor определяется через id), то лексический анализатор и вправду недетерминирован. Однако, я с этой идеей (пересечением FIRST) не согласен. Возможно, когда я прочту книгу, мой взгляд на идею изменится, но сейчас я не вижу причин считать, будто множество начальных символов id является ещё и множеством начальных символов factor.

Galkov писал(а):
Говорить, что все написано по правилам (типа: "да все следует из синтаксиса!!!") - НЕЛЬЗЯ.

Согласен.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 20:35 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Peter Almazov писал(а):
Термины "Регулярный язык с детерминированной лексикой" и "Регулярный язык с недетерминированной лексикой" (ужасно выглядит, согласен) принадлежат Вирту.
Это из "Построения компиляторов"? ... в любом случае, дайте ссылку, пожалуйста.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 21:37 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Книга осталась на работе.
Посмотрите, например, что предлагается сделать в упр. 4.2:
"Using these sets, verify that EBNF is deterministic."


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 21:38 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
А я с собой ношу :D

Там такого прямого указания НЕТ
Там примерно такая последовательность изложения (стр.28-29):
  1. Определяются регулярные языки. Хоть коротко, но точно, имхо
  2. Сообщается, что для их распознавания достаточно иметь конечный автомат (никаких намеков на НКА или ДКА)
  3. Следом, единственное упоминание на то, что в природе существует недетерминированность, выглядит так:
    Цитата:
    Если очередное состояние уникально, то машина состояний является детерминированной, иначе недетерминированной
  4. Далее приводятся правила построения кода из регулярного выражения
  5. И уже потом - правила, лишь при выполнении которых возможно таковое построение кода. Магический термин все таки употреблен: "возможно лишь при условии детерминированного синтаксиса"
Т.е., прямого указания нет. А косвенное (за которое еще нужно догадаться) - есть
Самое главное косвенное указание: правила Вирта выделяют из всех регулярных синтаксисов, только ту ее часть, которую можно кодировать напрямую (названо - прозрачно), и этот синтаксис явно назван детерминированным.
Но мы должны догадаться, что оставшаяся часть - это недерминированные языки, и для них тоже кодирование вполне возможно, хотя и менее прозрачно.

Мне лично кажется, что более понятной была бы иная последовательнось изложения:
  1. Определение регулярного синтаксиса
  2. Сообщение, что для их распознавания достаточно конечного автомата, который может быть как ДКА, так и НКА
  3. Правила Вирта, которые разделяют языки на те, которым нужен НКА (недетерминированные), и на те - которым достаточно ДКА (детерминированные)
  4. И вот для детерминированных - вот Вам правила генерации кода. И мы, типа, будем их успешно использовать далее. Наши победили

Но это уже - так, ИМХО


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 23:07 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Galkov писал(а):
Правила Вирта, которые разделяют языки на те, которым нужен НКА (недетерминированные), и на те - которым достаточно ДКА (детерминированные)


Боюсь, таких "правил Вирта" не существует. ;) Разделять эти языки бессмысленно, ибо они суть одно и то же.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 02 Февраль, 2010 23:23 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
igor писал(а):
А теперь я жду объяснений. В чём был прикол?
Я серьёзно. Может я смотрю на всё это уже замыленными глазами и не вижу очевидное.
Прошу тогда помочь мне увидеть это нарушение условия детерминированности.


Объяснение первое: Вы решили не ту задачку, которая предложена в упражнении 4.2!!!
Есть формальное определение синтаксиса, и работать надо с ним. Применение "здравого смысла" - это же подгонка под ответ.
Давайте так... Есть у Вирта упражнение 5.1 (которое тоже приведено, чтобы его решали, извлекая для себя при этом новые знания :D )
Цитата:
Расширьте программу распознавания РБНФ таким образом, чтобы она генерировала (1) список терминальных символов, (2) список нетерминальных символов и (3) множества начальных (first) и последующих (follow) символов для каждого нетерминального символа
- и все это (обращаю внимание!!!) только исходя из текста "программы", которая в нашем случае - тот самый формальный синтаксис.
Спрашивается, какой список терминалов и нетерминалов выдаст эта программа :?:
Вовсе не тот, что у Вас.
Но мы же взрослые люди, и понимаем, что "здравый смысл", побудивший Вас выкинуть две последние строчки из синтаксиса - действительно является здравым.
Иначе ответ не сойдется.
В этом и прикол: стоит пристегнуть патерны лексики к синтаксису - и получится полный кердык.
И это не мой ведь прикол, это упражнение Вам дал Вирт. Возможно (точно я не знаю) для того, чтобы мы понимали, чего будет, если свалить все в одну кучу.

Объяснение второе: выполнение Вами упражнения, хоть и с другими условиями, имело и так великую пользу, поскольку продемонстрировало, что мы с Вами по разному считаем FOOLOW. Вот я уже два раза по шагам рассказывал как я его считаю, а Вы - нет. А результаты не сходятся.
При этих "объяснениях" выше, я мимоходом посчитал FOLLOW(expression) - сравните, не совпадает ведь :(
Но это же не дает нам возможность двигаться дальше :!:
Предположим что Вы согласительс п.1 "программы", что мух с котлетами смешивать нельзя. Если не согласитесь, то мы попросим Вас посчитать таки нашу задачу без применения "здравого смысла" - ибо через руки доходит лучше всего.
Но Вы ведь все равно не согласитесь с п.2, я же знаю :) И даже знаю как Вы будете не соглашаться: сошлетесь на стр.30, и скажите: "вот же symbol, из него все ясно, все детерминировано, и т.п."
На возражения, что невозможно определить FOLLOW(symbol) - скажите: "да вот он у меня!!!".
А ответы-то у нас разные...
igor, ну критикуйте мое определение для follow, ну все же я рассказал, что мог и умел...
Разве-что одно: нафига мне нужен этот follow...
Он мне нужен, когда при применении 3-го правила эти скобки находятся в конце. Например для factor{factor}
С чем мне сравнивать first от второго factor-а ??? Я сравниваю с follow(term).
А Вы с чем ??? Если ни с чем, то нафиг нам вообще нужен это дурацкий follow ...
Разобраться с этим надо всенепременно. Иначе - клинч.


igor писал(а):
PS: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить
А чего там рисунки :D
Есть у Вирта следующее упражнение - 4.3
Это уже те же рисунки, но воплощенные в код (кстати говоря, именно эту программу предлагает расширить Вирт в упражнении 5.1). И это уже очень интересно.
Почти боевой бизон :!:
При этом, с целью практичности, можно расширить РБНФ. Например так, как Вы и предлагали: символом char в стиле Оберон, и "диапазоном"

P.S. две точки - вот Вам и недетерминированность, получится. А если бы их было три, получилась бы еще и "откатность" - ужас

P.P.S. Выполненное упражнение 5.1 позволило бы и "третейское судейство": запузыриваешь в нее синтаксис Оберон-0, и сравниваешь результаты с приведенными на ст.57-58


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 02:26 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Присоединяюсь к сказанному выше Trurl-ем. Язык --- множество предложений, порождаемых грамматикой(ами). Синтаксис в последних может быть детерминирован/недетерминирован.

Galkov писал(а):
Самое главное косвенное указание: правила Вирта выделяют из всех регулярных синтаксисов, только ту ее часть, которую можно кодировать напрямую (названо - прозрачно), и этот синтаксис явно назван детерминированным.
Но мы должны догадаться, что оставшаяся часть - это недерминированные языки, и для них тоже кодирование вполне возможно, хотя и менее прозрачно.
Я понимаю так: для кодирования недетерминированного синтаксиса его надо преобразовать в детерминированный (если возможно).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 02:28 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Т.е. имеется в виду, что детерминированный синтаксис - это такой, по которому не получится при всём желании НКА?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 09:03 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Да


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 09:22 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Для тех, кому лень врубаться, и кому режет глаз то, что лексику Оберона называют недетерминированной (посягают на самое святое!!!) подчеркну, что речь идет о грамматике для лексического анализатора.

Вот маленький пример.
Регулярный язык для лексического анализатора (сканера):
{ > | >= } – недетерминированный
Регулярный язык для синтаксического анализатора (парсера):
{ ЗнакБольше | ЗнакБольшеИлиРавно } - вполне себе детерминированный.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 09:29 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Такой момент...
Для Оберона Вирт формально определяет грамматику для синтаксического разбора (для парсера). (Для заметки: там ">", ">=" являются разными "буквами" алвафита.) Сканер частично определяется продукциями, частично неформальными правилами --- см. в конце 7.1.

Поскольку формально синтаксис сканера не дан, как можно говорить о его детерминированости?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 09:34 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Peter Almazov писал(а):
Регулярный язык для синтаксического анализатора (парсера)
Этот язык не регулярный.

2) Peter Almazov, хотелось бы вернуться к вопросу: viewtopic.php?p=41707#p41707. Указанные Вами определения даны у Вирта? Или мы о них сами "догадываемся" навроде того, как описывает Galkov тут: viewtopic.php?p=41711#p41711

Это вообще-то вещи разные.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 03 Февраль, 2010 09:55 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Евгений Темиргалеев писал(а):
Peter Almazov писал(а):
Регулярный язык для синтаксического анализатора (парсера)
Этот язык не регулярный.
А какой же?
Евгений Темиргалеев писал(а):
2) Peter Almazov, хотелось бы вернуться к вопросу: viewtopic.php?p=41707#p41707. Указанные Вами определения даны у Вирта? Или мы о них сами "догадываемся" навроде того, как описывает Galkov тут: viewtopic.php?p=41711#p41711

Это вообще-то вещи разные.
Сами догадываемся, Galkov полностью раскрыл тему.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8, 9  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB