OberonCore

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

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




Начать новую тему Ответить на тему  [ Сообщений: 180 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 9  След.
Автор Сообщение
СообщениеДобавлено: Суббота, 30 Январь, 2010 10:29 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
igor писал(а):
Galkov писал(а):
Смотрим правил 3 и спрашиваем себя: какие это такие символы "могут следовать за K".
Вот в моем понимание, это ничто иное, как FOLLOW(lexeme)
Похоже, что Вы не правильно истолковали правило 3. Или я не правильно истолковал :) . Но об этом позже (постараюсь завтра, но не обещаю).
Приступаю к обещанному :) .

Peter Almazov писал(а):
У нас обратная задача - решить, порождена ли конкретная лексема ААА123 этой грамматикой. Т.е., внимание!, я принял решение о том, что считать лексемой еще до распознавания.
Совершенно согласен с этим утверждением и приму его в качестве отправного пункта.

Допустим, мы решили записать подряд две лексемы: "name" и "56". То есть изначально именно они являются правильными и вопрос в том, сможет ли лексический анализатор их правильно распознать. Первая лексема относится к классу ident, вторая - к классу number.

Мы рассмотрим два случая: 1) эти лексемы записаны слитно; и 2) записаны раздельно.
Синтаксические формулы для этих двух случаев могут выглядеть так:
  1. letter {letter | digit} digit {digit}
  2. letter {letter | digit} blank digit {digit}
Нас сейчас интересует только первая фигурная скобка и какой символ следует непосредственно за ней. Напомню правило 3:
Вирт писал(а):
K = [exp] | {exp}. Множество начальных символов exp и символов, которые могут следовать за K, не должны пересекаться.
Множество начальных символов exp равно: First(exp) = {"A".."Z", "0".."9"}.
Множество символов, которые могут следовать за K, равно: 1) {"0".."9"}; 2) {20X, 09X, 0DX}.

Что мы видим? То, что в первом случае указанные множества пересекаются (правило 3 нарушается), а во втором случае - не пересекаются (правило 3 соблюдается).

В свете сказанного, следующее утверждение
Galkov писал(а):
... Вот в моем понимание, это ничто иное, как FOLLOW(lexeme)
у меня вызывает недоумение. Никакого FOLLOW(lexeme) правило 3 не рассматривает.

2Galkov. Вы по прежнему считаете лексику Оберонов недетерминированной?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Суббота, 30 Январь, 2010 10:45 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Евгений Темиргалеев писал(а):
В регулярную грамматику, определяющую сканер, не возможно включить вложенные комментарии.
Из любви к истине, я вынужден согласиться с этим утверждением :) .

Вложенные комментарии относятся к классу контестно-свободных языков (а не регулярных), но при этом их синтаксис остаётся детерминированным . Три правила Вирта справедливы и для них (и для синтаксиса всего Оберона в целом).

Спор касался детерминированности, а не принадлежности к классу регулярных языков.


Последний раз редактировалось igor Суббота, 30 Январь, 2010 10:59, всего редактировалось 1 раз.

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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Валерий Лаптев писал(а):
Peter Almazov писал(а):
Так что г-н Galkov прав, правило "самой длинной лексемы" (или не самой длинной) НЕ СЛЕДУЕТ из синтаксиса.
Совершенно верно!
Докажите! Так как сделал это я (см. мой пост выше). Или хотя бы найдите ошибку в моём доказательстве обратного утверждения.


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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Galkov писал(а):
3) [u]Нетерминал ident.
... Применяем правило 2, и получаем, что ...
Правило 2 применять не на чём, в моём файле не встречается конструкция fac0 fac1.


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

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Валерий Лаптев писал(а):
Это правили родилось из практических соображений, причем, насколько я понимаю, в основном при трансляции С++. Ранее я что-то не помню СПЕЦИАЛЬНОГО упоминания об этом правиле.
Скажем так, Дядюшка Ахо ((с) Илья Ермаков, чего-то мне понравилось это словосочетание, если ударение в фамилии делать на последний слог) явно указывает на таковое.
Это уж точно ДО всяких там C++, мне кажется...
А точнее, мне кажется так, что сие используется вообще везде, после появления самого разделения "работы" на лексер/парсер.
Вот коллега Trurl справедливо указал на Фортран, как нарушитель этого правила. А ведь он был сделан раньше фундаментальных трудов по компиляторам... вроде бы.


Последний раз редактировалось Galkov Суббота, 30 Январь, 2010 17:22, всего редактировалось 2 раз(а).

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

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Peter Almazov писал(а):
Отсюда видно, что вопрос о длине лексемы не связан с РБНФ, никак из нее не выводится.
Есть еще более очевидная вещь.
Разные лексемы могут быть и одинаковой длины. Например, "ELSE" и ident с последующим пробелом
Автор имеет право сделать лексику, в которой выбирается именно та альтернатива, на которую он (автор, а не некий тупой компьютер) показал пальцем.
Но совершенно очевидно, что этот выбор никак определяется РБНФ-фомулой
Код:
Start = "ELSE"|"ELSIF"|(letter{letter|digit}).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Суббота, 30 Январь, 2010 19:22 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Евгений Темиргалеев писал(а):
Реализация сканера Оберона объединена с этим "фильтром" в целях оптимизации.
Да, это так. Но наш спор с Галковым не касался реализации сканера, а касался самой лексики Оберонов, является ли она детерминированной.

Другими словами говоря, можно ли задачу разбиения сплошного входного текста на лексемы поручить детерминированному конечному автомату (для вложенных комментариев используется магазинный автомат, но тоже детерминированный)?

Или для этого потребуется инструмент с бОльшим "интеллектом": предпросмотр вперёд более, чем на один символ; откаты и перебор вариантов в поиске правильного; привлечение семантической информации в процессе разбора и т.д.

А Вы тоже считаете (как и Galkov), что лексика Оберонов является недетерминированной?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Суббота, 30 Январь, 2010 22:47 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
igor писал(а):
Но наш спор с Галковым не касался реализации сканера, а касался самой лексики Оберонов, является ли она детерминированной.
Значит не понял вас (обоих), когда выносил тему. Думаю, Вам стоит указать более точный заголовок темы (вместо записанного мною).
igor писал(а):
А Вы тоже считаете (как и Galkov), что лексика Оберонов является недетерминированной?
Мне кажется что можно построить детерминированный магазинный (конечный) автомат, который будет "сканером" для Оберона.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Суббота, 30 Январь, 2010 23:08 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Евгений Темиргалеев писал(а):
Значит не понял вас (обоих), когда выносил тему.
Напомню из-за чего весь сыр-бор:
igor писал(а):
igor писал(а):
И сканер, и парсер во всех Оберонах работают с детерминированным синтаксисом.
Galkov писал(а):
Вот и славненько. Только лексика Оберонов, являясь регулярной, не является детерминированной
И так. Детерминированная ли лексика у Оберонов?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 00:33 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
Евгений Темиргалеев писал(а):
Мне кажется что можно построить детерминированный магазинный (конечный) автомат, который будет "сканером" для Оберона
Кое-что можно сказать и точно.
Например, Lex-формализм может описать комментарий вместе с фокусами INC(level)/DEC(level), который был Вами (по памяти, извините если что) как-то и нарисован.
Скажем так:
Код:
...
<*>"(*"            { level++; BEGIN(comment);   }
<comment>{
  "*)"             { if(--level==0) BEGIN(0);     }
  {sym}            { /*пропуск одного символа*/ }
}
...
И можно точно утверждать, что это все скомпилируется в табличный ДКА, и даже и не магазинный.
И это даже будет работать


Последний раз редактировалось Galkov Вторник, 09 Февраль, 2010 01:58, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 01:53 

Зарегистрирован: Вторник, 11 Август, 2009 11:44
Сообщения: 516
Откуда: Бердск
2igor
Думал я , думал... из-за чего весь сыр-бор.
И показалось мне, что от того, что Вы себе не очень правильно представляете процесс patern matching-а (русский эквивалент как-то сразу в голову не приходит)
Вы все время пытаетесь принять какое-то решение при альтернативе, даже тогда, когда однозначного его не существует.
Поэтому, когда Вам говорят, что у Вас нет основаваний именно для такого решения (например - повторить содержимое данных фигурных скобок), Вы считаете, что я настаиваю на противоположном решении (прекратить повторение), и из такого предположения находите противоречие.
Считая, что нашли противоречие у меня.

Да ни в коем случае :!:
Если у нас нет точных оснований для какого-то однозначного разрешения альтенативы, значит мы должны продолжить изучение ОБОИХ вариантов. Не зная еще какой из них правильный.
Только такая тактика позволит нам обнаружить принадлежность нашего текста множеству фраз, порожденных синтаксисом.

igor, монопольку знаете ??? Там Вы передвигаете фишку по клеточкам. Если Вы будете передвигать ее по диаграмме состояний, то это будет интерпретатор конечного автомата. Каждый раз Вы передвигаете фишку в тот узел, в который ведет стрелочка, помеченная входным символом.
Что делать, когда у нас "нет оснований" передвижения в одном конкретном направлении, и мы должны изучать несколько вариантов ??? Т.е., из одного узла исходят несколько стрелочек с одним символом. Мы должны начать играть несколькими фишками, вот и вся проблема. Несмотря на страшное название - недетерминированность.
На каждом шаге мы должны передвинуть все фишки. Если нет стрелочек с нужной буквой - фишка выкидывается, что означает, что изучаемая нами альтернатива приказала долго жить. Если несколько фишек пришли в один узел диаграммы переходов, они объединяются в одну, естественно.
Текст кончился, если какая-то из оставшихся фишек находится в целевом (target) состоянии, значит наш текст принадлежит множеству, порожденному нашей регулярной грамматикой. Patern matching - по буржуинскому.
Если фишки закончились, или ни одна из оставшихся не находится в "правильном" узле - ну значит не получилось.

Все же просто. Просто не всегда можно "угадать эту мелодию с одной ноты". Для того, чтобы определить возможность "с одной" - проверяем правила, изложенные Виртом.
Вы спрашиваете про лексику Оберонов ???
Вот Вам встречное предложение угадать лексему "с одной буквы": в тексте идет символ "1", какая это будет лексема :?:
Если можете, ну считайте лексику детеминированной. А вот я - нет... ну дальше - Вы в курсе :D


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

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Galkov писал(а):
2igor
... когда Вам говорят, что у Вас нет основаваний именно для такого решения (например - повторить содержимое данных фигурных скобок), Вы считаете, что я настаиваю на противоположном решении (прекратить повторение), и из такого предположения находите противоречие.
Считая, что нашли противоречие у меня.
Какая-то доля истины в этих словах есть :). Но из этого, отнюдь, не следует, что лексика недетерминирована.

Galkov писал(а):
Вот Вам встречное предложение угадать лексему "с одной буквы": в тексте идет символ "1", какая это будет лексема :?:
Если можете, ну считайте лексику детеминированной. А вот я - нет... ну дальше - Вы в курсе :D
Я легко отвечу на этот вопрос, взглянув на множества First() и Follow() в своём файле. Если это первый символ в лексеме, то этот символ однозначно принадлежит лексеме number (см. множество First() для классов лексем). Если это не первый символ в лексеме, то он может относиться к лексеме ident или number или string (или к комментарию) (см. множество Follow() для классов лексем).

Замечу, что в случае, когда символ "1" встретился в середине лексемы, неопределённость возникает только у меня (и проистекает из неопределённости самого вопроса), а сам лексический анализатор всегда :!: знает какого класса лексему он разбирает в настоящий момент.

Замечу также, что окончание лексемы лексический анализатор всегда легко "вычислит" именно благодаря детерминированности синтаксиса.

Galkov писал(а):
Если можете, ну считайте лексику детеминированной.
Ну, как? Я прошёл Ваш тест на детерминированность? :D


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 11:08 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Перенесено отсюда: viewtopic.php?p=41293#p41293
Пожалуй, надо выступить в защиту г-на Galkov, т.к. истина превыше всего.
Trurl осудил его за фразу "Только лексика Оберонов, являясь регулярной, не является детерминированной"
Trurl писал(а):
Регулярный и недетерминированный язык - это как целое трансцендентное число.
На самом деле во всем виноват Вирт.
Говоря о регулярных языках, он пишет: "The application of these simple translations rules generating a parser from a given syntax is, however, subject to the syntax being deterministic". (выделение моё).
Т.е., Вирт говорит, что синтаксис регулярных языков может быть детерминированым , а может быть и недетерминированым. Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
А Galkov справедиво указал, что для сканера Oberon это не так. Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 12:45 

Зарегистрирован: Вторник, 29 Ноябрь, 2005 21:41
Сообщения: 1030
Peter Almazov писал(а):
Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
В общем случае - нет. Где он об этом сказал?
Peter Almazov писал(а):
Trurl осудил его за фразу "Только лексика Оберонов, являясь регулярной, не является детерминированной"
Вообще-то понятно что имелось в виду, но сказано коряво.
Peter Almazov писал(а):
Речь идет не об общем случае, а о смысле слов "syntax being deterministic".
То что я процитировал о том и говорил. Общий случай для первого варианта.


Последний раз редактировалось Сергей Оборотов Воскресенье, 31 Январь, 2010 12:58, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 12:51 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 563
Откуда: Москва
Сергей Оборотов писал(а):
Peter Almazov писал(а):
Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
В общем случае - нет. Где он об этом сказал?
Речь идет не об общем случае, а о смысле слов "syntax being deterministic".
Цитаты из Compiler Construction 2005


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 15:11 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Peter Almazov писал(а):
А Galkov справедиво указал, что для сканера Oberon это не так. Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".
Дуги-то две. Но текущие литеры, которые определяют переход по ним --- разные. У Вирта так и определено (выделил жирным):
Compiler Construction, 3 Regular Languages писал(а):
For the recognition of regular sentences a finite automaton, also called a state machine, is necessary and sufficient. In each step the state machine reads the next symbol and changes state. The resulting state is solely determined by the previous state and the symbol read. If the resulting state is unique, the state machine is deterministic, otherwise nondeterministic. If the state machine is formulated as a program, the state is represented by the current point of program execution.
Тут картинка: http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 1.82.D1.8C


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 15:14 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Peter Almazov писал(а):
Т.е., Вирт говорит, что синтаксис регулярных языков может быть детерминированым , а может быть и недетерминированым. Имеется в виду, что конечный автомат, построенный для первого случая, обязательно окажется ДКА.
А Galkov справедиво указал, что для сканера Oberon это не так. Например, из вершины НКА, где мы принимаем символ "(" идут 2 дуги. То же самое верно для символа ">".
Вы говорите о том, что в Оберонах есть пары лексем типа: ":" и ":=", ">" и ">=", "<" и "<=" и т.д. И из этого делаете вывод, что КА является недетерминированным, потому что якобы из вершины, соответсвующей этому текущему состоянию автомата, идут две дуги.

Пожалуйста, внимательно посмотрите на прилагаемый рисунок. На нём изображён фрагмент ДКА для лексем ">", ">=", ":" и ":=". Названия текущих состояний автомата я взял прямо из исходника Блэкбокс (кроме начального состояния, которое я обозначил словом begin).

А теперь вопрос. Где Вы тут увидели две дуги, соответствующие лексемам ":" и ":=" и идущие из одной и той же вершины?

Не спешите тыкать пальцем в две дуги, исходящие из начальной вершины. Сначала прочитайте вот эту цитату из книги "Языки программирования и методы трансляции":
С. З. Свердлов писал(а):
На вход КА поступают символы, принадлежащие входному алфавиту. ... Находясь в некотором состоянии и получив на вход очередной символ, автомат переходит в следующее состояние, определяемое значением функции переходов для данной пары символ-состояние, и считывает очередной символ. В общем случае функция переходов может определять переход в несколько состояний для данной пары символ-состояние. В этом случае говорят о недетерминированном конечном автомате (НКА). Автомат останавливается, когда заканчиваются символы на его входе.
В нашем случае нет ни одной пары символ-состояние, для которой функция переходов имела бы более одного значения. Значит, наш конечный автомат является детерминированным. Две дуги, исходяшие из начальной вершины соответствуют РАЗНЫМ очередным символам! Поэтому функция перехода однозначно переведёт автомат либо в состояние colon, если очередной символ равен ":", либо в состояние gtr, если очередной символ равен ">".

PS: Евгений Темиргалеев немного опередил меня с разъяснениями :)


Вложения:
ФрагментДКА.jpg
ФрагментДКА.jpg [ 9.98 КБ | Просмотров: 8491 ]


Последний раз редактировалось igor Воскресенье, 31 Январь, 2010 15:55, всего редактировалось 2 раз(а).
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 15:32 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Peter Almazov писал(а):
... идут 2 дуги. То же самое верно для символа ">".
Уверен, что Вы предполагали что-то типа этого (см. рисунок). Но не учли, что автомат на каждом шаге принимает только один элементарный символ.


Вложения:
Фрагмент2.jpg
Фрагмент2.jpg [ 6.76 КБ | Просмотров: 8486 ]
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 15:50 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Лексические тонкости Оберонов
СообщениеДобавлено: Воскресенье, 31 Январь, 2010 16:05 

Зарегистрирован: Вторник, 13 Ноябрь, 2007 20:38
Сообщения: 1056
Peter Almazov писал(а):
Не понял, зачем было вываливать сюда большой рассказ о ДКА, в который всегда можно преобразовать НКА.
Очень хороший вопрос.

Потому что Вы сказали:
Peter Almazov писал(а):
А Galkov справедиво указал, что для сканера Oberon это не так.
То есть речь идёт о реальном сканере, а не только о чистой теории формальных языков. А все сканеры Оберонов всегда строятся на основе ДКА. Какой смысл было бы использовать НКА, если его всегда можно преобразовать в ДКА, исключив тем самым множество проблем.


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

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


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

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


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

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