OberonCore https://forum.oberoncore.ru/ |
|
Детерминированность лексики Оберона https://forum.oberoncore.ru/viewtopic.php?f=61&t=2279 |
Страница 5 из 9 |
Автор: | igor [ Понедельник, 01 Февраль, 2010 17:22 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Valery Solovey писал(а): А разве id - нетерминал? Чёрт, забыл. С точки зрения сканера id - нетерминал, а с точки зрения парсера id - терминал.Я уже советовал выше, перечитайте страницу 30. |
Автор: | Евгений Темиргалеев [ Понедельник, 01 Февраль, 2010 18:36 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
igor писал(а): можно продолжить обсуждение в этой теме (на усмотрение модераторов) Моё мнение такое: когда товарищ Galkov решил переключиться с лексики Оберона на синтаксис РБНФ, ему стоило создать новую тему.
|
Автор: | Galkov [ Вторник, 02 Февраль, 2010 13:51 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Valery Solovey писал(а): Приравнивать входные символы нельзя. Просто, factor - это другой Уровень. Его входными элементами являются сами id. Целиком, а не его составляющие. Еще как ЗЯ Просто по определению, FIRST и FOLLOW - это множества именно терминальных символов. Попробую подтвердить, что я не одинок в этом мнении: у Вирта в разделе 7.2 (стр.57-58) перечислены эти множества для нетерминалов, невзирая на их уровень.
Ну ладно, попробую (это значит, что излагаю лишь мысли, которые можно критиковать) самостоятельно, не заглядывая в буквари... 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, следовательно - проверить правила детерминированности Вирта, следовательно - написать код лексера. Не, написать-то можно. Говорить, что все написано по правилам (типа: "да все следует из синтаксиса!!!") - НЕЛЬЗЯ.
Ну как, нам удалось пройти до конца логическим путем вместе ??? |
Автор: | Galkov [ Вторник, 02 Февраль, 2010 15:35 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Peter Almazov писал(а): В общем, тут лексика тоже должна быть отделена, иначе сам черт ногу сломит Золотые слова Дополнительно отметил бы, что просто добавление {blank} в хвост или начало определиния id - никак не спасут отца русской демократии. И хотелось бы акцентировать внимание на том, что "тут тоже" - мне не представляется до конца правильным Мне думается, что ВЕЗДЕ. Грубо говоря: мухи - отдельно, котлеты - отдельно. Иначе - всегда будут такие сюрпризы. И прежде всего - в определении синтаксиса Оберона. Смотрим, и видим первые две (для Оберон-0) строки Код: ident = letter {letter | digit}. Это же ровно те же яйца, только в профиль!!!integer = digit {digit}. И чего у нас получается ??? Здесь играть, здесь не играть, а здесь рыбу заворачивали ??? Посмотрите на множества FISRT и FOLLOW на стр.57-58 - они там идут ведь как терминалы. И получается все в порядке. Естественно. И это вовсе не вопрос "студент должен додумать сам", а вопрос аккуратности. Да, пусть (предположим) студент сам додумывает про FIRST и FOLLOW. Но с ними-то все в книге предельно аккуратно (мне пока именно так кажется а опечатки - не считаются). А здесь - не согласный я А с другой стороны, куды девать эти предложения, если в книге про категорическое (на чем я уже долго настаиваю) выделение лексера из общего синтаксиса - скромно умалчивается Мое предложение такое:
А то иначе - сил моих бабских больше нету Ну вот Игорь категорически утверждает про то, что лексер в каждый момент знает какую лексему он рассматривает Мы ему показываем пальцем на разные лексемы, начинающиеся с одинаковых символов Нет, говорит он, они принадлежат одному классу лексем (не открывая нам глаза на определение класса) Ну спрошу я его, к примеру, чем же таким этот "класс" отличается от нескольких фишек на диаграмме переходов НКА А он мне, видимо, скажет, что не видит особого смысла рисовать НКА, когда можно нарисовать ДКА А единого регулярного выражения (он же - патерн) для лесем integer и CharConstant (начинающихся с одного символа) - так и не нарисовал. А комментарий - так это вообще не лексема, а безобразие какое-то Потому что тот факт, что мы говорим про Оберон, уже как-то и подзабылся Надо же как-то кончать эту сказку про белого бычка, выходить как-то из замкнутого круга |
Автор: | Peter Almazov [ Вторник, 02 Февраль, 2010 16:02 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Согласен со всем. И даже программа из 4 пунктов совместными усилиями практически выполнена. А "этот несчастный синтаксис" - недетерминирован. А дальше-то что? |
Автор: | Trurl [ Вторник, 02 Февраль, 2010 17:41 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Peter Almazov писал(а): Согласен со всем. не согласен я. С обоими. Цитата: А дальше-то что? Да что тут предлагать?.. А то пишут, пишут... Конгресс, немцы какие-то... Голова пухнет. |
Автор: | Peter Almazov [ Вторник, 02 Февраль, 2010 18:10 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Давайте разберемся. Термины "Регулярный язык с детерминированной лексикой" и "Регулярный язык с недетерминированной лексикой" (ужасно выглядит, согласен) принадлежат Вирту. Первый означает, что при реализации распознающего автомата обязательно получится ДКА. Второй - все остальное. Возьмем такой регулярный язык { > | >= } Для него можно построить НКА, т.к. из состояния, где мы принимаем символ > к двум разным вершинам ведут 2 дуги, обе с меткой >. По определению, это - "Регулярный язык с недетерминированной лексикой". В чем заключаются возражения? |
Автор: | Valery Solovey [ Вторник, 02 Февраль, 2010 18:39 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Galkov писал(а): Мне представляется логичным такой ответ: так не бывает Ничего себе аргумент...Если для factor и id множество FIRST пересекается (на основании того, что factor определяется через id), то лексический анализатор и вправду недетерминирован. Однако, я с этой идеей (пересечением FIRST) не согласен. Возможно, когда я прочту книгу, мой взгляд на идею изменится, но сейчас я не вижу причин считать, будто множество начальных символов id является ещё и множеством начальных символов factor. Galkov писал(а): Говорить, что все написано по правилам (типа: "да все следует из синтаксиса!!!") - НЕЛЬЗЯ. Согласен. |
Автор: | Евгений Темиргалеев [ Вторник, 02 Февраль, 2010 20:35 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Peter Almazov писал(а): Термины "Регулярный язык с детерминированной лексикой" и "Регулярный язык с недетерминированной лексикой" (ужасно выглядит, согласен) принадлежат Вирту. Это из "Построения компиляторов"? ... в любом случае, дайте ссылку, пожалуйста.
|
Автор: | Peter Almazov [ Вторник, 02 Февраль, 2010 21:37 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Книга осталась на работе. Посмотрите, например, что предлагается сделать в упр. 4.2: "Using these sets, verify that EBNF is deterministic." |
Автор: | Galkov [ Вторник, 02 Февраль, 2010 21:38 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
А я с собой ношу Там такого прямого указания НЕТ Там примерно такая последовательность изложения (стр.28-29):
Самое главное косвенное указание: правила Вирта выделяют из всех регулярных синтаксисов, только ту ее часть, которую можно кодировать напрямую (названо - прозрачно), и этот синтаксис явно назван детерминированным. Но мы должны догадаться, что оставшаяся часть - это недерминированные языки, и для них тоже кодирование вполне возможно, хотя и менее прозрачно. Мне лично кажется, что более понятной была бы иная последовательнось изложения:
Но это уже - так, ИМХО |
Автор: | Trurl [ Вторник, 02 Февраль, 2010 23:07 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Galkov писал(а): Правила Вирта, которые разделяют языки на те, которым нужен НКА (недетерминированные), и на те - которым достаточно ДКА (детерминированные) Боюсь, таких "правил Вирта" не существует. Разделять эти языки бессмысленно, ибо они суть одно и то же. |
Автор: | Galkov [ Вторник, 02 Февраль, 2010 23:23 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
igor писал(а): А теперь я жду объяснений. В чём был прикол? Я серьёзно. Может я смотрю на всё это уже замыленными глазами и не вижу очевидное. Прошу тогда помочь мне увидеть это нарушение условия детерминированности. Объяснение первое: Вы решили не ту задачку, которая предложена в упражнении 4.2!!! Есть формальное определение синтаксиса, и работать надо с ним. Применение "здравого смысла" - это же подгонка под ответ. Давайте так... Есть у Вирта упражнение 5.1 (которое тоже приведено, чтобы его решали, извлекая для себя при этом новые знания ) Цитата: Расширьте программу распознавания РБНФ таким образом, чтобы она генерировала (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: Я пошёл дальше, и нарисовал на листочке графы автоматов, соответствующих этому синтаксису. Если кому то интересно, то я мог бы их оцифровать и выложить А чего там рисунки Есть у Вирта следующее упражнение - 4.3 Это уже те же рисунки, но воплощенные в код (кстати говоря, именно эту программу предлагает расширить Вирт в упражнении 5.1). И это уже очень интересно. Почти боевой бизон При этом, с целью практичности, можно расширить РБНФ. Например так, как Вы и предлагали: символом char в стиле Оберон, и "диапазоном" P.S. две точки - вот Вам и недетерминированность, получится. А если бы их было три, получилась бы еще и "откатность" - ужас P.P.S. Выполненное упражнение 5.1 позволило бы и "третейское судейство": запузыриваешь в нее синтаксис Оберон-0, и сравниваешь результаты с приведенными на ст.57-58 |
Автор: | Евгений Темиргалеев [ Среда, 03 Февраль, 2010 02:26 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Присоединяюсь к сказанному выше Trurl-ем. Язык --- множество предложений, порождаемых грамматикой(ами). Синтаксис в последних может быть детерминирован/недетерминирован. Galkov писал(а): Самое главное косвенное указание: правила Вирта выделяют из всех регулярных синтаксисов, только ту ее часть, которую можно кодировать напрямую (названо - прозрачно), и этот синтаксис явно назван детерминированным. Я понимаю так: для кодирования недетерминированного синтаксиса его надо преобразовать в детерминированный (если возможно).
Но мы должны догадаться, что оставшаяся часть - это недерминированные языки, и для них тоже кодирование вполне возможно, хотя и менее прозрачно. |
Автор: | Илья Ермаков [ Среда, 03 Февраль, 2010 02:28 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Т.е. имеется в виду, что детерминированный синтаксис - это такой, по которому не получится при всём желании НКА? |
Автор: | Peter Almazov [ Среда, 03 Февраль, 2010 09:03 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Да |
Автор: | Peter Almazov [ Среда, 03 Февраль, 2010 09:22 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Для тех, кому лень врубаться, и кому режет глаз то, что лексику Оберона называют недетерминированной (посягают на самое святое!!!) подчеркну, что речь идет о грамматике для лексического анализатора. Вот маленький пример. Регулярный язык для лексического анализатора (сканера): { > | >= } – недетерминированный Регулярный язык для синтаксического анализатора (парсера): { ЗнакБольше | ЗнакБольшеИлиРавно } - вполне себе детерминированный. |
Автор: | Евгений Темиргалеев [ Среда, 03 Февраль, 2010 09:29 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Такой момент... Для Оберона Вирт формально определяет грамматику для синтаксического разбора (для парсера). (Для заметки: там ">", ">=" являются разными "буквами" алвафита.) Сканер частично определяется продукциями, частично неформальными правилами --- см. в конце 7.1. Поскольку формально синтаксис сканера не дан, как можно говорить о его детерминированости? |
Автор: | Евгений Темиргалеев [ Среда, 03 Февраль, 2010 09:34 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Peter Almazov писал(а): Регулярный язык для синтаксического анализатора (парсера) Этот язык не регулярный.2) Peter Almazov, хотелось бы вернуться к вопросу: viewtopic.php?p=41707#p41707. Указанные Вами определения даны у Вирта? Или мы о них сами "догадываемся" навроде того, как описывает Galkov тут: viewtopic.php?p=41711#p41711 Это вообще-то вещи разные. |
Автор: | Peter Almazov [ Среда, 03 Февраль, 2010 09:55 ] |
Заголовок сообщения: | Re: Детерминированность лексики Оберона |
Евгений Темиргалеев писал(а): Peter Almazov писал(а): Регулярный язык для синтаксического анализатора (парсера) Этот язык не регулярный.Евгений Темиргалеев писал(а): 2) Peter Almazov, хотелось бы вернуться к вопросу: viewtopic.php?p=41707#p41707. Указанные Вами определения даны у Вирта? Или мы о них сами "догадываемся" навроде того, как описывает Galkov тут: viewtopic.php?p=41711#p41711 Сами догадываемся, Galkov полностью раскрыл тему.
Это вообще-то вещи разные. |
Страница 5 из 9 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |