igor писал(а):
Как по Вашему сканер должен понять что это две лексемы "name" и "56", а не одна лексема "name56"? Пробельный символ между "name" и "56" устраняет неопределённость, делает синтаксис детерминированным
Чего-то мне кажется, что вы ошибаетесь.
Если исходить ТОЛЬКО из написанного Вами, то и сейчас - НИКАК. Ибо у Вас "
повторение" имеет право (и должно иметь это право) быть пустышкой.
Вот я все время Вам твержу, что для возможности такого разделения нужна допонительная информация (т.е., не содержащаяся в написанных РБНФ-выражениях), а Вы мне не верите.
Нужна-нужна, и называется она: правило "самой длинной лексемы"
Ну а теперь про Ваш файл....
Самое первое, что я понял, так это то, что у нас с Вами какое-то разное понимание FOLLOW, и на фига он нужен.
Вашего понимания я до конца не осознал, но как-то оно больше похоже на LAST...
А нафига нам LAST-то ??? Нам нужно множество символов, которые допускает определенный нами синтаксис (весь целиком, а не только его определение), которые могут следовать ПОСЛЕ нужного нам нетерминала.
Зачем ??? Это иногда (не всегда, бывает и все банальнее) нужно для проверки 3-го правила (для "повторов" и "необязательностей") Вирта на стр 29:
Цитата:
Множества начальных символов exp и символов, которые могут следовать за K, не должны пересекаться
В том случае, когда эта "конфигурация" является последней в определении нетерминала - мы должны озадачиться множеством FOLLOW для него.
Это я так все понял. Правильно/неправильно - давайте обсуждать. Глядишь, и более старшие коллеги чего подскажут...
А пока я изложу далее свое понимание "этого" по Вашему тексту, чтобы база для обсуждения была более подробной, чем вышеприведенная фраза.
1)
Нетерминал lexeme. Первые скобки с альтернативойДа нет вопросов - множества FIRST для разных альтернатив действительно не пересекаются. Пока
Это я к тому, что Вы просили "ткнуть носом" на недетерминированность. В смысле, мне было бы интересно посмотреть, как бы Вы вводили сюда нетерминал
char=digit{hexdigit}"X". Или hex-альтернативу для
number=digit{hexdigit}"H".
[философское отступление]Фразу Вирта про предпочтительность детерминированной лексики я понимаю как возможность определить таковые константы, например, как в Дельфи:
number="$"hexdigit{hexdigit}, или
number="#"digit{digit}. Ну да, можно. А можно и не определять - не настолько большой кошмар "недетерминированность". Можно сказать - вообще не кошмар.
Спрашивается, зачем Вирт употребляет детерминированность для лексики ??? Мне представляется, что только для педагогических целей: прозрачное отражение в конечные коды. А есть еще и задача понимаемось/понятность/надежность исходного кода нами, человеками.
Все точно так же, как в языках программирования. Самое прозрачное отражение в целевые коды делает ассемблер!!!
А мы, человеки, продолжем беспокоиться о каких-то там ЯВУ
Ну вот, приводил же уже
Код:
"<" {... RETURN lxLT}
"<=" {... RETURN lxLE}
- все просто как топор. Но ведь можно написать и как-то хитромудро "<"["="], и куда при этом вклеивать action, и как сей патерн обозвать - тоже ведь вопрос.
А результат-то будет один и тот же (если постараемся).
Можно даже точно сказать следующее (
Илья упоминал ведь про это): Всякий НКА, для которого не надо никакие правила проверять, можно привести (ручками - тоже нетрудно, между прочим, и у дядюшки Ахо примеры про это есть) к ДКА. Так для него тоже никаких правил проверять не надо, но уже потому, что они выполняются по самой процедуре построения.
Из этого ДКА можно сразу написать код.
А можно, глядя на диаграму переходов, и написать эквивалентные регулярные выражения. Тут основная трудность будет в придумывании имен... Сочинять будем всякие там "классы лексем", и т.п..
Будут ли эти регулярные выражения настолько же понятны, как и исходные, из которых и делали НКА ???
Очень сомневаюсь (хотя чем черт не шутит)... К примеру, Ваших терминов про "классы лексем", и различия смежду токенами и лексемами - я до сих пор вкурить не могу
[/философское отступление]
2)
Нетерминал lexeme. Пропуски пробелов и комментариевСмотрим правил 3 и спрашиваем себя: какие это такие символы "
могут следовать за K".
Вот в моем понимание, это ничто иное, как FOLLOW(lexeme)
Чему он равно ??? А фиг его знает !!!
Помните, Вы говорили, что лексер - это тот же самый парсер ??? Так для парсера такие вопросы не возникают. А если и возникнут, то FOLLOW - это просто пустышка. Все файл закончился.
Т.е., я готов согласиться, что это тот же самый парсер, если наша задача, не более, чем ответить на вопрос: является ли нашей лексемой (одной!!!) содержимое этого файла.
В этом случае все тип-топ. Но ведь нас же интересует возможность разделения name56 на две лексемы ???
Ну предположим (хотя я понимаю, что фигня это), что за одной лексемй сразу же следует другая.
Тогда
FOLLOW(lexeme)=FIRST(lexeme) - и я опять выражу сомнение, в том, что множества FIRST(lexeme) и FIRST(comment) не пересекаются.
Какие у меня получаются варианты для "большого текста": либо правило 3 не выполняется, либо я вообще не могу ответить на этот вопрос.
3)
Нетерминал ident. Повторы в немОпять правило 3. Опять "
символы, которые могут следовать за K". И это FOLLOW(ident). Чтобы смекнуть про содержание этого множества, мы должны проанализировать все вхождения этого нетерминала в наш синтаксис. Ну да, и видим, что он входит только в lexeme. Применяем правило 2, и получаем, что FOLLOW(ident)=blank+FIRST(comment)+FOLLOW(lexeme). Про FOLLOW(lexeme) см. выше. И выводы - те же, несмотря на идиотизм ситуации.
4)
Нетерминал number. Повторы в немМожно повторить предыдущий пункт слово в слово. Не, ну заменить ident на number, конечно же
5)
Нетерминал string. Повторы в нем (альтернатива совершенно непроблематична - правило один выполняется слишком очевидно)
Здесь по-проще. "
Символ, который может следовать за K" слишком очевиден. Но анализ (типа супер въедливость) вскрывает ошибку: кавычки таки содержатся в множестве char. Но это легко исправимо.
6) Затрону таки
нетерминал commentИбо нарисован он неправильно, а я об этом уже заикнулся ранее.
Так вот, символ, следующий за
{sym} - это "*"
Пересечение sym и "*" - не пусто => правило 3 невыполняется