Сплиттер -- простейший лексический анализатор разбивающий входной текст на слова (токенайзер).
У данного типа анализаторов есть следующие проблемы -- разделение подряд идущих слов и группировка в текстовые блоки состоящие из мелких слов. Первая не ???решаема???, из-за особенностей работы сплиттера. Вторая может быть решена с помощью эскейп-последовательностей. Но при это появляется проблема экранирования вложенных эскейп-символов и символов-экранирования. Попробуем решить данную проблему используя два эскейп-символа -- открывающий и закрывающий.
Грамматика описывающая входные строки сплиттера:
<S>::=<text> #eoln
<text>::=
| <token>
| <token> <delims> <text> ;последовательность
| <delims> <text>
<token>::=
| <word> ;слово
| #beg <group> #end ;группировка
| #beg <group>
| #beg #end
| #beg
| <word> <token> ;конкатенация
<word>::=
| #!DELIM_BEG_EOLN
| #!DELIM_BEG_EOLN <word>
<group>::=
| #!END_EOLN
| #!END_EOLN <group>
<delims>::=
| #delim
| #delim <delims>
#delim:: ;разделители
#eoln:: ;конец строки
#beg:: ;начало группы
#end:: ;конец группы
#!END_EOLN:: ;все, кроме символа конца группы и конца строки
#!DELIM_BEG_EOLN:: ;все, кроме символов начала группы и символов разделителя и конца строки
Продукционная грамматика сплиттера:
<S>::=<text> #eoln
<text>::=
| <token> !out(tok), tok=""!
| <token> !out(tok), tok=""! <delims> <text>
| <delims> <text>
<token>::=
| <word> ;слово
| #beg <group> #end
| #beg <group>
| #beg #end
| #beg
| <word> <token>
<word>::=
| #!DELIM_BEG_EOLN !tok+=ch!
| #!DELIM_BEG_EOLN !tok+=ch! <word>
<group>::=
| #!END_EOLN !tok+=ch!
| #!END_EOLN !tok+=ch! <group>
<delims>::=
| #delim
| #delim <delims>
#delim::
#eoln::
#beg::
#end::
#!END_EOLN::
#!DELIM_BEG_EOLN::
После преобразования в недетерменированный конечный автомат:
После минимизации и оптимизации:
После преобразования в детерминированный конечный автомат:
Сравните с построенным вручную:
TODO:перерисовать
TODO:добавить действия
Реализация на javascript.
function splitter(input, delims=" \t\n", beg='<', end='>'){
var output = [];
var tok="";
var state=0;
var pos=0;
while(state != -1){
let ch = (pos<input.length)?input[pos++]:0;
switch(state){
case 0:
if(ch == beg){
state = 2;
}else if(ch === 0){
state = -1;
}else if(delims.indexOf(ch)!=-1){
state = 0;
}else{
tok+=ch;
state = 1;
}
break;
case 1:
if(ch == beg){
state = 2;
}else if(ch === 0){
output.push(tok);
state = -1;
}else if(delims.indexOf(ch)!=-1){
output.push(tok);tok="";
state = 0;
}else{
tok+=ch;
state = 1;
}
break;
case 2:
if(ch == end){
state = 1;
}else if(ch === 0){
output.push(tok);
state = -1;
}else{
tok+=ch;
state = 2;
}
break;
}
}
return output;
}
Результаты тестирования:
splitter("abc 123 \t < > <<> > 123<456> ");
Array [ "abc", "123", " ", "<", ">", "123456" ]