Лексер и алгоритм поиска по файлам

Научно-технические вопросы применения русского языка в программировании. Проекты с сайта программирование-по-русски.рф, кроме ЯОС . Информация об организациях и людях, использующих или изучающих русский язык в программировании. Сравнение операционных систем.
Ответить
БудДен
Сообщения: 2839
Зарегистрирован: 07.10.18 14:01

Лексер и алгоритм поиска по файлам

Сообщение БудДен » 13.06.21 22:31

Предлагается такой алгоритм лекс. разбора:

- под буквой понимается русская или латинская буква, а также цифра. Цифра считается заглавной буквой.
- один знак подчёркивания, с двух сторон граничащий с буквой или цифрой, является лексемой типа "белое поле";
- любая последовательность пробелов, табуляций, переносов строки (CR/LF т.е. ВК/ПС) является лексемой типа «Белое поле»;
- аббревиатура: последовательность из более чем одной заглавной буквы (или цифры), перед которой находится не заглавная буква (цифра), и за которой идёт не заглавная буква (цифра) - она является лексемой типа «Слово»;
- обычное слово: последовательность из букв(цифр), перед которой не буква, и у которой последующие символы - прописные буквы, считается лексемой типа «Слово»;
- слово-продолжение: последовательность, следующая за лексемой типа «Слово», начинающаяся с буквы (или цифры), продолжающаяся строчными буквами и за которой идёт либо вообще не буква, либо буква в верхнем регистре (или цифра), также считается лексемой типа «Слово»
- любой другой символ образует односимвольную лексему
- знаки препинания, допустимые в идентификаторе, сразу преобразуются в те знаки, которые они заменяют.
- символ с кодом 0 - тоже однобуквенная лексема (это нужно для бинарных файлов, содержащих текстовые фрагменты)

Примеры (сначала идёт строка, потом метазнак =>, потом лексемы строки, разделённые пробелами. Лексемы типа «Белое поле» обозначаются словом "ПРОБЕЛ"

Код: Выделить всё

(* это комментарий*)
=>
( * ПРОБЕЛ это ПРОБЕЛ комментарий * )

3.14
=>
3 . 14

аЗачемЭтоЗатеяли¿
=>
а Зачем Это Затеяли ¿
и

Код: Выделить всё

Языки˛сделанныеВ_СССР˛до1966года
=>
языки ˛ сделанные В СССР ˛ до 1966 года

"строковой литерал\n"
=>
" строковой ПРОБЕЛ литерал \ n "
Для поиска строки в файле изучаемый файл разбивается таким лексером, и строка тоже разбивается. Далее выкидываются все пробельные лексемы. Далее есть какой-то метасимвол (пока пусть будет ☼, но вопрос о метасимволах пока вообще не решаем, а откладываем). При поиске происходит следующее:

- все буквы приводятся к нижнему регистру
- знаки в парах «¿» и «?», «˛» и «,» «!» и «¡», «ˉ» и «-» считаются одинаковыми
- все лексемы с пробелами выкидываются.
- метасимвол «☼» в рамках слова означает меняющееся окончание слова; пока неясно, как именно тут сопоставлять, и выработка решения по этому вопросу будет самой сложной частью, но которую пока откладываем; поэтому ☼ означает произвольные буквы в количестве от 0 до 2.

Успехом поиска является совпадение последовательности лексем, полученных из искомой строки, с подпоследовательностью лексем, полученных из файла. Предлагаю осуждать.
Последний раз редактировалось БудДен 22.06.21 18:36, всего редактировалось 12 раз.

БудДен
Сообщения: 2839
Зарегистрирован: 07.10.18 14:01

Re: Лексер и алгоритм поиска по файлам

Сообщение БудДен » 14.06.21 22:19

Поскольку замечаний не поступило, считаем алгоритм утверждённым.

Павиа
Сообщения: 136
Зарегистрирован: 23.05.19 21:28

Re: Лексер и алгоритм поиска по файлам

Сообщение Павиа » 15.06.21 09:37

- все буквы приводятся к верхнему регистру
Надо к нижнему. Так как заглавных буквы реже встречаются, то перевод к нижнему будет быстрее работать.
- последовательность из одного или нескольких знаков подчёркивания, с одной или двух сторон граничащая с буквой или цифрой, является лексемой типа "белое поле";
Почему бело поле? Всю жизни _mul - были лексемами рода "слова".
- любая последовательность пробелов, табуляций, переносов строки является лексемой типа «Белое поле»;
Файн ридер добавляет
PS - знак разделения парагрофов
LS - знак разделения листов

PS:WideChar=#$2029;
LS:WideChar=#$2028;
- последовательность из более чем одной буквы в верхнем регистре или цифры, перед которой не буква в верхнем регистре, начинающаяся с буквы и за которой идёт не цифра и не буква в верхнем регистре, является лексемой типа «Слово»;
Как сложно. Слово это то что начинается с буквы или знака подчеркивания. И содержит или букву или цифру или знак подчёркивания или знак дефис или перенос.
Не букв в верхнем регистре не бывает.
- последовательность, перед которой начало файла или не буква (рус/лат), начинающаяся с буквы, возможно, продолжающаяся цифрами или строчными буквами, и после которой идёт либо вообще не буква, либо буква в верхнем регистре - считается лексемой типа «Слово»;
- последовательность, следующая за лексемой типа «Слово», начинающаяся с буквы, продолжающаяся строчными буквами и за которой идёт либо вообще не буква, либо буква в верхнем регистре, также считается лексемой типа «Слово»

Это вообще не понял.

Код: Выделить всё

function IsAlfa(const ch:WideChar):Boolean;
begin
Result:=(('А'<=Ch) and (CH<='Я') ) or (Ch='Ё') or
        (('а'<=Ch) and (CH<='я') ) or (Ch='ё') or
        (('A'<=Ch) and (CH<='Z') ) or
        (('a'<=Ch) and (CH<='z') );
end;

function isUpAlfa(const ch:WideChar):Boolean;
begin
Result:=(('А'<=Ch) and (CH<='Я') ) or (Ch='Ё') or
        (('A'<=Ch) and (CH<='Z') );
end;


function IsWordAlfa(const ch:WideChar):Boolean;
begin
Result:=IsAlfa(ch);
result:=Result or ('_'=Ch) or ('-'=Ch) or ('¬'=Ch);
end;

function IsDigital(const ch:WideChar):Boolean;
begin
Result:=CharInSet(Ch, ['0'..'9']);
end;

function ReadWord(var Text:TText):TSimvol;
var
  s:String;
begin
 S:='';
 if IsWordAlfa(FCurrentChar(Text)) then
   begin
   if (FCurrentChar(Text)='-') then
       S:=S+FReadChar(Text)
     else while (IsWordAlfa(FCurrentChar(Text))) or (IsDigital(FCurrentChar(Text))) do
     begin
       S:=S+FReadChar(Text);
     end;
     {Перенос}
     if (s[Length(s)]='-') or (s[Length(s)]='¬') then
        begin
        if IsNewLineChar(FCurrentChar(Text)) then
           begin
             Delete(s, Length(s),1);
             ReadNewLine(Text);
             while (IsWordAlfa(FCurrentChar(Text))) or (IsDigital(FCurrentChar(Text))) do
               begin
               S:=S+FReadChar(Text);
               end;
           end;
        end; {}
   end;
 Result.value:=s;
 Result.Kind:=skWord;
end;
#^-+*/\|♥?!.,;:&˛¿¡„“«'»"ˉ<>=
В текстах часто встречается
mdash:WideChar=#$2014; // Длинное тире
HorizontalEllipsis:WideChar=#$2026; // Многоточие

У меня набор по более будет, у вас скобок не хватает и других знаков пунктуации.

Код: Выделить всё

function IsPunctuation(const ch:WideChar):Boolean;
begin
Result:=CharInSet(Ch, ['!', '"', '#', '$', '%', '&', '''', '(', ')', '*',
                       '+', ',', '-', '.', '/', ':', ';', '<', '=', '>',
                       '?', '@', '[', '\', ']', '^', '`', '{', '|', '}',
                       '~']);
Result:= Result or (ch=mdash) or (ch=HorizontalEllipsis)
                or (ch='«') or (ch='»');
end;
Последний раз редактировалось Павиа 15.06.21 10:04, всего редактировалось 1 раз.

Павиа
Сообщения: 136
Зарегистрирован: 23.05.19 21:28

Re: Лексер и алгоритм поиска по файлам

Сообщение Павиа » 15.06.21 09:43

https://yadi.sk/d/P7O9XfAqlZBS8Q
https://yadi.sk/d/KNu9ja9GjnenRQ
Вот мои наработки.По качеству разбиения обгоняют Наташу, правда давно сравнивал.
https://github.com/natasha/razdel

БудДен
Сообщения: 2839
Зарегистрирован: 07.10.18 14:01

Re: Лексер и алгоритм поиска по файлам

Сообщение БудДен » 15.06.21 10:40

Спасибо за отзыв! Да, скобок недописал, поправлю. Про подчёркивание напишу ответ фразами, состоящими из валидных идентификаторов в ЯОС, составленных по соглашению о словочетаниях (возможно, некоторые слишком длинные):

СмыслЗаморочекСо«словом»и_подчёркиваниемˉВ_следующем.
ИдентификаторыЧастоЯвляютсяСловосочетаниями˛ноПробеловВ_идентификатореНеДопускается. ВместоНихМожноРазделятьСлова,выделяяКаждоеСловоС_заглавнойБуквы.
НоВозникаютПроблемыС_однобуквеннымиСловами˛которыеЛегкоПерепутатьС_аббревиатурами.

взятьХотяБыСО_дляПримера˛чтоОзначает«StackOverflow»˛ноМожноБылоБыПонятьКак«сБуквойО»

В_этихСлучаяхЯ_используюПодчёркиваниеПередНачаломСлова˛аСамоСловоНачинаетсяСоСтрочнойБуквы.
ИменноПоэтомуПодчёркиваниеПриравниваетсяК_пробелу.
В_ЯОС_подчёркиваниеВ_словах˛подобных«_mul»,втречаетсяРедко.

Но можно поменять правило: подчёркивание считается пробелом только в том случае, если оно ограничено
буквами или цифрами и слева, и справа. Потому что по моему соглашению об отличении аббревиатур от границ
слов подчёркивание может стоять только внутри слова. В этом случае, _mul и mul перестанут сливаться. Хотя сольются
mul_int и mulInt. В любом случае, чем сложнее алгоритм, тем больше у него всяких «углов», где может случиться сбой
В любом случае, способов поиска будет более одного, и придётся их сочетать, если возникнут проблемы. Можно, например, чтобы
дополнительная "примочка" к алгоритму анализировала находки и специально выявляла случаи таких совпадений, выдавая предупреждение,
что будьте внимательны.

БудДен
Сообщения: 2839
Зарегистрирован: 07.10.18 14:01

Re: Лексер и алгоритм поиска по файлам

Сообщение БудДен » 16.06.21 12:52

Нашёл у себя в закладках: https://github.com/returntocorp/semgrep - перекликается с идеей алгоритма, во всяком случае, на уровне заголовка.

Ответить