Здравствуйте, Воронков Василий, Вы писали:
ВВ>Кстати, забыл спросить. А как сделать так, что лексер не создавал строк? 
Надо ведь как-то проверить что разобранный идентификатор является ключевым словом.
Это проблема. Я сйчас создаю. Правда только для идентификаторов. Но генерируемый парсер может эту проблему решить. Ведь распознование строк точно так же можно сделать через ДКА. Только код ДКА может оказаться большим если строк много.
Насколько я знаю Кока тоже создает строки для идентификаторов. Но ей по фигу так как она все равно отплевывает их в поле val токена.
Еще одним решением может быть создание ручной реализации хэш-таблицы способной работать на подстроке. В приципе это не сложно, так как можно просто покоцать стандартный Dictionary<K,V>. За одно его можно ускорить если отказаться от виртуальных вызовов при рассчете хэша и сравнении.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Здравствуйте, VladD2, Вы писали:
Возникла тут одна идейка — она как раз и предполагает создание некоторой собственной хэш-таблицы. Основная суть такая — на настоящий момент мы вычитываем идентификатор до самого конца и уже только потом начинаем его искать — тут без создания строки не обойтись. Решением может быть поиск который производится по одновременно с чтением идентификатора (предполагается разумеется что хэш-таблица будет сохранять состояния и сама процедура поиска это всегда синхронная операция). Концептуально это выглядит примерно так:
class StringTable
{
private readonly ArrayList Buckets = new ArrayList();
private Bucket lastBucket;
private int lastOffset = -1;
public StringTable()
{
}
public void Add(string value)
{
if (value == null || value.Length == 0)
throw new ArgumentException();
InternalAdd(value, 0, Buckets);
}
private void InternalAdd(string value, int offset, ArrayList buckets)
{
char c = value[offset];
foreach (Bucket b in buckets)
if (b.Char == c)
{
if (offset == 2 || value.Length == offset + 1)
b.Strings.Add(value);
else
InternalAdd(value, offset++, b.Buckets);
return;
}
Bucket newBuck = new Bucket(c);
buckets.Add(newBuck);
if (offset == 2 || value.Length == offset + 1)
newBuck.Strings.Add(value);
else
InternalAdd(value, offset++, newBuck.Buckets);
}
public bool FindSegment(char c)
{
if (++lastOffset < 2)
{
foreach (Bucket b in lastBucket == null ? Buckets : lastBucket.Buckets)
if (b.Char == c)
{
lastBucket = b;
return true;
}
}
else
foreach (string s in lastBucket.Strings)
if (s.Length >= lastOffset + 1 && s[lastOffset] == c)
return true;
return false;
}
public void ResetSearch()
{
lastBucket = null;
lastOffset = -1;
}
}
class Bucket
{
public readonly char Char;
public readonly ArrayList Buckets = new ArrayList();
public readonly StringCollection Strings = new StringCollection();
public Bucket(char c)
{
Char = c;
}
}
Поиск соответственно осуществляется так:
Console.WriteLine(table.FindSegment('i'));
Console.WriteLine(table.FindSegment('f'));
Console.WriteLine(table.FindSegment('f'));
Output:
True
True
False
Чего думаешь?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, Воронков Василий, Вы писали:
ВВ>Чего думаешь?
Думаю, что это страдания. Эта область давно изучена наукой и в ней найдено всего два достойных решения.
1. Использования хэширования. То о чем я тебе говорил. Создать специализированную хэш-таблицу которая будет работать не с целими строками, а с подстроками. Для этого нужно раздраконить хэш-таблицу из фрэймворка.
2. Создать генератор ДКА разбирающего строку. Ради эксперемента написал генартор ДКА для произвольного набора строк. Вот его код:
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
using CharMap = System.Collections.Generic.Dictionary<char,
System.Collections.Generic.List<string>>;
class Program
{
static string _strs =
"using assembly event field method param property return "
+ "type typevar namespace void where class struct new partial "
+ "interface enum delegate base this ref out __arglist params "
+ "public protected internal private unsafe abstract sealed "
+ "static object string sbyte byte short ushort int uint "
+ "long ulong char extern override readonly virtual volatile const "
+ "implicit explicit operator add remove float double decimal "
+ "bool get set true false is as stackalloc checked unchecked "
+ "if else switch while do for foreach in break continue yield "
+ "throw lock fixed case default null typeof sizeof try finally "
+ "catch goto";
static void Main(string[] args)
{
File.WriteAllText(@"..\..\dfa.cs", Make.Dfa(_strs.Split(' ')));
}
}
class Make
{
public static string Dfa(string[] strs)
{
StringBuilder str = new StringBuilder(1024);
// Сортировка не обязательна. Просто так получается более читабельный код.
Array.Sort(strs);
// Генерируем класс с функцией-распознователем.
// Внутренности функции-распознователя генериуются отдельным методом.
str.AppendFormat(@"
class Dfa
{{
public static int CheckStr(string text, int start)
{{
{0}
return -1;
}}
}}
", MakeLevel(strs, 2));
return str.ToString();
}
/// <summary>
/// Рекурсивная функция генерирующая распознования одного уровня символов.
/// </summary>
/// <param name="strs">Набор строк для которых нужно сгенерировать распознование
/// </param>
/// <param name="level">Уровень вложенности. Используется как для корректноой
/// генерации отступов, так и для рассчета длинны строк.</param>
/// <returns></returns>
private static string MakeLevel(string[] strs, int level)
{
StringBuilder str = new StringBuilder(1024);
CharMap charMap = MakeDic(strs);
// Генерируем проверку выхода за конец строки и switch для данного уровня.
str.Append(
@"
if (start > text.Length)
return -1;
switch(text[start])
{
");
foreach (KeyValuePair<char, List<string>> pair in charMap)
{
str.AppendFormat(
@" case '{0}':
{{
", pair.Key);
// Удаляем у всех строк в списке первый символ (мы ведь его уже
// обработали). При этом если строка пустая, то она удаляется из списка.
string[] nextStrs = RemoveFirstChars(pair.Value);
// Опримизации код с целью сократить его объем.
if (nextStrs.Length == 1) // если остался один альтернатива?...
{
string ident = nextStrs[0];
if (ident.Length == 1) // если осталось проверить один символ строки...
{
// Генерируем проверку одного символа строки. Если она не удачна,
// то или возвращаем -1 (строка не распознана), или длинну строки,
// если nextStrs.Length != pair.Value.Count.
// Условие nextStrs.Length != pair.Value.Count выполняется если
// на этом уровне есть строки являющиеся полной подстрокой для днугих
// строк. Например, "test" является полной подстрокой для "test1".
str.AppendFormat(
@" return ++start < text.Length && text[start] == '{0}' ? {1} : {2};
", ident[0], level, nextStrs.Length != pair.Value.Count ? level - 1 : -1);
}
else
{
// подстрока одна, но символов в ней много...
// используем для проверки функцию string.Compare().
str.AppendFormat(
@" return string.Compare(text, start + 1, ""{0}"", 0, {1}) == 0
? {2} : -1;
", ident, ident.Length, level + ident.Length - 1);
}
}
else if (nextStrs.Length > 0)
{
// Если есть алтернативы, то генерируем вложеный switch.
// Для этого вызваем эту же функцию рекурсивно.
str.Append(@" start++;
");
str.Append(MakeLevel(nextStrs, level + 1));
str.Append(" break;");
}
else // Мы распознали строку. При этом ее длинна равна level - 1.
str.AppendFormat(" return {0};", level - 1);
// Закрываем блок case-а.
str.Append(
@"
}
");
}
// Закрываем блок switch-а.
str.Append(@"}");
// Добавляем отступы.
str.Replace("\r\n", "\r\n" + new string('\t', level));
return str.ToString();
}
/// <summary>
/// Удаляет первые символы строк и копирует непустые строки в новый массив.
/// </summary>
/// <param name="strs">Исходная коллекция строк.</param>
static string[] RemoveFirstChars(IList<string> strs)
{
List<string> list = new List<string>(strs.Count);
foreach (string str in strs)
if (str.Length > 1)
list.Add(str.Substring(1));
return list.ToArray();
}
/// <summary>
/// Создает словарь ключем которого является первые символы строк, а
/// значением списки строк начинающихся на этот символ.
/// </summary>
/// <param name="strs"></param>
/// <returns></returns>
private static CharMap MakeDic(string[] strs)
{
CharMap map = new CharMap();
foreach (string str in strs)
{
List<string> list;
if (!map.TryGetValue(str[0], out list))
map.Add(str[0], list = new List<string>());
list.Add(str);
}
return map;
}
}
А вот тест для этого дела:
using System;
class Program
{
static void Check(string text, int start)
{
int ret = Dfa.CheckStr(text, start);
if (ret >= 0)
Console.WriteLine("В строке '{0}' распознано ключевое слово '{1}'",
text, text.Substring(start, ret));
else
{
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("В строке '{0}' нераспознано ключевых слово", text);
Console.ResetColor();
}
}
static void Main(string[] args)
{
Check(" test", 1);
Check(" test1", 1);
Check(" case", 1);
Check(" az", 1);
Check(" as", 1);
Check(" absract", 1);
Check(" abstract", 1);
Check(" abstrac", 1);
Console.ReadLine();
}
}
Этот тест генерирует ДКА для ключевых слов C# 2.0. Размер генерируемого файла 21.66 килобайт (1053 строк). В принципе довольно много, но не так чтобы смертельно много. Хорошо бы сделать тест и сравнить скорость этого дела с распознованием через хэш-таблицу (как обычную, так и специализированную). Для сравнения сканер генерируемый Кокой для полного лексера C# (Scanner.cs) имеет размер 107 кил (около 6000 строк). Но он использует хэш-таблицу для выделения ключевых слов. В общем-то если он разжиреет еще на 22К, то это мало кто заметит. Но есть языки где количество ключевых слов намного больше. Например, ассемблер. Его подстветка на рсдн, кстати, сильно тормозит.
Короче, тут нужны эксперементы. Но твоя идея явно не лучшая.
В общем, нужно или использовать генерируемый ДКА, или пользоваться идеей хэширования. Но это я говорил с самого начала.
ЗЫ
Если выбрать генерацию автомата, то наверно лучше хакать Коку. Кстати, саму генерацию лучше перевести на StringTemplates (классная библиотека используемая в ANTLR). Она сделает код значительно чище и упростит его модификацию.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Здравствуйте, VladD2, Вы писали:
VD>@"
VD>if (start > text.Length)
VD> return -1;
VD>switch(text[start])
VD>{
VD>");
Тут у тебя ошибка. Надо: start >= text.Length
VD>Этот тест генерирует ДКА для ключевых слов C# 2.0. Размер генерируемого файла 21.66 килобайт (1053 строк). В принципе довольно много, но не так чтобы смертельно много. Хорошо бы сделать тест и сравнить скорость этого дела с распознованием через хэш-таблицу (как обычную, так и специализированную). Для сравнения сканер генерируемый Кокой для полного лексера C# (Scanner.cs) имеет размер 107 кил (около 6000 строк).
Обычная хэш-таблица в 2.5-3 раза быстрее
Свой вариант тоже померил (в оптимизированной версии без энумераторов и пр.). На коротких идентификаторах раза в 2 быстрее хэш-таблицы, на длинных типа "interface" почти в два раза медленее.
Кстати, я не очень понял как поможет этот Dfa при по-символьном разборе текста. Он же хочет, чтобы ему строку передавали.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, Воронков Василий, Вы писали:
VD>>@"
VD>>if (start > text.Length)
VD>> return -1;
VD>>switch(text[start])
VD>>{
VD>>");
ВВ>Тут у тебя ошибка. Надо: start >= text.Length
С чего бы это ошибкой стало? Если стартовый символ равен или больше длинны строки, то мы уже за ее пределами. Стало быть строка не распознана.
VD>>Этот тест генерирует ДКА для ключевых слов C# 2.0. Размер генерируемого файла 21.66 килобайт (1053 строк). В принципе довольно много, но не так чтобы смертельно много. Хорошо бы сделать тест и сравнить скорость этого дела с распознованием через хэш-таблицу (как обычную, так и специализированную). Для сравнения сканер генерируемый Кокой для полного лексера C# (Scanner.cs) имеет размер 107 кил (около 6000 строк).
ВВ>Обычная хэш-таблица в 2.5-3 раза быстрее
Это на каком объеме и на каких строках? Можно поглядеть тест?
ВВ>Свой вариант тоже померил (в оптимизированной версии без энумераторов и пр.). На коротких идентификаторах раза в 2 быстрее хэш-таблицы, на длинных типа "interface" почти в два раза медленее.
Темболее хорошо бы поглядеть на тесты.
ВВ>Кстати, я не очень понял как поможет этот Dfa при по-символьном разборе текста. Он же хочет, чтобы ему строку передавали.
ДКА просто сканирует строку символ за символом. Если мы попадаем в току где символ распознан, то можем остановиться вернув состояние и информацию о том, что мы распознали.
Алгоритмически по фигу как получается следующий символ. text[++start] можно заменить на любой вариант функции возвращающей следующий символ.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Здравствуйте, VladD2, Вы писали:
VD>>>@"
VD>>>if (start > text.Length)
VD>>> return -1;
VD>>>switch(text[start])
VD>>>{
VD>>>");
ВВ>>Тут у тебя ошибка. Надо: start >= text.Length
VD>С чего бы это ошибкой стало? Если стартовый символ равен или больше длинны строки, то мы уже за ее пределами. Стало быть строка не распознана.
Да, что-то торможу.
Это же мой код с ">". Конечно ошибка.
... << RSDN@Home 1.2.0 alpha rev. 631>>
