Распознавание символа - FIND и NUMBER

Перейти вниз

Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:04 pm

На кошачьем форуме опять взялись "ловить неуловимого Джо" - рассуждать о полезности "правильной организации словарей". Но, к сожалению, самое интересное в словарях лежит за гранью понимания "кошатников". Скучно. Перечитать, что ли старые записи?
***
Формально, процедура СИМВОЛ должна заниматься поиском слова в словаре. Она проста как сибирский валенок и может быть легко разложена на привычные FORTH-кирпичики (см. у Баранова и Ноздрунова).
Поэтому "фортеров" хлебом не корми, дай предложить свой вариант FIND - ускореный применением методов хэширования, оформленный в виде метода словаря, наоборот, вынесенный за пределы словаря в виде глобального оператора switch...
***
Так вот, это неправда. FIND ищет не всегда слово и не всегда в словаре... За примерами далеко ходить не надо - они приведены аж в первом описании Мура.
- На входе - не всегда слово. Мур предложил пару стратегий проведения "дораспознавания" слов, если их поиск оказался неудачным - обрезание (и возвращение для рассмотрения WORD) суффиксов и разделителей, "прицепившихся к словам".
- К распознаванию слова как имени в словаре и слова как числа Мур добавил поиск слова в дисковой памяти.

Т.е. и входная, и выходная граница FIND получаются сильно размытыми, а "собственно FIND" представляется совсем неинтересным.
***

Что же такое FIND? Это процедура,
1. получающая на входе что-то, что имеет смысл считать осмысленным FORTH-сообщением
2. и, учитывая текущий контекст,
3. распознающая это сообщение.

Конечно, под этакое "определение" подходит половина вселенной, но я готов показать, что то, что пытаются нам подсунуть современные "улучшатели", в эту "половину" не входит.
Ведь, по сути, эта процедура ответственна за основополагающее свойство FORTH - однозначное соответствие лексемы входного потока адресу кода.
Очевидно, что возможны две крайности в реализации этой функции:

1. упрощение - соединение простейших "распознавателей" в цепочку: "сам не распознал - передай другому". Так делал Мур: сначала пытался распознать лексему как имя словарной статьи (FIND), затем - как число (NUMBER), затем, как слово, сохраненное в дисковой памяти.
2. усложнение - создание распознавателя как некоторой "вещи в себе", которая начнет с лексемы, а закончит исполнением всех действий, положенных для ее обработки - исполнением, размещением на стеке или компиляцией.

Еще более очевидно, что сама механика распознавания от этих крайностей особенно не зависит, разница, скорее, терминологическая - "Цикл Управления", "переключение контекстов" и т.д...
***

Тут мы видим отличие первых версий FORTH от последующих. В первых FIND (как часть INTERPRET) располагался внутри Цикла Управления, т.к. циклу было "безразлично", что ему скармливают: текстовый ввод или шитый код.
Позднее Цикл Управления замкнули исключительно на интерпретации шитого кода (точнее, шитый код сам себя интерпретирует и понятие "Цикл Управления" утратило свою фундаментальность). INTERPRET теперь "обычное слово", и его работа по распознаванию входного потока FORTH-систему заботит очень мало (в ней просто нет частей, способных этим озаботиться.
В случае получения (путем целевой компиляции) специализированной FORTH-машины, INTERPRET может напрочь отсутствовать, т.к. все, что нужно уже скомпилировано и ввод лексем-команд не нужен.
Кажется логичным в общем случае иметь не один INTERPRET, а несколько - вызываемых "параллельно" для интерпретации нескольких потоков, которые могут быть открыты Fort-системой одновременно. И, соответственно, нескольких FIND.
Применение единого механизма может быть оправдано только унификацией похожих способов интерпретации - чтобы не плодить одинаковый код.
Поэтому я считаю, что основным методом реализации распознавания должен быть "упрощающий": он, с одной стороны, убережет от необходимости повторять общие места в распознавателях-монстрах и, с другой, может быть легко конвертирован в них путем инкапсуляции в некоторых "охватывающих словах". ОСНОВНОЙ ПРИНЦИП!


Последний раз редактировалось: Gudleifr (Пт Сен 15, 2017 2:21 pm), всего редактировалось 2 раз(а)
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:06 pm

FORTH-СООБЩЕНИЕ

Что это такое? Это то, что можно либо исполнить, либо прописать в шитый код. Числа, например, можно "исполнить", положив их значение на стек.
В "нормальных" языках програмирования обычно "нормальной" реакцией на ввод чего-либо является его "регистрация". Т.е. заполнение введенными значениями каких-либо структур, которые в дальнейшем будут как-то использоваться (может, даже, исполняться, если речь идет об "обычных" интерпретаторах).
Главная идея FORTH - простота, и эти промежуточные структуры - на фиг. Ввел - исполняй!
Если ввод используется для чего-то, кроме исполнения, то до "обычного" FIND дело просто не доходит - распознает данные тот, кому они понадобились.
***

Каков же список вещей, которые могут исполняться/компилироваться?

1. Слова в словаре - самое простое, что можно придумать.
2. Слова в специальных хранилищах (на дисках, в библиотеках...) - как предлагал Мур.
3. Литералы разного вида (обычно - целые и вещественные числа) - их ищет NUMBER, хотя задача может потребовать и чего-то более изощренного (например, комплексных чисел или ДНК-последовательностей).
4. Строки для нетривиальной интерпретации "в обход" нормальной.

Последнее - явно избыточно, т.к. может быть сведено либо к интерпретации нормальной, либо к "регистрации" в обход FIND.
Так что, все, что может быть распознано по каким-то таблицам имен, относится к FIND, а все, что распознается по регулярным выражениям - NUMBER.
***

Так, что мы уточнили формат вывода FIND и NUMBER - что-то, что можно исполнить/скопмпилировать, и разницу в их работе - по таблицам или по регулярным выражениям.
В зависимости от назначения FORTH-системы несколько разных FIND и/или NUMBER могут объединятся в цепочки (см. выше). Например, до выхода стандарта ANSI-94 (см. Броуди, Баранов и Ноздрунов) нормальным считалось иметь CONTEXT-FIND, CURRENT-FIND, FORTH-FIND (ищущих в означенных словарях) и один NUMBER - для всех видов чисел.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:09 pm

ВЫДЕЛЕНИЕ FORTH-СООБЩЕНИЙ

Возможны три типа потока слов (т.е. не самих лексем, а способов их размещения в строке):

1. Наиболее удобный для ввода программы. На данный момент ничего удобнее обычного потока слов, разделенных пробелами не придумано. (Хотя, некоторые фортеры, и сам Мур в том числе, пытаются придумать некоторую более выразительную/емкую грамматику - например, раскрасив слова).
Одно из преимуществ обычного потока слов - однозначность выделения лексемы. "Обычный" FIND только этого и ждет.

2. Потоки, порожденные другими программами. Отличие этих потоков от всех остальных - наличие явно описанной грамматики, их порождающей. Достаточно переписать WORD под регулярные выражения и обычный FIND - опять на коне.
Однако, здесь получается некоторая избыточность - имеется два схожих механизма анализа регулярных выражений - в WORD и NUMBER, и что, особенно неприятно - на разных уровнях FORTH-системы. Т.е. в случае "регулярного потока общего вида", анализом литералов должен бы, по уму, заниматься сам WORD (в обход FIND).
Но, в большинстве случаев подобный ввод настолько прост, что WORD не усложняется, а упрощается: например, поток Win-сообщений - четыре параметра, уже лежащие на стеке. Простота "регулярного" ввода вызывает и злоупотребления: часто очень легко предварить поток такого вида "обычным словом", которому и поручить его распознавание. Наверное, имеет смысл явно "дотягивать" подобные слова до уровня INTERPPRET.

3. Потоки, распознавать которые следует эвристически. Именно об этом говорил Мур. И у него еще был простой случай, хотя и потребовавший возможности отката неправильного распознавания... Т.е. слияния WORD и FIND в единый механизм.
Придумать задачу, настолько сложную, что ее ввод придется делать таким сложным - сложно. (Например, распознавание речи, когда с уровня распознавания предложений возможен откат на уровень слов, с уровня слов - на уровень слогов, от слогов - к отдельным звукам).

Т.о. мы видим, что в случаях, отличных от простейшего имеет смысл "играть" не только внутренним устройством WORD, FIND и NUMBER, но и их взаимными связями.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:10 pm

УСЛОЖНЕНИЕ ПУТЕМ УПРОЩЕНИЯ

Договорившись в конце предыдущего абзаца до распознавания "естественного" языка, мы быстро дойдем до всякого рода "экспертных систем" и "перцептронов".
Однако, на этом пути мы очень быстро придем к тому, что "размышление" будет весить гораздо больше, чем "действие" и FORTH-минимализм - исполнять/компилировать - уже будет избыточным... Достаточно будет одного действия - возбуждение...
Но это уже совсем другая история...
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:12 pm

КОНТЕКСТ FIND

Очевидно, при поиске по таблицам огромнейшее значение имеет порядок таблиц, в которых мы ищем слово. Причем, "таблицы" могут быть подобными друг другу (как словари, предложенные Барановым и Ноздруновым), а могут и совершенно разными (как предлагал Мур). Разница, скорее, чисто в затратах времени и места на индексацию. Быстрый поиск осуществляется в хорошо проиндексированной базе имен, медленный - в больших текстовых массивах.
Начинать поиск, очевидно стоит с первого.
***

Мур использовал понятие контекста, в основном, для экономии времени поиска на диске, ограничивая размер "дисковых словарей".
Позднее (Броуди, Баранов и Ноздрунов) словари использовались для разграничения пространств "поиска" и "компиляции", без чего явно невозможна была бы реализация целевой компиляции.
В стандарте ANSI-94 принята другая концепция: использование стека "контекстов", чтобы как-то организовать свою программу (зря Броуди так расхвалил иерархию лексиконов). Доходит до смешного - некой пародии на ООП: словари - объекты, а одинаковые слова, определенные в них по-разному - методы.
***

Возможно, конечно, возведение механизма словарей в некий абсолют, перейдя от концепции слов, как абстракции действий, к словарям, как описаниям некоторых абстракций чего угодно. Вплоть до словарей, как отдельных FORTH-машин.
Например предлагается каждый "контекст" снабдить своей разновидностью FIND - от обычного, до подменяющего WORD или NUMBER. (Словарь чисел тогда не будет искать словарную статью, которых в нем нет, но попытается интерпретировать лексему как числовой литерал).
Однако, признать полезным столь философское переосмысление чисто практического приема очень трудно, т.к. она явно нарушает ОСНОВНОЙ ПРИНЦИП. Вводить специальный механизм для сложностей, которые либо никогда не возникнут, либо вызовут проблемы, которые окажутся "механизму" не по зубам? Или "универсальность" подобного механизма дает какую-то иллюзию "высокоуровневости"?
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:13 pm

МЕЛОЧИ ЖИЗНИ

Попробую пойти от потребности. Для FOBOS понадобилось, по крайней мере, три разновидности поиска слов:
1. "Стандартный" для FORTH (исторически реализованный по Баранову и Ноздрунову). Он реализован на языке ассемблера в ядре, т.к. без него интерпретация текстовой части невозможна.
2. Dll-ный, ищущий исполняемые адреса API-функций. На этапе загрузки ядра MD делает это автоматически, но затем приходится искать их самим. Впрочем, реализация достаточно рудиментарная - "имя" состоит из двух строк - имени бибиотеки и имени функции. Сама же искалка - пара API-функций. Нужна только приемлимая функция компиляции найденного адреса. Иметь несколько словарей не обязательно, пока мы не озаботимся проблемами Dll-Hell (хранением разных версий одних и тех же библиотек).
3. Поиск нужного обработчика сообщения. Это должно бы быть примером отсутствия излишних имен. "Именем" обработчика является четверка параметров, получаемых оконной функцией. (Пока это не так).
4. Пока нет, но когда-нибудь будет ввод из консоли (других текстовых органов управления).

Три потока (файл, консоль и Win-сообщений) и три FIND (слов, функций и сообщений).
Сначала я подумал о подкараулившей меня раньше времени многозадачности, но потом вспомнил о том, что мы считаем FIND важной частью FORTH-системы исключительно по инерции. Любое слово вправе читать что хочет, откуда хочет и делать с ним, соответственно, тоже, что хочет. Тем более, вполне возможно придется комбинировать разные потоки с разными FIND.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:14 pm

ОСНОВОПОЛАГАЮЩЕЕ СВОЙСТВО?

Но если я буду использовать разные FIND или даже обойдусь совершенно без них, кто будет обеспечивать однозначность соответствия лексема - код? Гибкость - гибкостью, но если поиск лексемы будет настолько "контекстно-зависимым", что нельзя будет ручаться за то, как FORTH-система воспримет ту или иную фразу. (Что-то вроде Python, где о смысле оператора можно судить, в лучем случае, только дочитав программу до конца).
Считать каждый случай использования INTERPRET-подобных слов отдельной FORTH-подсистемой? (Поклонники ООП и "контекстов", конечно, радостно заявят, что у них подобных проблем нет, т.к. все частности инкапсулируются... Но нам от этого не легче. Какая разница мне от того, почему именно я не могу предсказать поведение системы?)
Наверное, надо расширить или сузить область рассмотрения. Углубиться в исследование, собственно, FIND - механизма поиска в словаре? Или подняться до уровня слова FORTH-СИСТЕМА, запрашивающего, читающего, распознающего и исполняющего команды?
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:17 pm

С ТОЧКИ ЗРЕНИЯ БАНАЛЬНОЙ ЭРУДИЦИИ

Что такое Fort-система изначально? Процесс взаимодействия тупого программиста с умным пользователем. Программа, умеющая что-то делать, но ожидающая, что ей явно будут указывать, что именно делать, и, что все особые случаи пользователь будет обрабатывать сам. (Это не я придумал, это Мур написал).
Т.е. программа, состоящая из двух частей: уже откомпилированного кода и команд, получаемых из пользовательского ввода.
Использование разных стратегий ввода и распознавания команд - суть, использование разных языков. Но язык определяет машину (это тоже не я сказал, это - Дейкстра).
Раз уж мы его вспомнили, вспомним, что он писал о сложных программах. Он рассматривал их как ожерелье, собранное из обозримых программистом машин-бусин, настолько независимых друг от друга, что заменить одну из них можно было без пересборки всего ожерелья...
На верхнем уровне можно провести аналогию между ожерельем и идеями Мура - в первом случае ожерелье собирает компилятор, во втором сам пользователь. Определение пользователем новых FORTH-слов - это не столько создание новых машин, сколько приготовление заготовок-фрагментов ожерелья. Рождается крамольный вывод: в FORTH допускается только простейший язык самого верхнего уровня, все языки более низкого уровня - лишь вопрос реализации.
Нас это не явно не устраивает, нам нужно средство писания и самих машин-бусин. Не зря же Броуди твердил об иерархиях лексиконов! Однако, речь он вел только о добавлении новых слов, а не о разных языках. Надо ли нам выходить за эти границы? Ведь Дейкстра этого явно не требует, обсуждая, по сути, тоже только лексиконы.

1. Чужой язык может быть языком аппаратуры или подпрограмм.
2. Чужой язык может быть языком другого пользователя, операционной системы.
3. Чужой язык может требоваться самому пользователю.

Сложность представляет только случай (2). В случае (1) поддержка чужого языка может быть реализована строго "по месту", без всяких интерпретационных ухищрений. В случае же (3) можно сразу обучить FORTH нужному языку, используя его вместо стандартного.
Рассмотрим (2) подробнее. Во-первых, нельзя ли избежать такой ситуации в принципе? Очень часто можно. Достаточно не стремиться сделать универсальный FORTH "на века" и не увлекаться красивыми синтаксическими экспериментами, универсальный язык - "команды, разделенные пробелами" - достаточно мощен и удобен. Однако, не всегда все зависит от нас, например, язык Win-сообщений был дан нам в ощущениях.
Во-вторых, если такая ситуация возникла, то имеем ли мы дело с небольшим фиксированным набором комбинаций или множество языков может быть достаточно объемным и, даже, расширяемым? И есть ли тут какая-либо разница? По, крайней мере, и "упрощающий" и "усложняющий" подходы одинаково применимы в обоих ситуациях.
***

Пусть, например, задача - написать на FORTH компилятор ALGOL-подобного языка.
Сначала мы должны распознать лексемы (C-код, который умеет это делать обычно пишет программа lex на основе списка регулярных выражений), нам это уже вполне по силам - мы можем научить свой NUMBER распознавать и литералы, и разделители, и идентификаторы. Куда девать результат? Передавать лексемы по мере распознавания компилятору (обычно пишется программой yacc или bison - компилятором компиляторов - на основе описания грамматики) или загонять в промежуточный файл. Второй случай нам может показаться ближе тем, что этот файл может быть удобно представлен на обычном FORTH-языке. Но, независимо от способа, все сведется к вызову некоторых слов, которые "знают свое место в грамматике".
Что бросается в глаза:

1. FORTH умеет читать свой язык, но не умеет на нем писать! Это не недосмотр создателей. Это философское ограничение: "тупой программист - умный пользователь". Язык нужен только для управления FORTH-программой.
2. При чтении "языка грамматики" мы сталкиваемся с тем, что слово не нужно исполнять, ни компилировать, а нужно именно "регистрировать". Конечно, создание в памяти механизма грамматического разбора, можно свести (и придется) к обычным исполнению и компиляции, но не проще ли создать на время распознавания некое специализированное FORTH-грамматическое-ядро? Т.е. кроме WORD, FIND и NUMBER, нам придется править и то, чего в FORTH просто нет - "регистрацию" (в FORTH на этом месте только условный оператор исполнять/компилировать).

Т.е. не мытьем, так катанием, приходим к Дейкстровскому: новый язык - новая машина. Хотите новый язык - пишите новую FORTH-машину и "приращиваете" ее к своей. Не FORTH, готовый читать все, что нужно, но набор "бусин", собранных из стандартных кирпичей.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:19 pm

АЛГОРИТМЫ ПОИСКА

Простейшая конструкция словарей, описанная Барановым и Ноздруновым, прекрасно работает. Что может нас подвигнуть на ее "улучшение"? Который из кусков алгоритма FIND надо заменить:

1. определение области поиска;
2. способ поиска;
3. что делать, если поиск успешен?
4. что делать, если поиск не успешен?

avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:22 pm

ГДЕ ИСКАТЬ?

Организация наборов словарей очень сильно зависит от принятой парадигмы, а парадигм предостаточно:
- СЛОВАРИ-БИБЛИОТЕКИ - позволяют собрать работающую программу с минимальной избыточностью ("грузим только те библиотеки, какие нужны");
- СЛОВАРИ-КАТАЛОГИ - ускоряют поиск слов за счет ограничения области поиска ("зачем искать везде, если я знаю, где оно лежит?");
- СЛОВАРИ-ЛЕКСИКОНЫ - позволяют вводить слова-понятия иерархически ("от языка управления машиной - до проблемно-ориентированного языка");
- СЛОВАРИ-КОНТЕКСТЫ - обеспечивают контекстную зависимость ("мы знаем, о чем говорим");
- СЛОВАРИ-ОБЪЕКТЫ - имитируют ООП ("словарь - класс, слово - метод");
- СЛОВАРИ-МАШИНЫ - инкапсулируют в себе свои собственные EXPECT-WORD-FIND-NUMBER ("нет такого ПОТОКА, который нельзя было бы считать ПОТОКОМ");
- СЛОВАРИ-ПРОСТРАНСТВА - изолируют отдельные пространства памяти друг от друга ("читаем - отсюда, а пишем - сюда").
...

Технические различия:
- размер словарей и средства оптимизации поиска в них;
- количество одновременно просматриваемых словарей (и управление порядком их просмотра);
- уровень унификация структур: от полностью одинаково устроенных, до являющихся полноценными FORTH-машинами, со своим машинным кодом;
- уровень использования специфических аппаратных/программных средств (сегментов, страниц, параметров защиты, механизмов ОС...).

Т.о. найти двух фортеров, которые бы сошлись во мнении о том, как надо делать словари, крайне проблематично. Хотя, "пространство технических решений" и меньше "пространства решений идеологических". Следствие: принятие какой-либо замысловатой парадигмы чаще всего приводит к написанию жутко избыточного и непродуктивного кода.
***

Еще раз убеждаюсь, что идея нормальности наличия в системе вторичной FORTH-машины правильна. Как иначе вырастить поверх примитивных словарей первой версии что-то, отражающее сиюминутное мнение фортера о необходимости той или иной парадигмы?
***

Создать что-то универсальное в данном случае означает ничего не делать, т.к. большинство решений между собой несовместимы. (Нечто, вроде этакого "ничего не решающего решения", предложено и в ANSI-94). По сути, ответ на вопрос о словарях следует из ответа на вопрос о назначении данной FORTH-системы.

Примерно...размер словарейколичество одновременно просматриваемыхуровень унификация структурспецифические аппаратные/программные средства
СЛОВАРИ-БИБЛИОТЕКИсловари - минимальные замкнутые множества слов-функций, как и в "нормальных" языкахпара-другая, обеспечивающих "операторы языка" общего назначения, плюс, один-два набора специфичных функций, с которыми работаем в текущий моментполная, т.к. все функции должны вызываться единообразнословари используются в т.ч. для инкапсуляции ф-ий ОС, но ОС-зависимые решения не применяются
СЛОВАРИ-КАТАЛОГИбольшие, иначе зачем ускорять поиск?мало, иначе выигрыша в скорости поиска не будетполнаянапрашивается использование файловой системы ОС (как в Python)
СЛОВАРИ-ЛЕКСИКОНЫобозримые, см. Броудидлинные цепочки прото-лексиконовполная (стандартная)нет, ибо классика
СЛОВАРИ-КОНТЕКСТЫобозримые, по стандартам структурного программированиястеки просмотра "подключенных к модулю" контекстов в стиле ANSI-94возможны вариантывозможно
СЛОВАРИ-ОБЪЕКТЫмалые, методов-то обычно не многосписок наследованияполнаянет
СЛОВАРИ-МАШИНЫбольшие, внутри машин делить не хочетсянет, они слишком разныенет, они слишком разныеинкапсуляция машинных зависимостей, чтобы FORTH-системе они казались одинаковыми
СЛОВАРИ-ПРОСТРАНСТВАобозримые, внутри пространств деление возможновозможно и между пространствамиболее-менее по возможности


Последний раз редактировалось: Gudleifr (Вт Июн 20, 2017 9:41 pm), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:24 pm

КАК ИСКАТЬ?

Широко известны три способа:

1. Начинающие фортеры часто используют обычный CASE-оператор, сравнивающий считанное слово со словами словаря. Даже Мур сначала так делал. Естественное ограничение этого способа - добавить в словарь новые слова можно только при модификации кода.
2. Очевидное решение - свернуть CASE-оператор в цикл, вынеся слова в отдельный список. А простейший способ хранения списка, разрешающий добавление и не требующий одинаковой длины элементов - обычный односвязный список. Что стандартно и имеем.
3. Очевидное улучшение - использование хэш-таблиц (см. например, статью Родригеза). Они дают время поиска слов, практически независящее от длины списка. Это очень просто и часто используется, невзирая на явную избыточность такой оптимизации.

Лучший способ - второй. Единственный список гораздо лучше управляется и легко модифицируется. В большинстве стратегий управления словарем используется тот факт, что мы имеем дело практически со стеком:
- новая словарная статья конструируется на вершине стека;
- при необходимости очистить стек от оверлеев или старой версии программы, это легко сделать, просто обрезав его;
- новые версии слов закрывают от программиста свои омонимы.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:25 pm

ПОИСК УСПЕШЕН

Стандартно адрес статьи, найденный FIND, возвращается в цикл INTERPRET, который и решает, компилировать слово или исполнять, в зависимости от STATE и IMMEDIATE. Однако, иногда фортеры хотят странного. Например известна идея "FORTH без STATE", при которой словари разделяются на три категории: ИСПОЛНЯЕМЫЕ, КОМПИЛИРУЕМЫЕ и КОМПИЛИРУЮЩИЕ. Вместо того, чтобы установить STATE в 0 (режим исполнения), идет поиск (и исполнение) слов словаря ИСПОЛНЯЕМЫХ, а в режиме компиляции идет поиск (и компиляция) слов словаря КОМПИЛИРУЕМЫХ и поиск (и исполнение) слов словаря КОМПИЛИРУЮЩИХ.
***

Вероятно, возможны и другие варианты зависимости использования полученного адреса от словаря, особенно для СЛОВАРЕЙ-МАШИН.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:26 pm

ПОИСК НЕ УДАЛСЯ

Ранее я писал, что естественной реакцией на ненахождение слова FIND должна быть передача его следующей процедуре распознавания (например, NUMBER). Однако, даже в этом простейшем случае существует дилемма: допустим, я не нашел слова в словаре, должен ли поиском в следующем словаре заниматься тот же FIND (по Баранову и Ноздрунову, FIND даже не заметит, что произошло переключение словарей), или следующий словарь будет обрабатываться другим FIND (или тем же FIND, но после уведомления системы о неудачном поиске, в следующем цикле интерпретации)?
***

Кроме того, распространено решение иметь в конце словаря слово NOTFOUND, которое будет делать что-то полезное. (Например, в FOBOS неудача поиска обработчика сообщения обычно приводила к запуску функции DefWindowProc). Некоторые вешают на NOTFOUND вызов NUMBER... А некоторые даже заводят, для единообразия, пустые словари, содержащие только NOTFOUND, распознающие разного рода литералы.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:27 pm

ИЗ МОЕГО ОПЫТА

С одной стороны, я никогда не писал настолько больших FORTH-систем, чтобы от словарей был хоть какой-либо прок. Мне всегда казалось переписать исходники заново проще, чем выполнить "целевую компиляцию". Почистить словарь или просто перезапустить FOBOS - проще, чем переключать словари с задачи на задачу. Обеспечить наследование загрузочных блоков - проще, чем следить за наследованием словарей.
***

С другой, придя к концепции вторичной машины, я столкнулся с совсем несовместимыми словарями, для которых обычная схема не подходит.
***

Т.е. всегда по инерции реализовал механизм словарей по Баранову и Ноздрунову (красиво, ведь), но никакой выгоды от этого не имел. Наоборот, иногда получал паразитную контекстную чувствительность программы, приводящую к трудновыявляемым ошибкам.
***

Можно рассудить так: необходимость изобретать сложные словари может порождаться необходимостью организовать код для удобства восприятия, техническими потребностями или желанием объектно повыпендриваться.
В первом случае есть два довода против: простота FORTH-программы в отсутствии избыточности, а не в структуризации, и есть алтьтернатива - блоки и оверлеи.
В случае же технической необходимости вероятность того, что заранее заготовленная структура словарей окажется полезной именно в этом случае, ничтожна.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:33 pm

СЛУЧАЙНО ПРИГОДИВШИЕСЯ СЛОВАРИ

В одной из старых советских книг предлагались следующие способы сделать запросы к БД более лаконичными.

1. множество значений характеристик
должность == инженер, техник, завлаб,...;
фамилия == Иванов, Петров,...;
зарплата == 100-500;
год рождения == 1920-1985;

2.описание самоидентифицирующихся значений
красный -> цвет;
инженер, лаборант -> должность;

3. приписывание семантической ориентации
моложе == =<(возраст);
выше == =>(зарплата, рост, производительность);
снс == =зн(должность);

4. выделение определяющих атрибутов
инженер == сотрудник | должность = инженер;
комсомолец == сотрудник | партийность = ВЛКСМ;

5. указание специфицирующего набора характеристик
сотрудник == (фамилия, имя, отчество, должность);
подразделение == (название);

6. введение синонимов
зарплата == оклад;
сотрудник == кто;

7. определение словосочетаний
общие сведения == фамилия, имя, отчество, год-рождения, должность, группа;

8. описание значения атрибутов
научный сотрудник == снс/мнс/завниг;
темный == черный/синий/коричневый/фиолетовый.

Очевидно, что все пункты, кроме (2) выглядят вполне по-фортовски: возможность макро-определения одних слов-предикатов через другие.

А как быть с "самоидентифицирующимися значениями" т.е. с восстановлением предиката, по константе?
Чтобы "ЦВЕТ СИНИЙ" значило то же, что и "СИНИЙ", но, разумеется, оставалась возможность написать "ОТТЕНОК СИНИЙ".

Т.к. FORTH позволяет все, то, очевидно, возможны самые разные варианты.
Допустим, для определенности, предикаты записываются в виде ": ПРЕДИКАТ ВЫЧИСЛЯТОР ПРОВЕРЯТОР ;", где ВЫЧИСЛЯТОР получает текущее значение (поля БД), а ПРОВЕРЯТОР проверяет его соответствие условию.
Т.е. ЦВЕТ - ВЫЧИСЛЯТОР, а СИНИЙ - ПРОВЕРЯТОР.
(Возвращаясь к пунктам (1 и 3-8 ) видим, что их можно рассматривать как конструктор из ВЫЧИСЛЯТОРОВ и ПРОВЕРЯТОРОВ).
Очевидное решение пункта (2) - проверка словом СИНИЙ флага выполнения ВЫЧИСЛЯТОРА.
Или даже (используя нечеткую логику, раз уж речь идет о понимании естественного языка), поиск наиболее подходящего ВЫЧИСЛЯТОРА для данного ПРОВЕРЯТОРА.
Есть ли в FORTH более естественные решения?
Как сообщить слову о том, что от него хотят что-то необычное?
Очевидно, используя словари.
ВЫЧИСЛЯТОР должен быть словарем.
***

Т.е. СИНИЙ, лежащий в словаре ЦВЕТ берет значение поля "цвет", а в словаре ОТТЕНОК - поля "оттенок". СИНИЙ, лежащий в корневом словаре, идентичен "цветному".
(Или наш словарь настолько умен, что позволяет перенести СИНИЙ из словаря ЦВЕТ в корневой, при объявлении его "самоидентифицирующимся").
Понятно, не хочется плодить одинаковые имена, при этом возникает идея наличия в словарях более неоднозначного соответствия "имя-связь-код" : "одно имя с несколькими связями но одинаковым кодом" и/или "одно имя с несколькими связями, причем, у каждой свой код". Или проще, хранение в словаре не имени, а ссылки на имя.
Неприятность при таком подходе поджидает при наличии в предикате более одного ВЫЧИСЛЯТОРА.
Например, "ИМЯ1 ИМЯ2 ТЕЗКИ".
Т.е. надо иметь четыре словаря для "ИМЯ1 ИМЯ2 ТЕЗКИ", "ИМЯ1 ТЕЗКИ", "ИМЯ2 ТЕЗКИ" и "ТЕЗКИ" (2 в степени N для N ВЫЧИСЛЯТОРОВ, не считая варианта с перестановками - "ИМЯ2 ИМЯ1 ТЕЗКИ").
Т.е. в словаре ИМЯ1 должно быть слово ИМЯ2, тоже являющееся словарем.
Но, самое смешное, если мы готовы записывать в словари не имена, а лишь ссылки на них (и косвенный шитый код), это даже не вызовет особых накладных расходов.
Т.о. мы приходим к разделению словаря на отдельные части: стековую (код), строковую (имена) и списковую.
Это, например, может быть полезно в случае, когда набор операций (слов) некоторого подмножества машин фиксирован, но код этих слов различен.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:36 pm

РАСПОЗНАВАНИЕ ЛИТЕРАЛОВ

Если дело дошло до NUMBER, значит в словаре слово не найдено и надо пытаться понять его другими средствами.
Исторически сложилось:

1. Каждый фортер понимает эту процедуру по-своему. Даже из стандарта его исключили, оставив там >NUMBER и CONVERT. Некоторые относят его к "процедуре обработки ошибки поиска в словаре".
2. Эта процедура должна быть определена в ядре, т.к. через нее проходит цикл интерпретации, но работа с изрядной долей распознанных литералов относится к необязательным расширениям.
3. К распознаваемым литералам относятся только целые числа в текущей системе счисления (в т.ч. двойной длины), и числа с плавающей точкой в десятичной системе счисления.

И все эти три особенности элегантно убираются одним-единственным решением.

1. Во-первых, распознавание литералов - вещь достаточно широко изученная и не надо изобретать никаких велосипедов. Литералы описываются регулярными выражениями, а регулярные выражения распознаются конечными автоматами. Это не только просто, но и эффективно.
2. Конечные автоматы описываются графами, т.е. реализуются в виде связных структур в памяти. И превращение одной структуры в другую сводится просто к перестановке ссылок и дописывании нужных узлов. Т.о. при выполнении простых предосторожностей (в FOBOS текущей версии они, к сожалению, не соблюдены) можно в момент реализации ядра ограничиться только нужными литералами, а остальные легко добавить потом. Все предосторожности - требование формирования ЗНАЧЕНИЯ внутри конечного автомата (чтобы исключить зависимость кода ядра от вида литерала).
3. Регулярные выражения позволяют описать практически любые мыслимые литералы, не ограничивая фортера какими-либо узкими рамками.

Почему этот подход не используется широко? По моему мнению, где-то в районе понимания конечных автоматов проходит верхяя граница программистских знаний микро- и структурных фортеров.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:36 pm

НЕ ЛИТЕРАЛОМ ЕДИНЫМ...

Раз уж механизм регулярных выражений столь мощен, то, может, применить его еще раньше - в WORD? Нет. Это уже чрезмерное усложнение интерпретации. Для распознавания "пробела в конце" регулярные выражения не нужны, а попытка считать словом что-то "более регулярное", наложит на язык совершенно не нужные ограничения.
***

Сказка про белого бычка. Формализуешь одну часть FORTH, придется пересматривать остальные, изменения там вызовут необходимость что-то менять здесь... Нет, уж, чтобы не заниматься вытаскиванием себя из болота за волосы, ограничимся "регулярным" NUMBER.
***

Другое дело, если FORTH вынужден интерпретировать что-то написанное на регулярном языке: html, xml или C. Тогда, действительно, придется распознавать лексемы и запускать слова грамматического анализа. Но это совсем другая история...
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:38 pm

КОНЕЧНЫЕ АВТОМАТЫ И NUMBER

Надо заметить, что все ниже написанное справедливо независимо от того, как называется процедура распознавания чисел и к какому месту FORTH она прицепляется (например выносится в отдельный [псевдо]словарь или вызывается как процедура обработки ошибок FIND (NOTFOUND).
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:40 pm

КЛАССИКА
Как помните, Броуди приводил пример реализации NUMBER в виде (надеюсь, вы уже можете читать код с листа):

: NUMBER?
DUP 1+ С@ ASCII - = DUP >R -1 DPL ! 0 0 ROT
BEGIN CONVERT DUP C@ DUP ASCII : = SWAP ASCII . ASCII / 1+ WITHIN OR
WHILE 0 DPL ! REPEAT
-ROT R> IF DNEGATE THEN ROT С@ BL = ;
: NUMBER
NUMBER? NOT ABORT" ?" ;

Код для CONVERT не приводится (однако, замечается, что оно изменяет DPL).
***

У Баранова и Ноздрунова:

: DIGIT
0 ROT ROT 0 DO I ALPHA OVER - IF 2DROP I -1 0 LEAVE THEN LOOP DROP ;
: CONVERT
BEGIN 1+ DUP >R C@ BASE @ DIGIT
WHILE SWAP BASE @ UM* DROP ROT BASE @ UM* D+
DPL @ 1+ IF DPL 1+! THEN R> REPEAT R> ;
: NUMBER
0 0 ROT DUP >R COUNT OVER + OVER С@ С" - = DUP >R SWAP >R
IF ELSE 1- THEN -1
BEGIN DPL ! CONVERT DUP R@ <
WHILE DUP С@
С" . <> IF RDROP RDROP R> BADWORD THEN 0 REPEAT
DROP RDROP R> IF DNEGATE THEN RDROP ;

Можно выделить стандартные куски:

- "0 0 ROT" - на стек, под рабочие переменные кладется "накопитель числа" - там будут суммироваться считанные цифры. Cуммирует их CONVERT ("SWAP BASE @ UM* DROP ROT BASE @ UM* D+"), т.о. техника напоминает вывод чисел: там "скобки" <# и #> создают некоторый стековый контекст, внутри которого может работать слово #. Здесь контекст создает NUMBER, а CONVERT вызывается прямо из него. Если мы захотим использовать CONVERT само по себе, то придется создавать этот контекст самим (т.к. он документирован - "ud1, ca1 --> ud2, ca2", это не сложно). Более того, у Броуди в этот контекст входит и DPL.
- "BEGIN ... CONVERT ... WHILE ... REPEAT" - повторять считывание последовательностей цифр, пока это возможно и разделены они "допустимыми символами". Положение последнего разделителя запоминается в DPL. В обоих вариантах распознаются полько два вида чисел: целые (без разделителей) и целые длинные (с разделителями). Если распознавать и другие виды чисел, то придется сделать анализ разделителей более сложным, но цикл вызова CONVERT практически не изменится.
- ABORT" или BADWORD - прекращение интерпретации при неудаче распознавания числа. Это неудобно в том случае, если после неудачи NUMBER надо продолжить анализ слова (см. у Мура).
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:49 pm

FOBOS - ПЕРВАЯ WIN-ВЕРСИЯ

Так как я в процессе разбора WIN-сообщений обнаружил, что получил достаточно универсальный способ изготовления конечных автоматов, то решил применить его и в NUMBER. Три основных части этой реализации:

Сам конечный автомат. Я засунул туда наиболее востребованные варианты чисел, пришедшие в голову:

ГруппаУзелСимволБратСынКод
1. Пока ничего не считаноn1PLUS'+'n1MINUSn2POINTCN+ CNDIG
n1MINUS'-'n1POINTn2POINT-1 NDIG ! CN+ CNDIG
n1POINT'.'n1DIGn9DIGDUP DPL ! CN+ CNDIG
n1DIG'9'nERRn3POINTCN@ CNEXP
ОшибкаnERR000-1
2. Считан ведущий знак (+/-) n2POINT'.'n2DIGn9DIGDUP DPL ! CN+ CNDIG
n2DIG'9'nERRn3POINTCN@ CNEXP
3. Считано целое числоn3POINT'.'n3EXPn4EXPDUP DPL ! CN+ CNEXP CNDIG
n3EXP'E'nNULn6PLUSCN+ CNDIG
Число считано полностьюnNUL0nERR00
4. Считаны целое число и точкаn4EXP'E'n4DIGn6PLUSCN+ CNDIG
n4DIG'9'nNULn5EXPCN@ CNEXP
5. Считано число с точкойn5EXP'E'nNULn6PLUSCN+ CNDIG
6. Считаны мантисса и признак степени (e)n6PLUS'+'n6MINUSn7DIGCN+ CNDIG
n6MINUS'-'n6DIGn7DIG-1 NFLT ! CN+ CNDIG
n6DIG'9'nNULnNULCN@
7. Считаны мантисса, признак степени и знак порядкаn7DIG'9'nERRnNULCN@
9. Считана точкаn9DIG'9'nERRn5EXPCN@ CNEXP

Таинственные "группы" и "узлы" появились из известной программистской хитрости - "дерево любого вида представимо в виде бинарного, имеющего связи "старший сын" и "младший брат"". Так что "группы" - это состояния конечного автомата, а "узлы" - ведущие из состояния стрелки.
На первый взгляд, автомат страшноватенький и непонятно зачем придуман.
Во-первых, я не думаю, что "классический NUMBER", который научат распознавать числа с плавающей точкой, будет выглядеть намного понятнее. Во-вторых, прелесть конечного автомата в том, что его можно научить распознавать и другие литералы, а не только числа. Вдруг понадобится?
Если вы смотрите внимательно, то можно видеть ошибку: использование символа '9' для сигнала о распознании числа ошибочно сигнализирует о числе, если основание системы счисления меньше 10. В этом случае символ '9' должен распознаваться как ошибка распознавания числа. Так что, безопасным будет использования какого-либо символа '0' - это всегда цифра - или какого-либо спецсимвола, лежащего за пределами множества символов.

Второе - слова распознавания примитивов, использованные в атомате:
CN@ - взять первый символ оставшейся строки;
CN+ - тоже самое, только с удалением этого символа из строки и проверкой на то, что строка кончилась;
CNEXP - проверка на то, не оказался ли считанный символ признаком порядка (e), т.е. надо срочно переходить к изменению контекста под распознавание вещественных чисел, установке флагов и т.п. (чтобы не запутаться принимается, что такие числа должны быть записаны в десятичной системе счисления);
CNDIG - попытка прочесть в строке число (последовательность цифр). Включает вызов >NUMBER или, то же самое, CONVERT. Такая сложность вызвана просто тем, что такое слово (кстати, стандартное) у меня уже на тот момент было. CNDIG стало просто простейшей его оболочкой, подгоняющей слово под требования конечного автомата (возврат символа '9').

Третье - слово для работы с конечным автоматом - RECEPT. Его шитую версию (и алгоритм) уже приводил, теперь привожу кодовую (c минимальными отличиями от тогдашней - с тех пор поменял в косметических целях местами поля "эталон" и "сын"). Конечно, с задней мыслью - сам забыл, как она работает, а перед вставкой в новую версию надо бы все подчистить.

Код:
    ; символ, адрес узла -- ...
     ; (вершина стека - в ebx, остальное - в sp-стеке)
     mov eax, [esp]
     @@: cmp eax, [ebx + 8] ; сравниваем символ с эталоном
     jz @F
     mov ecx, ebx ; на случай, если брата нет
     mov ebx, [ebx + 4] ; переход к брату
     or ebx, ebx
     jnz @B
     mov ebx, ecx ; если брата нет, все равно исполняем
     @@: add esp, 4 ; символ больше не нужен
     mov eax, [ebx] ; сын
     or eax, eax
     jz @F
     mov [ebp], ebx ; сохранение адреса узла
     mov [ebp + 4], esi ; и указателя шитого кода в стеке возвратов
     add ebp, 8
     mov esi, lRECD ; надеемся вернуться
     @@: mov [ebp], esi ; здесь одинаково и для сына и для самого
     add ebp, 4 ; это значение будет снято EXIT кода узла
     mov esi, ebx
     pop ebx ; снимаем со стека адрес узла
     add esi, 12 ; адрес шитого кода узла
     Next ; переход к выполнению кода узла
     lRECR: sub ebp, 8 ; переход к сыну с новым сообщением
     mov esi, [ebp + 4] ; указатель шитого кода
     mov eax, [ebp] ; это адрес узла
     push ebx ; новый эталон (надеемся, его положил сюда код узла)
     mov ebx, [eax] ; новый узел (сын)
     jmp @RECEP
     lRECD:
     DD lRECR ; заглушка для имитации шитого кода

Тонкое место здесь - переход к шитому коду и обратно. При этом надо отличать - имеет место вызов кода узла, имеющего сыновей, когда его код преследует основную цель - формирование нового символа для распознавания и переход после этого к исследованию сыновей, и вызов узла без сыновей, когда код может делать, что угодно и его завершение вызывает завершение работы автомата.
В отличие от шитой версии нет надобности хранить в стеке адрес текущего узла - RECEPTING кажется вызываемым им словам "прозрачным".
Данный пример, плюс ко всему, показывает нам пример нестандартного шитого кода - слова выполняются не друг задругом, а под управлением некоторой последовательности символов. Видно, что при некоторой доле кодового трюкачества такие фокусы вполне осуществимы и в прямом шитом коде, а не только в косвенном.

Какие недостатки сподвигли меня отказаться от этой версии?
- С одной стороны, совсем не обязательно, что все эти разносолы: длинные целые, вещественные с фиксированной и плавающей точкой понадобятся в программе;
- С другой - а вдруг понадобятся другие литералы?
- Места пристыковывания конечного автомата к обычному FORTH-кода выглядят не очень опрятно.


Последний раз редактировалось: Gudleifr (Вт Июн 20, 2017 9:46 pm), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:53 pm

FOBOS - НОВАЯ ВЕРСИЯ

Основная идея этой версии - сделать конечный автомат NUMBER полностью открытым для FORTH-программиста. Благодаря этому удалось сократить изначальный конечный автомат до:

ГруппаУзелСимволБратСынКод
До начала распознаванияnSTART00nMINUS0 NDIG ! 0 OVER COUNT CN@ CNDIG
Ждем число или минусnMINUS'-'nDIGnDIG-1 NDIG ! CN+ CNDIG
Ждем числоnDIG'0'nERRnNULCN@
ОшибкаnERR0002DROP DROP BADWORD
Число считаноnNUL0nERR02DROP NIP NDIG @ IF NEGATE THEN

Т.е. изначально распознается только простейший случай - целое число одинарной длины.
Можно заметить, что появилось новое состояние - nSTART, которое обеспечивает формирование контекста, чтобы самому NUMBER окончательно стало до лампочки, что распознавать. В этих же целях код выхода из контекста добавлен в состояния nERR и nNUL. Теперь действие NUMBER полностью определяется автоматом. Поменяем автомат - получим новый NUMBER.


Последний раз редактировалось: Gudleifr (Вт Июн 20, 2017 9:48 pm), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Июн 15, 2017 2:54 pm

ЕЩЕ ОДНА ПРОБЛЕМА

Забудем про способ распознавания литералов. Важно, что после успеха такого распознавания на стеке (стеках) остается что-то, зависящее от типа литерала: число, длинное число, вещественное, комплексное... Следующим шагом является, в зависимости от значения переменной STATE, либо оставление этого значения как есть, либо компиляция его в словарь (вместе с извлекателем). Т.к. значение может быть разных типов, то компиляция будет производится по-разному, пользуясь флагами, полученными при распознавании. Т.е. налицо избыточное усложнение интерпретатора: сначала распознай и отчитайся о готовности, а потом анализируй заново (это хорошо, пока литералы простые, а если нужно для их разбора какие-то ресурсы выделять/освобождать?). Кроме того, подобный подход ограничивает число распознаваемых типов заранее предусмотренными.
Конечно, есть обходные пути: проверять STATE внутри NUMBER (где-то в nNUL), а не внутри интерпретатора. Это неудобно, т.к. компиляция литералов будет происходить совсем не там, где происходит компиляция слов. Второй обходной путь - использование спец-лексиконов, заточенных под распознавание разных типов. Однако, это просто обзывание разными словами тех же самых сложно-условных выражений.
Самый уродливо-прекрасный способ - "сделать наоборот", т.е. скомпилировать литерал в словарь, а, если дело происходит в режиме исполнения, выполнить скомпилированное. К сожалению, на этом пути стоит преграда - компилировать некуда, в момент распознавания литерала он физически занимает вершину словаря (см. выше эти ужасные DROP-ы). Да и работать с вершиной словаря не так удобно, как со стеком.
Т.о. единственное, что мы можем при распознавании - сохранить адрес слова, компилирующего литералы такого в какой-либо переменной (на стеке хранить неудобно - процедуры распознавания его здорово перелопачивают). А, вот, куда его девать после окончания распознавания? На стек, явно, класть не стоит - он не всегда нужен.
Оставить в переменной? Можно, но, ограничивает наши возможности компиляции одним словом (читай определенным набором типов). Вдруг, мы захотим добавить какие-нибудь параметры? Возвращаемся, по сути, к первоначальному набору флагов-параметров - DPL и ему подобных.
Оставшийся вариант - скомпилировать в словарь. Т.о., если мы в режиме исполнения, делать ничего не надо, а если в режиме компиляции - надо запустить скомпилированное слово, которое скомпилирует вместо себя нужный извлекатель данных из шитого кода и данные со стека.
Более того, если литерал зело сложен, то можно скомпилировать цепочку слов, производящих перед компиляцией сложную обработку данных, зависящих от хода разбора.
Т.о. кроме выполнить и компилировать, возможен и третий вариант - скомпилировать, а затем - выполнить...
Ограничение то же самое - надо отслеживать, чем в настоящее время занята вершина словаря.
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Gudleifr в Чт Фев 01, 2018 12:18 pm

СОВМЕЩЕНИЕ FIND И NUMBER

Т.к. в последнее время все чаще свожу задачи не к одной FORTH-машине, но к нескольким, то частные решения использую гораздо чаще универсальных.

Понадобился мне тут распознаватель html-текстов с моего форума. Ну перекодировщик с юникода в 1251 написал быстро. А дальше? Нужная мне информация оказалась размазанной по всему файлу, разделенная тоннами тегов. Хоть перцептрон паяй. Решил пойти FORTH-путем: постепенного накопления слов, отвечающих за распознавание каждый своего куска.

Сам "FORTH" (на Perl занял всего десяток строк):

$l = <>;
while ($l) { # ЭТО QUIT
$r = 0;
foreach $i (sort keys %voc) { # FIND
if ($voc{$i}[0]) {
if ($l =~ /$voc{$i}->[1]/) { # WORD
$l = $2;
$r = 1;
$voc{$i}->[2]($1); # EXECUTE
last
} } }
$l = <> unless ($r) # ЭТО ACCEPT
}

А СЛОВАРЬ выглядит примерно так:

%voc = (

forum => [ 0, "<a class=\"forumlink\" href=\"http:\/\/gudleifr\.forum2x2\.ru/f(.*?)<\/a>(.*)", sub {
$t = shift;
$t =~ /([0-9]*)-forum\">(.*)/;
print "ПОДФОРУМ: $1 $2 \n";
$voc{path}[0] = 0 } ],

topic => [ 0, "<a class=\"topictitle\" href=\"http:\/\/gudleifr\.forum2x2\.ru/t(.*?)<\/a>(.*)", sub {
$t = shift;
$t =~ /([0-9]*)-topic\">(.*)/;
print "ТЕМА: $1 $2 \n";
$voc{forum}[0] = 0;
$voc{path}[0] = 0 } ],
....

Первое поле - флаг CONTEXT, второе - страшное регулярное выражение, позволяющее выбрать из ПОТОКА слово, третье - код последнего.
И что мы видим? Необходимость CONTEXT, т.к. в разных местах html имеет смысл искать разные слова. (В примере можно рассмотреть, что за словом topic не может следовать слово forum, и тем более - path). Очевидно, вместо неуклюжего флага имеет смысл сделать CONTEXT списком, более того, списком упорядоченным (я обошелся тупым выбором имен в алфавитном порядке).

Что еще ""очевидно"?
Еще кусочек СЛОВАРЯ:

txt_end => [ 0, "(.*)(.*)", sub {
$t = shift;
print "$t\n";
$r = 0 } ],

Здесь можно видеть, что некоторые слова хотят раньше времени завершить цикл QUIT, сожрав строчку до конца (заведомо пустая подстрока "(.*)" в шаблоне, обнуление $r). Сразу возникает идея засунуть в СЛОВАРЬ дополнительную информацию: например, флаг остатка строки и/или списки управления CONTEXT... И есть, ведь, структурные фортеры, вводящие в свои словари множество пропертей и эвентов.

Так что, все эти фичи, которые бывалыми фортерами втюхиваются молодежи как обязательные "ката", родятся сами, как только человек решит пойти FORTH-путем. Идея того, что эти решения - суть естественные последствия писания самого тупого из возможных интерпретаторов, кажется им чуть ли не кощунством.

P.S. Т.о. методом тыка я построил СЛОВАРЬ, который вырезал из html то, что мне нужно...
P.P.S. Теперь мне нужна машина, которая объединит эти тексты в БД, связанную гиперссылками. Т.к. слова будут не только печататься, но и делать что-то более интеллектуальное, то видимо, попутно изобретется и СТЕК...
avatar
Gudleifr
Admin

Сообщения : 725
Дата регистрации : 2017-03-29

Посмотреть профиль

Вернуться к началу Перейти вниз

Re: Распознавание символа - FIND и NUMBER

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения