1) Перерыв получился, потому что мне показалось очень важным изучить "Построение компиляторов" Вирта перед продолжением беседы
2) Некоторые фразы у Вирта мне показались не очень убедительными. Нас в данном топике интересует разделение компилятора на лексер/парсер.
И чего же мы видим. Сначала как бы определяются регулярные языки (стр 28), и тут же сообщается, что "
Для распознавания регулярных выражений необходимо и достаточно иметь конечный автомат ...". Мимоходом сообщается, что автоматы разделяются на детерминированные и недетерминированные (к чему это - не думаю, что швейцарские студенты раскусят это лукавство с ходу), и далее идет обсуждение только детерминированных, с правилами вывода кода из РБНФ, и условиями на эти выражения для применимости этих правил.
С моей точки зрения, лукавство заключается в том, что лексеры в массе своей - это недетерминированные автоматы.
Детерминированность предполагает разрешение любой альтернативы по первому же символу.
А это не так, да хоть бы и для Оберон-0
Ну посмотрите, к примеру, на каком символе будут различимы 3 патерна: ELSE, ELSIF, и ident
А ведь с точки зрения пользователя, недетерминированный автомат - совсем не кошмар в графическом представлении.
Если детерминированный представляется графом, в котором в каждый момент "активна" только одна вершина, то в недерминированном - их просто несколько, вот и вся разница. Также как и в детерминированном, какие-то из вершин являются "целевыми", а весь набор активных в данный момент вершин является "целевым", если в нем есть хотя бы одна "целевая"
Мне даже кажется, что наиболее важной причиной выделения лексера в отдельную функциональность - это оставить детерминированность парсеру. Хотя тот уже не просто автомат, а как бы - "стековый". Вот парсер - тот ДА, все альтернативы распознает с первой лексемы, вся недетерминированность сосредоточена в лексере.
Грубо говоря, борьба идет за единичку в определении грамматики: хоть LL(1), хоть LR(1).
По-моему, это более значительная причина, чем указанная Виртом "
независимость от конкретного представления ..."
3) Далее, главное правило лексера Вирт так и не обозначил ведь, хотя оно и используется по полной программе
Это же Ваш вопрос о различении константного символа...
Ну скажем, он определил как бы синтаксис для РБНФ-лексера на стр 28. Исходя из которого, как бы совершенно логически вывел коды для GetSym (между прочим, приведенный Виртом GetSym не скушает лексики самого РБНФ - комбинация """ для него криминальна).
А вы попробуйте проверить им же выше означенные условия для применимости правил вывода. И ничего у Вас не выйдет. Вам придется доказать (!!!) что после нетерминала identifier ну никак не может следовать буква.
Ну да, не может (поэтому код-то верный).
Только это ни откуда не следует!!!
Это такая договоренность есть для всех лексеров - выбирать символы из входного потока до посинения, пока не отвалятся ВСЕ патерны. И последний отвалившийся и будет принятой лексемой (если конечно отвал произошел из "целевого" состояния).
Это правило делает некорректным смешение патернов лексера и парсера в одну кучку. Правила проверки однозначности разрешения альтернатив перестанут работать.
Ну посмотрите упражнение 4.2 на стр. 42...
Ну неправильно это: первые 2 строчки в приложении A1, и первые 9 - в приложении A2
Отдельно должны быть лексика и синтаксис. Потому что между ними вставлено вышеозначенное правило лексеров. И только после этого начнут правильно работать "правила проверки", приведенные Виртом.
4) Формализм для определения лексеров я кажется читал еще в Dragon-book...
Выглядит упрощенно примерно так:
Код:
P1 {Action1}
P2 {Action2}
P3 {Action3}
....
Где Pi - регулярные выражения для разных лексем, а ActionI - действия, предписанные разработчиком при распознавании лексемы. Причем тут есть следующая заморочка: если для примера ничего не делать, то лексер устанавливает свои автоматы (все вместе которые можно рассматривать как один недетерминированный автомат) в стартовое состояние, и начинает принимать текст дальше. Хоть весь текст может скушать за один присест.
Разработчик явно указывает в Action типа такого {... RETURN LexemID}, тогда парсер получит чего надо, и должен будет вызвать лексер еще раз.
Вот такое получается формальное определение магического слова "пропустить", которое мы употребляли ранее.
Есть еще фокус: отвалиться последними могут одновременно несколько патернов. Например, для служебного слова и идентификатора. Тут тоже совершенно точное правило - срабатывает Action для того патерна, который записан раньше. Поэтому совершенно обязательно сначала записывают патерны для служебных слов, а потом для идентификатора.
Как бы в подтверждение, что это не мои фантазии, а давно общепринято:
flex.pdf писал(а):
0.8 How the input is matched
When the generated scanner is run, it analyzes its input looking for strings which match any of its patterns. If it finds more than one match, it takes the one matching the most text (for trailing context rules, this includes the length of the trailing part, even though it will then be returned to the input). If it finds two or more matches of the same length, the rule listed first in the flex input file is chosen.
5) В общем, как-то так