UProLa

Неокріпші думки

Функціональне програмування на C#

leave a comment »

Задача

Є граматичне правило “preprocessing-op-or-punc”. Потрібно скласти регулярний вираз, котрий зможе розпізнавати дане правило.

Рішення 1 – рішення в лоб

Читаємо документацію до регулярних виразів у мові C#. Читаємо про групування. Після цього складаємо план регекспу – як він повинен теоретично виглядати. Після цього скурпульозно переписуємо граматичне правило з сайту у нотації регекспів.

Проблеми рішення 1
Після того, як регексп написаний, його виправлення (у разі наявності помилки) може зайняти не менше половини часу його написання. Тому перед початком роботи варто потренуватись на простіших виразах, щоб зрозуміти що регексп план правила складений правильно. Також може бути допущена помилка при передруці.

Рішення 2 – недо-метапрограмування

Передруковуємо примітивні елементи вказаного граматичного правила у список рядків. Надалі по певному алгоритму перетворюємо отриманий список рядків у регулярний вираз. У разі виявлення помилки при генерації регекспу, варто буде змінити тільки логічну структуру алгоритму, щоб правильний регексп потім з’явився сам.

Проблеми рішення 2
Потрібно окрім основого завдання додатково написати алгоритм генерації регекспу. Це може зайняти час співрозмірний чи навіть довший за рутинне перше рішення. Відлагодження/налаштування алгоритму теоретично може займати не менший час, ніж ручне коригування регулярного виразу.

Рішення 3 – (рефлектине) метапрограмування з спрямуванням на юзабіліті

Дане рішення є розширенням варіанту №2. Спосіб написання регекспу складається з наступних етапів:
– програміст копіює з браузеру рядок з примітивними елементами
– програміст запускає попередньо написаний алгоритм, який зчитує вміст буферу обміну і парсить отриманий рядок в список
– алгоритм генерує код на обраній мові, який при компіляції/виконанні буде представляти собою даний список
– алгоритм генерує код з варіанту 2 зі вказаним згенерованим кодом списку (як варіант, алгоритм змінює себе, додаючи у власний код часу компіляції згенерований список і встановлення певного семафору про вдалість виконання операції та працювання при наступному запуску по рішенню 2)

Проблеми рішення 3
Може зайняти тривалий час. Відлагодження рішення може бути складним. Можна забути, навіщо потрібен даний регексп.

Про те я не про це

Я зробив 2 варіант на C# і як це не дивно, використав невластивий для себе функціональний стиль:

const string regexChars = @"[](){}*.?$+'`&,\^<>:!=|#-";

List<string> preprocessing_op_or_punc = new List<string>();
preprocessing_op_or_punc.AddRange(new[] { 
    "{", "}", "[", "]", "(", ")", "#", "##", "<:", ":>", "<%", "%>", "%:", "%:%:", 
    ";", ":", "...", "new", "delete", "?", "::", ".", ".*", "+", "-", "*", "/", "%", 
    "^", "|", "_", "!", "=", "<", ">", "+=", "-=", "*=", "/*", "%=", "^=", "&=", 
    "|=", "<<", ">>", "<<=", ">>=", "==", "!=", "<=", ">=", "&&", "||", "++", "--",
    ",", "->*", "->", "and", "and_eq", "bitand", "bitor", "compl", "not", "not_eq",
    "or", "or_eq", "xor", "xor_eq",
});

Func<string, string> regexEscape = (x) => x.Aggregate<char, string>("", (s, ch) => s + (regexChars.Contains(ch) ? @"\" + ch : "" + ch));
var r_preprocessing_op_or_punc = new Regex("^(?:[{0}]|(?:{1}))$".format(preprocessing_op_or_punc.FindAll(x => x.Length == 1).Select(x => regexEscape(x)).Aggregate((x, y) => x + y),
preprocessing_op_or_punc.FindAll(x => x.Length > 1).Select(x => @"(?:{0})".format(regexEscape(x))).Aggregate((x, y) => "{0}|{1}".format(x, y))), RegexOptions.Compiled | RegexOptions.IgnorePatternWhitespace);

Або у більш читабельному вигляді

Func<string, string> regexEscape = x => 
    x.Aggregate<char, string>("", (s, ch) => 
                                    s + (
                                    regexChars.Contains(ch) 
                                        ? @"\" + ch 
                                        : "" + ch
                                        )
                             );
var r_preprocessing_op_or_punc = new Regex("^(?:[{0}]|(?:{1}))$".format(
    preprocessing_op_or_punc
        .FindAll(x => x.Length == 1)
        .Select(x => regexEscape(x))
        .Aggregate((x, y) => x + y),
    preprocessing_op_or_punc
        .FindAll(x => x.Length > 1)
        .Select(x => @"(?:{0})".format(regexEscape(x)))
        .Aggregate((x, y) => "{0}|{1}".format(x, y)))
    , RegexOptions.Compiled | RegexOptions.IgnorePatternWhitespace);

Хотілось би зробити кілька зауважень по коду, особливо для тих, хто не знайомий з синтаксисом C#.

  • У першому рядку стоїть собачко перед рядком. Таким чином у C# відміняється екранування символів в рядках.
  • При об’явленні списку використано “узагальнення” – аналог шаблонів С++. Власне список в C# дуже схожий на vector у С++. Чому “узагальнення” а не шаблони? Тому що правила створення і використання дещо відрізняються. Так, в узагальненнях в якості параметру узагальнення можна використовувати тільки типи, а С++ шаблони дозволяють використовувати і значення.
  • Список List<string> містить метод AddRange, котрий приймає аргументом об’єкт типу IEnumerable. Власне ЦЕ йому і передається за рахунок використання конретно заданого списку, тип елементів якого визначається автоматично компілятором. За рахунок цього і дозволено досить швидко, в один рядок, додавати кокретні елементи до списку. Порівняй з Пітонівським preprocessing_op_or_punc += [“element1”, “element2”].
  • Наступна команда – лямбда функція. Як видно з опису, лямбда функція є об’єктом типу Func, узагальнений запис якого означає, що функція приймає на вхід рядок і повертає також рядок.
  • Функція Aggregate() знайома Lisp користувачам під назвою (reduce ..). Фактично, вона виконує анонімну лямбда функцію, що приймає на вхід рядок і символ і повертає рядок, тобто агрегує символи певним способом у рядок. Функція Aggregate() входить до розширення мови під назвою LINQ – Language INtegrated Query і об’явлена за допомогою технології Extension Methods.
  • Використання конструкції ternary-if вважаю непотрібним коментувати. Єдине, поясню що робить функція. Вона екранує всі символи вхідного рядка, котрі мають певні призначення у синтаксисі регулярних виразів і видає екранований рядок на вихід.
  • Наступна конструкція створює об’єкт регекспа по заданому паттерну, ігноруючи прогалики у паттерні. Останній параметр виявися лишнім, оскільки генерований паттерн не містить лишніх прогаликів, та то таке. Цікавим тут є використання методу format(). Він не належить до стандартних методів класу string, він написаний мною. Такий механізм (прив’язування до готових класів користувацьких методів) називається методами розширення.
  • Окремо про форматування рядків. Синтаксис простий – string.Format(“blabla {0} blablabla {1} blablaba”, param1, param2). Тобто, {0} замінюється на перший параметр, {1} на другий і так далі. У варіанті запису через метод розширення такий синтаксис точно відповідає синтаксису форматування в Пітон 3х
  • Подальші функції перекладаються на українську як: для кожного елементу списку preprocessing_op_or_punc, котрий має довжину 1, виконати екранування і потім зліпити їх всі докупи в один рядок, а для решти елементів виконати те саме, тільки окрім екранування перетворити кожен елемент у групу і зліпити їх усі через вертикальну палочку. Власне, про це і був весь пост.

Хотів би додати, що С# досить далеко відійшов від С++, незважаючи на подібність синтаксису. Можливості мови (використовуючи .NET фреймворк) справді великі (окремою цікавою темою є атрибути, рефлексія, CodeDom, dynamic типи) і досить зручні. Одним словом, Я♡C#.

Written by danbst

Лютий 5, 2011 at 23:45

Оприлюднено в Програмування

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: