Завершение SQL. Часть 1: Трудности с парсингом или сказки о полировке ANTLR

Я работаю в компании, которая занимается разработкой взаимодействия IDE для баз данных более пяти лет. Перед тем, как начать писать эту статью, я понятия не имел, сколько фантастических сказок меня ждет впереди. Таким образом, сделав из нее 30 страниц, я решил тематически сгруппировать сказки и разделить статью на несколько частей.

Введение

По мере публикации частей я буду добавлять соответствующие ссылки:

• Часть 1. Дополнение SQL. Часть 1. Трудности парсинга. Рассказы о полировке ANTLR.
• Часть 2. Оптимизация обработки строк и открытия файлов.
• Часть 3. Жизнь расширений Visual Studio. Взаимодействие ввода-вывода. Нетрадиционное использование SQL.
• Часть 4. Использование исключений, влияние данных на процесс разработки. Использование ML.NET.

За время моей работы произошло много интересного. Мы обнаружили несколько ошибок в .NET, оптимизировали работу некоторых функций; оптимизированы функции, некоторые из них в несколько раз, а некоторые - совсем чуть-чуть. Что-то получилось отлично с первой попытки, а что-то провалилось даже после нескольких выстрелов. Моя команда разрабатывает и поддерживает языковые функции IDE, и автозаполнение кода является основным из них. Поэтому так названа серия статей. Каждый из них расскажет несколько историй, некоторые об успехе, некоторые о неудачах.

Эта часть посвящена проблемам синтаксического анализа SQL, борьбе с ними и ошибкам, которые возникали на протяжении всего процесса.

Несколько слов о себе

Я поступил на эту работу младшим специалистом практически без опыта. Как и другие, я был очарован игровой индустрией, и это была главная причина, по которой я начал писать код. Я участвовал в разработке нескольких игр, и некоторые из них были успешно выпущены. Есть еще десяток игр, разработанных или заброшенных на разных стадиях готовности.

Кроме того, я завершил несколько внештатных проектов, прежде чем получить эту работу. Самым большим из них было приложение для социальных сетей, представляющее собой футбольный портал с турнирными таблицами, данными игроков и уведомлениями о голах / счетах через SMS. Это было сделано более 10 лет назад, и тогда не так много людей использовали смартфоны, а те, кто им пользовался, либо не имели Интернета, либо использовали ужасный EDGE, который едва мог открывать сайты с текстовой версией. Так что идея показалась мне крутой.

Так уж получилось, что мне всегда нравилось создавать разные инструменты для себя и разработчиков, и иногда это было довольно близко к тому, что мне приходилось делать на работе. Например, когда я изучал Win32API, одним из моих проектов была программа для выделения кода XML в Rich Edit Control. Также была возможность сохранить выделенный текст в BMP, HTML или ранее великолепный BB-код для форумов.

Еще один проект, близкий к моей работе, - это анализ кода для С / С ++, который построил его диаграмму действий. Эта диаграмма действий строго соответствовала требованиям одного профессора, была сделана неуклюже, без знания синтаксического анализа, и работала только за счет моей крутой личности. Несколько лет спустя я натолкнулся на эту программу во время чистки своего ПК и решил сохранить ее и выложить на GitHub ради ностальгии.

Эти эксперименты плюс фриланс дали мне некоторый опыт и возможность устроиться на работу. Через некоторое время, после пары десятков болезненных отзывов, я получил некоторый выигрыш, и я начал приносить прибыль компании. Оглядываясь назад, забавно осознавать, что благодаря этим совпадениям я начал заниматься тем, к чему всегда стремился.

Трудности

Этот блок предназначен для того, чтобы дать некоторый контекст того, что мы делаем.

Настольная разработка

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

Еще одна проблема заключалась в невозможности объяснить сложность проекта коллегам-разработчикам, когда они пили пиво. Когда вы работаете с приложениями, которые работают по совершенно другим принципам, становится еще труднее.

Разбор SQL и диалектов

Еще до этой работы я писал небольшие парсеры для разных языков. Я также провел несколько курсов .NET и предложил своим студентам написать свой простой парсер JSON в качестве дополнительного задания при обсуждении строк. Но SQL и его переменные не похожи на XML или JSON, понятные как синтаксическим анализаторам, так и людям. Более того, синтаксис SQL более сложен, чем его аналог на C / C ++ с его бесчисленным множеством функций, накопленных за время его существования.

SQL имеет другую структуру с попыткой выглядеть как естественный язык, и я должен сказать, что эта попытка весьма успешна. В зависимости от диалекта в языке есть несколько тысяч ключевых слов. Чтобы отличить одно утверждение от другого, вам часто нужно искать впереди одно или два слова (токена). Такой подход называется «упреждающий».

Существует классификация парсеров в зависимости от того, как далеко они могут заглядывать вперед: LA (1), LA (2) или LA (*), что означает, что парсер может смотреть настолько далеко вперед, насколько это необходимо, чтобы определить правильную вилку. Иногда окончание необязательного предложения совпадает с началом другого необязательного предложения, и в таких ситуациях выполнение синтаксического анализа становится намного сложнее. T-SQL также не упрощает задачу: точка с запятой не нужна. Кроме того, некоторые операторы SQL могут иметь, но не обязательно, окончания, которые могут конфликтовать с началом предыдущих операторов.

Ты все еще мне не веришь? Есть способ описания формальных языков с помощью грамматики. Грамматика - это код, написанный на определенном языке, который описывает другой язык. Вы можете сгенерировать парсер из грамматики с помощью того или иного инструмента. Самыми известными инструментами и языками, описывающими грамматику, являются YACC и ANTLR. Парсеры, генерируемые YACC, используются в движках MySQL, MariaDB и PostgreSQL. Мы могли бы попробовать взять их прямо из исходного кода и разработать завершение кода и другие функции на основе анализа SQL с использованием этих парсеров. Кроме того, этот продукт будет получать бесплатные обновления для разработки, а анализатор будет вести себя так же, как движок исходного кода.

Так почему мы все еще используем ANTLR? Он твердо поддерживает C # /. NET, имеет приличный инструментарий, его синтаксис намного проще читать и писать. Синтаксис ANTLR стал настолько удобным, что Microsoft теперь использует его в своей официальной документации по C #.

Но давайте вернемся к сложности SQL по сравнению с другими языками, когда дело доходит до синтаксического анализа. Для этого я хотел бы сравнить размеры грамматики общедоступных языков. В dbForge мы используем наши части грамматики: они более полные, чем другие, но, к сожалению, перегружены вставками кода C # для поддержки различных функций (см. Подробности в параграфе Синтаксический анализ без деревьев раздела Ошибки).

Размеры грамматики для разных языков следующие:
JS - 475 строк парсера + 273 лексера = 748 строк
Java - 615 строк парсера + 211 лексеры = 826 строк
C # - 1159 строк парсера + 433 лексера = 1592 строки
С ++ - 1933 строки

MySQL - 2515 строк парсера + 1189 лексеров = 3704 строки
T-SQL - 4035 строк парсера + 896 лексеров = 4931 строка
PL SQL - 6719 строк парсера + 2366 Лексеры = 9085 строк

В конце некоторых лексеров представлены списки символов Юникода, доступных на языке. Эти списки бесполезны для оценки сложности языка. Таким образом, количество строк, которые я брал, всегда заканчивалось перед этими списками.

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

Это не все. Нам нужно больше, чем просто разобрать несколько файлов SQL. Поскольку мы разрабатываем IDE, мы должны иметь дело с неполными или недопустимыми скриптами. Даже если вы пишете свои сценарии без ошибок, есть вероятность, что вы напишете их бессвязно. Так что сценарий вряд ли останется актуальным на протяжении всего процесса разработки. Сначала я пишу SELECT FROM и просматриваю список доступных таблиц; после того, как я выберу один и перемещаю каретку в положение ВЫБРАТЬ, нажимаю ПРОБЕЛ и жду список столбцов из этой самой таблицы. Это простой пример, но он показывает, что синтаксический анализатор, обеспечивающий завершение кода в среде IDE, не может упасть из-за исключения после обнаружения недопустимого сценария.

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

Предикатные войны

Во время синтаксического анализа кода иногда следующее слово не говорит вам, какую из двух альтернатив выбрать. Часто бывает достаточно просто взглянуть на определенное количество слов впереди, и вы можете выбрать конкретную альтернативу. Механизм, который устраняет этот тип неточностей, в ANTLR «упреждающий». В этом случае метод синтаксического анализатора представляет собой вставленную цепочку «if’s», и каждый из них смотрит на шаг вперед. Ниже приведен пример грамматики, которая порождает неопределенность такого рода:

rule1:
  'a' rule2 | rule3
;

rule2:
  'b' 'c' 'd'
;

rule3:
  'b' 'c' 'e'
;

В середине правила 1, когда токен «а» уже передан, синтаксический анализатор просматривает два шага вперед, чтобы выбрать правило, которому следует следовать. Эта проверка будет выполнена еще раз, но эту грамматику можно переписать, чтобы исключить этот «прогноз». Обратной стороной является то, что такая оптимизация наносит вред структуре, а прирост производительности невелик.

Есть более сложные способы решить эту неопределенность. Например, механизм предиката синтаксиса (SynPred) в ANTLR3. Это помогает, когда необязательное окончание предложения пересекает начало следующего необязательного предложения. В терминах ANTLR3 предикат - это сгенерированный метод, который выполняет ввод виртуального текста в соответствии с одной из альтернатив, и в случае успеха он возвращает значение «истина», и такое завершение предиката называется успешным. Когда это виртуальная запись, она называется записью в режиме «возврата». Если предикат сработал успешно, происходит настоящая запись. Проблема возникает только тогда, когда предикат начинается внутри другого предиката, так что одно расстояние может быть пересечено сотни или тысячи раз.

Давайте рассмотрим упрощенный пример. Есть три точки неопределенности: (A, B, C).

1. Парсер вводит A, запоминает его позицию в тексте, запускает виртуальную запись уровня 1.
2. Парсер входит в B, запоминает его позицию в тексте, запускает виртуальную запись уровня 2.
3. Парсер входит в C, запоминает его позицию в тексте, запускает виртуальную запись уровня 3.
4. Синтаксический анализатор завершает виртуальную запись уровня 3, возвращается на уровень 2 и снова передает C.
5. Синтаксический анализатор завершает виртуальную запись уровня 2, возвращается на уровень 1 и снова передает B и C.
6. Синтаксический анализатор успешно завершает виртуальную запись, возвращает и выполняет реальную запись через A, B и C.

В результате все проверки в пределах C будут выполнены 4 раза, в пределах B - 3 раза, в пределах A - 2 раза. Но что, если подходящая альтернатива находится во втором или третьем списке? Затем произойдет сбой на одном из этапов предиката, его положение в тексте откатится, и начнется выполнение другого предиката.

Анализируя причины зависания приложения, мы часто сталкивались с тем, что SynPred выполнялся несколько тысяч раз. SynPreds особенно проблематичны в рекурсивных правилах, и, к сожалению, SQL рекурсивен по своей природе: возможность использовать подзапросы почти везде имеет свою цену. Однако иногда можно манипулировать правилом, чтобы избавиться от предиката, используя различные уловки и уловки.

SynPred снижает производительность. В какой-то момент их количество было поставлено под жесткий контроль, но проблема в том, что когда вы пишете грамматический код, SynPred может показаться вам неочевидным. Более того, изменение одного правила может привести к появлению SynPred в другом правиле, что делает контроль над ними практически невозможным. Мы создали простой инструмент «регулярное выражение» для управления количеством предикатов, выполняемых специальной задачей MSBuild. Если количество предикатов не совпадает с числом, указанным в файле, задача сразу же завершает сборку и предупреждает об ошибке. Увидев ошибку, разработчик должен был несколько раз переписать код правила, пытаясь удалить избыточные предикаты (возможно, с помощью других разработчиков). Если предиката нельзя избежать, разработчик добавляет его в специальный файл, что привлекает дополнительное внимание к обзору.

В редких случаях мы даже писали наши предикаты на C #, чтобы избежать тех, которые генерируются ANTLR. К счастью, этот метод тоже существует.

Крутые решения

Грамматическое наследование

Как только будут объявлены какие-либо изменения в поддерживаемых нами СУБД, мы начнем процесс реализации поддержки изменений в наших инструментах. Поддержка конструкций грамматического синтаксиса всегда является отправной точкой. Мы создаем специальную грамматику для каждого диалекта SQL, которая допускает повторение кода, но, в конце концов, это проще, чем пытаться найти то, что у них общего. Всего пару лет назад MySQL и MariaDB были очень похожи, и писать отдельные части грамматики не имело смысла. Вот почему мы поддержали те немногие конструкции, которые присутствовали в MariaDB, но отсутствовали MySQL в грамматике MySQL. У этого подхода был один недостаток для пользователей MySQL: мы могли предлагать недопустимые конструкции. Но в последние годы MySQL и MariaDB стали все больше и больше различаться с точки зрения синтаксиса и других функций, поэтому поддержка двух разных языков в рамках одной грамматики стала неактуальной.

Решением могло бы стать полное копирование грамматики и ее будущая поддержка. И после долгого обсуждения мы решили попробовать смелое решение. Я был счастлив, что мы не решили пойти на копирование - все мое существо было против этого. Поэтому мы решили написать наш собственный препроцессор грамматики ANTLR, который выполняет наследование грамматики. Совсем недавно мне на глаза попалась грамматика ANTLR3 в официальном репозитории ANTLR4. Думаю, вам нужно прочитать это предложение несколько раз, чтобы понять всю глубину этого безумия.

Также стало очевидно, что мы хотели бы иметь механизм полиморфизма. Т.е. нам нужна была возможность не только переопределить правило в потомке, но и вызвать основное. Мы также хотели бы контролировать позицию при вызове базового правила: это начало, середина или конец. Поэтому мы решили, что все правила можно переопределить и ничего больше указывать не нужно. Чтобы переопределить правило, достаточно указать правило с тем же именем в грамматике потомка. Как только это будет сделано, правило из родительской грамматики будет доступно под другим именем.

«Инструменты - несомненный плюс, когда мы сравниваем ANTLR с другими инструментами распознавания языков, Visual Studio и ANTLRWorks. И вы не хотите потерять это преимущество при реализации наследования. Итак, как нам указать базовую грамматику? Мы могли бы сделать какое-то соглашение о правилах, но это довольно неочевидно. Другой вариант - указать дополнительную информацию в отдельном файле, но даже сейчас мне противно даже думать об этом. Решение заключалось в указании базовой грамматики в унаследованной грамматике в формате комментариев ANTLR. Для инструментов ANTLR это просто комментарий, но мы можем извлечь из него всю необходимую информацию.

Когда требования установлены и выполнены, пора их выполнять. Мы написали задачу MsBuild, которая была встроена во всю систему сборки в качестве действия перед сборкой. Задача заключалась в том, чтобы выполнить работу препроцессора для грамматики ANTLR, генерируя результирующую грамматику из его базовых и унаследованных одноранговых узлов. Полученная грамматика была обработана самим ANTLR.

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

Механизм работы препроцессора не занимал много времени, но с добавлением генерации синтаксического анализатора потребовалось дополнительно 10–20 секунд на пересборку проекта. И в какой-то момент нам это надоело, и мы задумались над его оптимизацией. Было решено ввести в файл парсера CS хеш-сумму всех грамматик, от которых он зависит (в виде комментария). Прежде чем что-либо предпринять, препроцессор сравнил эти хэши с хешами файлов, находящихся на диске; и парсер считался действительным, если эти хэши совпадали друг с другом.

На начальном этапе разработки нам пришлось столкнуться с множеством неверных парсеров и грамматик, построенных на устаревших версиях препроцессора. В результате заголовок комментария получил хеш-сумму сборки с ее препроцессором.

Если вы нашли эту заметку полезной, продолжайте читать в блоге - https://codingsight.com/completing-sql-part-1-the-difficulty-with-parsing-or-tales-of-polishing-antlr/

Спасибо и следите за обновлениями!