![Синтаксический анализ MQL средствами MQL](https://c.mql5.com/i/articles/overlay.png)
Синтаксический анализ MQL средствами MQL
Введение
Суть программирования заключается в формализации и автоматизации неких процессов с помощью языков общего или специального назначения. Торговая платформа MetaTrader позволяет применять программирование для решения самых разных задач трейдера, благодаря встроенному языку MQL. И обычно процесс программирования строится на анализе и обработке прикладных данных по правилам, изложенным в исходных кодах. Однако иногда возникает необходимость проводить анализ и обработку самих исходных кодов. Вот несколько примеров.
Одна из наиболее понятных и востребованных задач — контекстно-смысловой поиск по базе исходных кодов. Разумеется, в исходном коде можно искать строки как в обычном тексте, но при этом теряется семантика искомого. А ведь в случае исходных кодов желательно различать специфику применения подстроки в каждом конкретном случае. Если программист хочет найти, где используется конкретная переменная, например, "notification", то простой поиск по её названию может выдать много лишнего, если строка встречается в других значениях — как имя метода, литерал или в комментариях.
Более сложной и востребованной, как правило, на крупных проектах, является задача по выявлению структуры кода, зависимостей, иерархии классов. Она тесно связана с мета-программированием, которое позволяет проводить рефакторинг кода (улучшение) и кодогенерацию. Напомним, что редактор MetaEditor предоставляет некоторые возможности кодогенерации, в частности, создание исходных кодов экспертов с помощью Мастера или формирование заголовочного файла по исходному коду. Однако потенциальные возможности данной технологии гораздо шире.
Анализ структуры кода позволяет вычислять различные метрики его качества, статистику, а также находить типичные источники runtime-ошибок, которые не может выявить компилятор. На самом деле компилятор, конечно, сам является первым инструментом анализа исходного кода, и выдает много типов предупреждений, однако проверка на все потенциальные ошибки в него, как правило, не встраивается — это слишком объемная задача, и потому её поручают отдельным программам.
Кроме того, синтаксический анализ исходных кодов используется для стилизации (форматирования) и обфускации (запутывания).
Для промышленных языков программирования доступно много инструментов, реализующих упомянутые задачи. В случае MQL выбор ограничен. Анализ MQL можно попытаться организовать доступными средствами путем настройки, приравнивающей MQL к C++. Это довольно просто работает в случае одних инструментов, таких как Doxygen, но требует более глубокой адаптации для более мощных средств вроде lint-а, поскольку MQL — все же не C++.
Также следует отметить, что в данной статье речь пойдет только о статическом анализе кода, в то время как существуют и динамические анализаторы, позволяющие в виртуальном окружении "на ходу" отслеживать ошибки работы с памятью, блокировки потоков, правильность значений переменных и многое другое.
Для статического анализа исходного кода можно использовать различные подходы. В случае простых задач, например, для поиска входных переменных MQL-программы, достаточно воспользоваться библиотекой регулярных выражений. В более общем виде анализ должен строиться на базе парсера, учитывающего грамматику MQL. В данной статье мы рассмотрим именно этот подход и попробуем применить его на практике.
Иными словами, мы напишем на MQL парсер MQL и получим мета-данные об исходных кодах. Это не только позволит решать вышеперечисленные задачи, но и откроет в перспективе другие фантастические возможности. Так, имея полностью корректный парсер, мы могли бы сделать на его основе интерпретатор MQL или автоматически конвертировать MQL в другие трейдерские языки или наоборот (так называемый транспайлинг). Но я не случайно употребил слово "фантастические". Хоть все эти технологии уже широко используются в других областях, чтобы приблизиться к ним на платформе MetaTrader — необходимо сперва разобраться с основами.
Обзор технологии
Существует множество различных парсеров. Мы не будем здесь вдаваться в технические подробности — вводную информацию можно найти в Википедии, а для более углубленного изучения создано огромное количество ресурсов.
Отметим лишь, что парсер функционирует на основе так называемой грамматики, описывающей язык. Одна из наиболее распространенных форм описания грамматик — Бэкуса-Наура (BNF). Существует очень много модификаций BNF, мы не будем заострять внимание на тонкостях и рассмотрим лишь основные моменты.
В BNF все составные конструкции языка обозначаются так называемыми нетерминалами, а неделимые сущности — терминалами. Слово "терминал" здесь обозначает конечную точку в синтаксическом разборе текста — некий токен, содержащий фрагмент исходного кода "как есть" и интерпретируемый целиком. Это может быть, например, символ "запятая", скобка, или отдельное слово. Перечень терминалов (алфавит) мы определяем сами внутри грамматики. Из терминалов по некоторым правилам составляются все остальные части программы.
Например, в упрощенной BNF-нотации можно указать, что программа состоит из операторов, следующим образом:
program ::= operator more_operators
more_operators ::= program | {пусто}
Здесь говорится, что нетерминал program может состоять из одного или большего числа операторов, причем последующие операторы описаны с помощью рекурсивной ссылки на program. Символ '|' (без кавычек в BNF) означает логическое ИЛИ — выбор одного из вариантов. Для завершения рекурсии в приведенной записи используется специальный терминал {пусто}. Его можно представить, как пустую строку или возможность пропустить правило.
Символ operator также является нетерминалом и требует "раскрытия" через другие нетерминалы и терминалы, например, так:
operator ::= name '=' expression ';'
Эта запись определяет, что каждый оператор должен начинаться с имени переменной, далее идет знак '=', некое выражение, а завершается оператор символом ';'. Знаки '=' и ';' — это терминалы. Имя состоит из букв:
name ::= letter more_letters more_letters ::= name | {пусто} letter ::= [A-Z]
Здесь в качестве буквы допускается использовать любой символ от 'A' до 'Z' (их множество обозначено квадратными скобками).
Пусть выражение строится из операндов и арифметических действий (операций):
expression ::= operand more_operands more_operands ::= operation expression | {пусто}
В простейшем случае выражением является один единственный операнд, но их может быть и больше (more_operands), тогда они "пристыковываются" к нему через символ операции как подвыражение. Пусть операндами могут быть ссылки на переменные или числа, а операции — '+' или '-':
operand ::= name | number number ::= digit more_digits more_digits ::= number | {пусто} digit ::= [0-9] operation ::= '+' | '-'
Таким образом, мы описали грамматику простого языка, в котором можно проводить вычисления над числами и переменными, например:
A = 10; X = A - 5;
Когда мы начинаем разбирать текст, то фактически проверяем, какие правила срабатывают, а какие нет. Сработавшие правила рано или поздно должны произвести "продукцию" — обнаружить терминал, совпадающий с содержимым в текущей позиции в тексте, при этом курсор перемещается на следующую позицию. Этот процесс повторяется, пока весь текст не будет по фрагментам поставлен в соответствие с нетерминалами, формируя последовательность, разрешенную грамматикой.
В представленном выше примере парсер, имея на входе символ 'A', начнет просматривать правила в следующем порядке:
program operator name letter 'A'
и найдет первое соответствие. При этом курсор передвинется на следующий символ '='. Поскольку letter — это одна буква, парсер вернется в правило name. А поскольку имя name может состоять только из букв, то альтернатива more_letters не работает (выбирается равной {пусто}), и парсер возвращается в правило operator, где следующим после имени как раз идет терминал '='. Это будет второе соответствие. Далее, раскрывая правило expression, парсер найдет операнд — целое число 10 (как последовательность двух цифр), и наконец, точка с запятой завершит разбор первой строки. По её итогам мы фактически будем знать имя переменной, содержимое выражения, а именно то, что оно состоит из одного числа, и его значение. Вторая строка разбирается аналогично.
Важно отметить, что грамматику одного и того же языка можно записать разными способами, причем формально они будут соответствовать друг другу, но при буквальном следовании правилам в некоторых случаях могут возникать проблемы. Например, описание числа можно было бы представить так:
number ::= number digit | {пусто}
Эта форма записи называется левой рекурсией - нетерминал number стоит не только в левой, но и в правой части, определяющей правила его "продукции", причем он идет самым первым, левым, в строке (отсюда и название левая рекурсия). Это самая простая — явная левая рекурсия. Но она может быть и неявной, если нетерминал раскрывается через несколько промежуточных правил в строку, начинающуюся с него же.
Левая рекурсия часто встречается в формальных BNF-нотациях грамматик языков программирования, однако некоторые виды парсеров (в зависимости от реализации) могут зацикливаться на подобных правилах. Действительно, если рассматривать правило, как руководство к действию (алгоритм парсинга), то данная запись будет снова и снова рекурсивно входить в number, так и не считывая новые терминалы из входного потока, что, по идее, должно было бы происходить при раскрытии нетерминала digit.
Поскольку мы постараемся создать грамматику MQL не на пустом месте, а с использованием, по возможности, BNF-нотации грамматики C++, нужно будет обращать внимание на левые рекурсии и переписывать правила альтернативным способом. Вместе с тем, потребуется реализовать и средства защиты от зацикливания — как мы увидим далее, грамматики языков класса C++ или MQL настолько разветвленные, что вручную проверить их на корректность не представляется возможным.
Здесь уместно отметить, что написание парсеров — целая наука, и начинать осваивать данную область желательно постепенно, от простого к сложному. Самым простым является парсер нисходящего синтаксического анализа. Он рассматривает входной текст как целое, соответствующее стартовому нетерминалу грамматики. В примере выше это был нетерминал program. Следуя каждому подходящему правилу, парсер проверяет последовательность входных символов на соответствие терминалам и продвигается вдоль текста при обнаружении совпадений. Если в какой-то момент разбора парсер находит несоответствие, он откатывается назад к тем правилам, в которых была указана альтернатива, и таким образом проверяет все возможные варианты языковых конструкций. Этот алгоритм полностью повторяет действия, которые мы чисто умозрительно выполняли в примере выше.
Операция "отката" называется по-английски backtracking, и может отрицательно сказываться на быстродействии. Так, классический нисходящий парсер в худшем случае порождает при просмотре текста экспоненциально увеличивающееся количество вариантов. Для решения этой проблемы существуют разновидности, в частности, прогнозирующий парсер, не требующий "откатов". Время его работы — линейно.
Это, впрочем, возможно только для грамматик, для которых по заданному количеству следующих символов k можно однозначно выбрать правило "продукции". Такие более продвинутые парсеры опираются в своей работе на специальные таблицы переходов, предварительно рассчитываемые исходя из всех правил грамматики. К ним относятся, например, LL-парсеры и LR-парсеры (хотя ими список не ограничивается).
LL расшифровывается как Left-to-right, Leftmost derivation, то есть текст просматривается слева направо, и правила тоже просматриваются слева направо, что эквивалентно нисходящему выводу (от общего к частному), и в этом смысле LL — родственник нашего нисходящего парсера.
LR расшифровывается как Left-to-right, Rightmost derivation, то есть текст просматривается слева направо, как и прежде, а вот правила просматриваются справа налево, что эквивалентно восходящему построению конструкций языка — от одиночных символов — к всё более крупным нетерминалам. Между прочим, LR имеет меньше проблем с левой рекурсией.
В названии парсеров LL(k) и LR(k) обычно указывается количество символов k, на которое они просматривают текст вперед, и в большинстве случаев достаточно выбора k = 1. Но эта достаточность весьма условна. Дело в том, что многие современные языки программирования, включая C++ и MQL, не являются языками с контекстно-свободной грамматикой. Иными словами, одни и те же фрагменты текста могут интерпретироваться по-разному в зависимости от контекста. В таких случаях для принятия решения о смысле написанного бывает мало одного и даже произвольного количества символов, а требуется увязывать парсер с другими инструментами, например, препроцессором или таблицей имен (списком уже распознанных идентификаторов и их смысла).
Для языка C++ имеется хрестоматийный случай неоднозначности (он подходит также и для MQL). Что означает приведенное ниже выражение?
x * y;
Это может быть произведение переменных x и y, а может быть описание переменной y как указателя типа x. Пусть Вас не смущает, что результат умножения, если это умножение, никуда не сохраняется, потому что операция умножения может быть перегружена и иметь побочные эффекты.
Еще одной проблемой, которой страдало большинство компиляторов C++ в прошлом, была неоднозначность в интерпретации идущих подряд двух символов '>'. Дело в том, что после введение шаблонов, в исходных кодах стали появляться конструкции вида:
vector<pair<int,int>> v;
а последовательность '>>' — изначально определена как оператор сдвига. Некоторое время, пока в компиляторы не была введена более тонкая обработка таких специфических случаев, подобные выражения приходилось писать через пробел:
vector<pair<int,int> > v;
Мы в нашем парсере тоже должны будем обойти эту проблему.
В общем, даже по этому краткому введению наверняка становится понятно, что описание и реализация продвинутых парсеров потребовали бы больших усилий — и в плане объема изложения и времени на их освоение. В связи с этим, в данной статье мы ограничимся самым простым парсером — нисходящего рекурсивного спуска.Планирование
Итак, задача парсера прочитать поданный на вход текст, разбить его на поток неделимых фрагментов — токенов — и затем сопоставить их с разрешенными конструкциями языка, описанными с помощью грамматики MQL в BNF-нотации или близкой к ней.
Для начала нам потребуется класс, читающий файлы — назовем его FileReader. Поскольку проект MQL может состоять из нескольких файлов, подключаемых из основного через директиву #include, экземпляров FileReader может потребоваться много, и чтобы ими управлять заложим еще один класс FileReaderController.
Текст из обрабатываемых файлов, в общем-то, представляет собой обычную строку. Однако нам потребуется передавать её между разными классами, а MQL, к сожалению, не допускает указатели на строки (я помню про ссылки, то бишь references, но их нельзя использовать при объявлении членов класса, а единственная альтернатива — пробрасывать ссылку во все методы через входные параметры — неудобна). Поэтому мы создадим отдельный класс Source, представляющий собой обертку для строки. Он будет выполнять и еще одну важную функцию.
Дело в том, что в результате подключения include-ов (и как следствие, рекурсивного чтения заголовочных файлов из зависимостей) мы будем получать на выходе контроллера объединенный текст всех файлов. А для диагностики ошибок нам потребуется по смещению в объединенном исходном коде получить название и строку оригинального файла, откуда данный текст был взят. Эта "карта" размещения исходных кодов по файлам будет также поддерживаться и храниться классом Source.
Здесь уместен вопрос, нельзя ли было не объединять исходные коды, а вместо этого обрабатывать каждый файл по отдельности? Да, вероятно, так было бы даже правильнее, но тогда потребовалось бы на каждый файл создавать свой экземпляр парсера и затем неким образом сшивать синтаксические деревья, которые парсер генерирует на выходе. Поэтому я решил объединять исходные коды и подавать в единый парсер. Желающие могут поэкспериментировать с альтернативным подходом.
Для того, чтобы FileReaderController мог находить директивы #include, нужно не просто считывать текст из файлов, но и делать предварительный просмотр в поисках этих директив. Таким образом, необходим своего рода препроцессор. В MQL он выполняет и другие полезные дела, в частности, позволяет определять макросы и затем подменять их на актуальные выражения (причем, с учетом потенциальной рекурсии вызова макроса из макроса). Но в нашем первом проекте синтаксического анализа MQL лучше не браться за все задачи сразу. Поэтому макросы в нашем препроцессоре обрабатывать не будем — это потребовало бы не просто описать дополнительно грамматику макросов, но и интерпретировать их на лету, чтобы иметь корректные выражения для подстановки в исходный код. Помните, мы говорили про интерпретатор во введении? Так вот здесь он уже пригодился бы, и почему это важно, станет понятно далее. Это направление для самостоятельных экспериментов номер 2.
Препроцессор реализуем в классе Preprocessor. На его уровне происходит несколько противоречивый процесс. Во время чтения файлов и поиска в них директив #include анализ и продвижение в тексте выполняется на самом мелком уровне — посимвольно, однако препроцессор "прозрачно" пропускает через себя все, что не является директивой, и на выходе оперирует самыми крупными блоками — целиком файлами или фрагментами файлов между директивами. А вот далее анализ пойдет на некоем среднем уровне, для описания которого нам потребуется ввести пару терминов.
Прежде всего, это лексема — абстрактная минимальная единица лексического анализа, подстрока ненулевой длины. Вместе с ней в связке часто используют еще один термин — токен, который тоже является единицей анализа, но уже не абстрактной, а конкретной. И то, и другое — некий фрагмент текста (например, отдельный символ, слово или даже блок комментариев). Тонкое отличие между ними заключается в том, что на уровне токенов мы помечаем фрагменты смыслом. Например, если в тексте встречается слово "int", оно для MQL является лексемой, которую мы обозначим токеном INT - элементом в перечислении всех допустимых токенов языка MQL. Иными словами, набор лексем можно понимать как словарь строк, которые соответствуют типам токенов.
Один из плюсов токенов в том, что они позволяют поделить текст на более крупные фрагменты, чем символы. В результате, анализ текста производится в два прохода: сперва из потока букв формируются более высокоуровневые токены, а уже на их основе осуществляется разбор языковых конструкций. Это дает возможность существенно упростить грамматику языка и работу парсера.
Токены у нас будет выделять из текста специальный класс Scanner. Его можно рассматривать как низкоуровневый парсер с заранее предопределенной и жестко зашитой в него грамматикой, обрабатывающий текст по буквам. Какие именно типы токенов нам потребуются, рассмотрим ниже. Если кто-то возьмется за эксперимент номер 1 (с загрузкой каждого файла в выделенный парсер), то там как раз можно объединить препроцессор со сканером и при обнаружении токена "#include <что-то>" создавать новый FileReader, новый сканер, новый парсер и передавать им управление.
Токенами MQL будут все ключевые (зарезервированные) слова, а также символы пунктуации и операций. Полный перечень ключевых слов MQL приложен в файле reserved.txt и включен в исходный код сканера.
Также самостоятельными токенами будут идентификаторы, числа, строки, литералы и прочие константы (например, даты).
При разборе текста на токены все пробелы, переводы строк, табуляции подавляются (игнорируются). Единственное исключение в виде специальной обработки следует сделать для переводов строк, так как их подсчет позволит указывать строку с ошибкой, если она возникнет.
Таким образом, подав на вход сканера объединенный текст, мы получим на выходе список токенов. Именно этот список токенов и будет обрабатывать парсер, который реализуем в классе Parser.
Для интерпретации токенов по правилам языка MQL необходимо передать в парсер грамматику в BNF-нотации. Для описания грамматики попробуем в упрощенном виде повторить подход, который использует парсер boost::spirit. Суть состоит в том, чтобы описывать правила грамматики с помощью выражений языка MQL за счет перегрузки некоторых операторов.
Для этого введем иерархию классов Terminal, NonTerminal, и производных от них. Terminal будет базовым классом, который по умолчанию соответствует единичному токену. Как было сказано в теоретической части, терминал — это оконечный неделимый элемент разбора правил: если в текущей позиции текста находится символ, совпадающий с токеном терминала, значит символ соответствует грамматике, его можно прочитать, и двигаться дальше.
NonTerminal будем использовать для составных конструкций, в которых могут в разных сочетаниях использоваться терминалы и другие нетерминалы. Поясним на примере.
Предположим необходимо описать простую грамматику для вычисления выражений, в которых могут применяться только целые числа и операции плюс '+' и умножить '*'. Для простоты ограничимся случаем, когда операндов только два, например, 10+1 или 5*6.
Исходя из такой задачи, необходимо, прежде всего, определить терминал, соответствующий целому числу. Именно этот терминал будет сопоставлен с любым валидным операндом в выражении. Учитывая, что сканер производит для каждого случая, когда он повстречал в тексте целое число, соответствующий токен CONST_INTEGER, определим объект класса Terminal, ссылающийся на этот токен. В псевдокоде это будет:
Terminal value = CONST_INTEGER;
Эта запись означает, что мы создали объект value класса Terminal, который привязан к токену "целое число".
Символы операций — это тоже терминалы с соответствующими токенами PLUS и STAR, генерируемыми сканером для одиночных символов '+' и '*':
Terminal plus = PLUS; Terminal star = STAR;
Чтобы в выражении можно было использовать любой из них, введем нетерминал, объединяющий две операции по ИЛИ:
NonTerminal operation = plus | star;
Здесь как раз вступает в игру перегрузка операторов: в классе Terminal (и всех наследниках) operator| должен создавать ссылки из родительского объекта (в данном случае — operation) на дочерние (plus и star), и пометить тип операции над ними — логическое ИЛИ.
Когда парсер будет проверять нетерминал operation на соответствие тексту под курсором, он делегирует объекту operation дальнейшую проверку ("вглубь"), и тот вызовет в цикле проверку для дочерних элементов plus и star (до первого совпадения, так как это — ИЛИ). Поскольку они являются терминалами, то просто вернут парсеру свои токены и тот определит, совпадает ли символ в тексте с одной из операций.
Выражение может состоять из нескольких величин и операций между ними. Поэтому выражение — это тоже нетерминал — его нужно "раскрывать" через терминалы и нетерминалы.
NonTerminal expression = value + operation + value;
Здесь мы перегружаем operator+, который обозначает, что операнды должны следовать друг за другом в указанном порядке. Опять же, реализация функции подразумевает, что в родительском нетерминале expression должны сохраниться ссылки на дочерние объекты value, operation и еще один value, причем тип операции — логическое И. Действительно, в данном случае правило должно выполняться только в том случае, если все компоненты присутствуют.
Проверка парсером текста на соответствие правильному выражению вызовет сперва проверку в массиве ссылок expression, а затем в объектах value, operation (который рекурсивно обратится к plus и minus), и наконец снова к value. На любом этапе, если проверка опускается до уровня терминала, значение токена сравнивается с текущим символом в тексте, и если соответствие есть, то курсор продвигается на следующий токен, а если нет — значит, нужно поискать альтернативу. Например, в данном случае, если проверка на операцию plus будет неудачной, то проверка продолжится для star. Если все варианты исчерпаны, а соответствие так и не найдено, значит, правила грамматики нарушены.
Операторы '|' и '+' — это не все операторы, которые мы перегрузим в наших классах, но полностью опишем их в разделе реализации.
Декларация объектов класса Terminal и производных от него, содержащих ссылки на другие, все более и более мелкие сущности, формирует абстрактное синтаксическое дерево (AST) заданной грамматики. Абстрактным оно является потому, что в нем нет привязки к конкретным токенам из входного текста, т.е. по идее грамматика описывает бесконечное множество валидных строк, в нашем случае - кодов MQL.
Итак, мы в общих чертах рассмотрели основные классы проекта. Чтобы легче представить себе всю картину целиком, сведем их на UML-диаграмме классов.
UML-диаграмма классов синтаксического анализа MQL
Нерассмотренными остались некоторые классы, в частности, TreeNode. Его объекты будут использоваться парсером в процессе разбора входного текста, чтобы сохранять все найденные соответствия терминал=токен. В результате мы получим на выходе так называемое конкретное синтаксическое дерево (CST), в котором все токены тем или иным образом иерархически включены в терминалы и нетерминалы грамматики.
В принципе, создание дерева будет опциональным, поскольку оно для реальных исходных кодов может оказаться очень большим. Вместо получения результатов работы парсера в виде дерева предусмотрим интерфейс обратного вызова — Callback. Создав свой объект, реализующий данный интерфейс, мы передадим его парсеру и сможем получать уведомления о каждой выполненной "продукции" — сработавшем правиле грамматики. Таким образом, мы сможем анализировать синтаксис и семантику "на лету", не дожидаясь полного дерева.
Классы нетерминалов с приставкой Hidden будут использованы для автоматического неявного создания промежуточных групп объектов грамматики, чего мы коснемся подробнее в следующем разделе.
Реализация
Чтение файлов
Source
Класс Source является, в первую очередь, хранилищем строки с обрабатываемым текстом. Его основа выглядит так:
#define SOURCE_LENGTH 100000 class Source { private: string source; public: Source(const uint length = SOURCE_LENGTH) { StringInit(source, length); } Source *operator+=(const string &x) { source += x; return &this; } Source *operator+=(const ushort x) { source += ShortToString(x); return &this; } ushort operator[](uint i) const { return source[i]; } string get(uint start = 0, uint length = -1) const { return StringSubstr(source, start, length); } uint length() const { return StringLen(source); } };
Класс имеет переменную source для текста, а также перекрытые операторы для наиболее частых операций со строками. Пока "оставим за кадром" вторую роль данного класса, заключающуюся в поддержке списка файлов, из которых хранимая строка собирается. Имея такую "обертку" для входного текста, можно попробовать заполнить её из одного файла. За данную задачу отвечает класс FileReader.
FileReader
Прежде чем браться за программирование, нужно определить способ, как следует открывать и считывать файл. Поскольку мы обрабатываем текст, логично выбрать режим FILE_TXT. Это избавит нас от ручного контроля за символами перевода строк, которые кроме всего прочего могут по-разному кодироваться разными редакторами (обычно это пара символов CR LF, но в публично доступных исходных кодах MQL встречаются и альтернативные варианты — только CR или только LF). Напомним, что в текстовом режиме чтение файлов осуществляется построчно.
Другая проблема, над которой стоит подумать — поддержка текстов в разных кодировках. Поскольку мы собираемся считывать несколько разных файлов, часть которых может быть сохранена в виде однобайтовых строк (ANSI), а часть в виде широких двухбайтовых (UNICODE), желательно поручить самой системе осуществлять правильный выбор режимов на лету (от файла к файлу). Кроме того, файлы могут быть сохранены и в кодировке UTF-8.
Как оказалось, MQL умеет автоматически считывать разнообразные текстовые файлы в правильной кодировке, если задать следующие входные параметры функции FileOpen:
FileOpen(filename, FILE_READ | FILE_TXT | FILE_ANSI, 0, CP_UTF8);
Мы далее применим это сочетание, дополнив его, по умолчанию, флагами FILE_SHARE_READ | FILE_SHARE_WRITE.
В классе FileReader предусмотрим члены для хранения имени файла (filename), дескриптора открытого файла (handle), текущую строку текста (line).
class FileReader { protected: const string filename; int handle; string line;
Кроме того, будем отслеживать текущий номер строки и позицию курсора в строке (колонку).
int linenumber; int cursor;
Сохранять прочитанные строки будем в экземпляр объекта Source.
Source *text;
В конструктор передадим имя файла, флаги, а также готовый объект Source для приема данных.
public: FileReader(const string _filename, Source *container = NULL, const int flags = FILE_READ | FILE_TXT | FILE_ANSI | FILE_SHARE_READ | FILE_SHARE_WRITE, const uint codepage = CP_UTF8): filename(_filename) { handle = FileOpen(filename, flags, 0, codepage); if(handle == INVALID_HANDLE) { Print("FileOpen failed ", _filename, " ", GetLastError()); } line = NULL; cursor = 0; linenumber = 0; text = container; } string pathname() const { return filename; }
Проверим успешное открытие файла и позаботимся закрыть дескриптор в деструкторе.
bool isOK() { return (handle > 0); } ~FileReader() { FileClose(handle); }
Посимвольное чтение данных из файла обеспечит метод getChar.
ushort getChar(const bool autonextline = true) { if(cursor >= StringLen(line)) { if(autonextline) { if(!scanLine()) return 0; cursor = 0; } else { return 0; } } return StringGetCharacter(line, cursor++); }
Когда строка с текстом line пуста или прочитана до конца, данный метод пытается прочитать следующую строку с помощью метода scanLine. Если в строке line есть еще необработанные символы, getChar просто возвращает символ под курсором и перемещает курсор на следующую позицию.
Метод scanLine определен очевидным образом:
bool scanLine() { if(!FileIsEnding(handle)) { line = FileReadString(handle); linenumber++; cursor = 0; if(text != NULL) { text += line; text += '\n'; } return true; } return false; }
Обратите внимание, что поскольку файл открыт в текстовом режиме, символы переноса строк нам не возвращаются, однако они нужны для подсчета строк, а также в качестве конечных признаков некоторых языковых конструкций, например, однострочных комментариев. Поэтому мы добавляем символ '\n'.
Помимо собственно чтения данных из файла класс FileReader должен предоставить возможность сверять входные данные под курсором с лексемами. Для этого добавим следующие методы.
bool probe(const string lexeme) const { return StringFind(line, lexeme, cursor) == cursor; } bool match(const string lexeme) const { ushort c = StringGetCharacter(line, cursor + StringLen(lexeme)); return probe(lexeme) && (c == ' ' || c == '\t' || c == 0); } bool consume(const string lexeme) { if(match(lexeme)) { advance(StringLen(lexeme)); return true; } return false; } void advance(const int next) { cursor += next; if(cursor > StringLen(line)) { error(StringFormat("line is out of bounds [%d+%d]", cursor, next)); } }
Метод probe сравнивает текст с переданной лексемой. Метод match делает практически то же самое, но дополнительно проверяет, чтобы лексема была упомянута как отдельное слово, т.е. после неё должен следовать разделитель — пробел, табуляция или конец строки. Метод consume "поглощает" переданную лексему-слово, т.е. удостоверяется, что входной текст совпадает с заданным, и в случае успеха перемещает курсор за конец лексемы. В случае неуспеха курсор не двигается, а метод возвращает false. Метод advance просто перемещает курсор вперед на заданное количество символов.
Наконец, рассмотрим небольшой метод, возвращающий признак конца файла.
bool isEOF() { return FileIsEnding(handle) && cursor >= StringLen(line); }
В классе есть другие вспомогательные методы для чтения полей, с ними можно ознакомиться в прилагаемых исходных кодах.
Объекты класса FileReader должны где-то создаваться. Делегируем эту роль классу FileReaderController.FileReaderController
В классе FileReaderController необходимо поддерживать стек включаемых файлов (includes), карту уже включенных файлов (files), указатель на текущий обрабатываемый файл (current), а также входной текст (source).
class FileReaderController { protected: Stack<FileReader *> includes; Map<string, FileReader *> files; FileReader *current; const int flags; const uint codepage; ushort lastChar; Source *source;
Списки, стеки, массивы вроде BaseArray и карты Map, встречающиеся в исходных кодах, подключены из вспомогательных заголовочных файлов, которые не будут здесь описываться — они уже использовались в моих предыдущих статьях. Но полный архив, разумеется, прилагается и к данной статье.
Контроллер создает пустой объект source в своем конструкторе:
public: FileReaderController(const int _flags = FILE_READ | FILE_TXT | FILE_ANSI | FILE_SHARE_READ | FILE_SHARE_WRITE, const uint _codepage = CP_UTF8, const uint _length = SOURCE_LENGTH): flags(_flags), codepage(_codepage) { current = NULL; lastChar = 0; source = new Source(_length); }
Освобождение source, а заодно и подчиненных объектов FileReader из карты происходит в деструкторе:
#define CLEAR(P) if(CheckPointer(P) == POINTER_DYNAMIC) delete P; ~FileReaderController() { for(int i = 0; i < files.getSize(); i++) { CLEAR(files[i]); } delete source; }
Чтобы включить тот или иной файл в обработку, в том числе самый первый файл проекта с расширением mq5, предусмотрим метод include.
bool include(const string _filename) { Print((current != NULL ? "Including " : "Processing "), _filename); if(files.containsKey(_filename)) return true; if(current != NULL) { includes.push(current); } current = new FileReader(_filename, source, flags, codepage); source.mark(source.length(), current.pathname()); files.put(_filename, current); return current.isOK(); }
Он проверяет карту files, не был ли уже обработан заданный файл, и сразу возвращает true, если файл есть. В противном случае процесс продолжается. Если это самый первый файл, мы создаем объект FileReader, делаем его текущим (current) и запоминаем в карте files. Если же это не первый файл, т.е. какой-то файл в данный момент уже обрабатывается, то предварительно нужно сохранить его в стек includes. Когда включенный файл будет целиком обработан, мы вернемся к обработке текущего файла с того же самого места, где был подключен включаемый файл.
Одна строка в приведенном методе include пока не будет компилироваться:
source.mark(source.length(), current.pathname());
В классе source пока нет метода mark. Как должно быть понятно из контекста, мы в данном месте переключаемся из одного файла в другой, и потому должны пометить где-то источник и его смещение в объединенном тексте. Этим и будет заниматься метод mark. В любой момент текущая длина входного текста — это то место, куда будут добавляться данные нового файла. Вернемся в класс Source и добавим карту файлов:
class Source { private: Map<uint,string> files; public: void mark(const uint offset, const string file) { files.put(offset, file); }
Основную задачу по чтению символов из файла в классе FileReaderController выполняет метод getChar, который делегирует часть работы текущему объекту FileReader.
ushort getChar(const bool autonextline = true) { if(current == NULL) return 0; if(!current.isEOF()) { lastChar = current.getChar(autonextline); return lastChar; } else { while(includes.size() > 0) { current = includes.pop(); source.mark(source.length(), current.pathname()); if(!current.isEOF()) { lastChar = current.getChar(); return lastChar; } } } return 0; }
Если текущий файл имеется и не прочитан до конца, вызываем его метод getChar и возвращаем полученный символ. Если текущий файл прочитан до конца, смотрим, остались ли директивы включения других файлов на стеке includes. Если файлы есть, извлекаем верхний, делаем его текущим (current), и продолжаем читать символы из него. Кроме того, не забываем пометить в объекте source, что источник данных был переключен на старый файл.
Класс FileReaderController также умеет возвращать признак того, что чтение подошло к концу.
bool isAtEnd() { return current == NULL || (current.isEOF() && includes.size() == 0); }
Помимо прочего предоставим пару методов для получения текущего файла и текста.
const Source *text() const { return source; } FileReader *reader() { return current; }
Теперь все готово для предварительной обработки файлов препроцессором.
Preprocessor
Препроцессор будет управлять единственным экземпляром класса FileReaderController (controller), а также тем, нужно ли подгружать заголовочные файлы (флаг loadIncludes):
class Preprocessor { protected: FileReaderController *controller; const string includes; bool loadIncludes;
Дело в том, что некоторые файлы мы можем захотеть обработать без зависимостей — например, в целях отладки или уменьшения рабочего времени. Папку, в которой по умолчанию находятся заголовочные файлы, сохраним в строковой переменной includes.
Конструктор получает все эти значения, а также название начального файла (вместе с путем) от пользователя, создает контроллер и вызывает для файла метод include.
public: Preprocessor(const string _filename, const string _includes, const bool _loadIncludes = false, const int _flags = FILE_READ | FILE_TXT | FILE_ANSI | FILE_SHARE_READ | FILE_SHARE_WRITE, const uint _codepage = CP_UTF8, const uint _length = SOURCE_LENGTH): includes(_includes) { controller = new FileReaderController(_flags, _codepage, _length); controller.include(_filename); loadIncludes = _loadIncludes; }
А теперь напишем метод run, который будет вызываться клиентом непосредственно для запуска обработки одного или нескольких файлов.
bool run() { while(!controller.isAtEnd()) { if(!scanLexeme()) return false; } return true; }
Пока контроллер не упрется в конец данных, считываем лексемы.
А вот и метод scanLexeme:
bool scanLexeme() { ushort c = controller.getChar(); switch(c) { case '#': if(controller.reader().consume("include")) { if(!include()) { controller.reader().error("bad include"); return false; } } break; ... } return true; // symbol consumed }
Если программа видит символ '#', то пытается "поглотить" следующее слово "include". Если его нет, значит, то был одиночный символ '#' и он просто пропускается (getChar перемещает курсор на одну позицию вперед). Если найдено слово "include", нужно обработать директиву, чем занимается метод include.
bool include() { ushort c = skipWhitespace(); if(c == '"' || c == '<') { ushort q = c; if(q == '<') q = '>'; int start = controller.reader().column(); do { c = controller.getChar(); } while(c != q && c != 0); if(c == q) { if(loadIncludes) { Print(controller.reader().source()); int stop = controller.reader().column(); string name = StringSubstr(controller.reader().source(), start, stop - start - 1); string path = ""; if(q == '"') { path = controller.reader().pathname(); StringReplace(path, "\\", "/"); string parts[]; int n = StringSplit(path, '/', parts); if(n > 0) { ArrayResize(parts, n - 1); } else { Print("Path is empty: ", path); return false; } int upfolder = 0; while(StringFind(name, "../") == 0) { name = StringSubstr(name, 3); upfolder++; } if(upfolder > 0 && upfolder < ArraySize(parts)) { ArrayResize(parts, ArraySize(parts) - upfolder); } path = StringImplodeExt(parts, CharToString('/')) + "/"; } else // '<' '>' { path = includes; // folder; } return controller.include(path + name); } else { return true; } } else { Print("Incomplete include"); } } return false; }
Данный метод пропускает с помощью skipWhitespace (здесь не рассматривается) все пробелы после слова "include", находит открывающую кавычку или символ '<', затем сканирует текст вплоть до парной кавычки или закрывающего символа '>', и наконец выделяет строку с путем и именем заголовочного файла. Далее идет обработка вариантов подгрузки файла из той же папки или из стандартной папки заголовочных файлов. В результате формируется новый путь и имя для загрузки, после чего контроллеру поручается обработать файл.
Помимо обработки директивы #include нам необходимо пропускать блоки комментариев и строки, чтобы не трактовать их как инструкции, если внутри вдруг окажется лексема "#include". Поэтому добавим соответствующие варианты в оператор switch, в методе scanLexeme.
case '/': if(controller.reader().probe("*")) { controller.reader().advance(1); if(!blockcomment()) { controller.reader().error("bad block comment"); return false; } } else if(controller.reader().probe("/")) { controller.reader().advance(1); linecomment(); } break; case '"': if(!literal()) { controller.reader().error("unterminated string"); return false; } break;
Вот, например, как пропускаются блочные комментарии:
bool blockcomment() { ushort c = 0, c_; do { c_ = c; c = controller.getChar(); if(c == '/' && c_ == '*') return true; } while(!controller.reader().isEOF()); return false; }
Другие вспомогательные методы реализованы похожим образом.
Итак, имея класс Preprocessor и прочие классы, мы теоретически можем уже загружать текст из рабочих файлов, примерно так.
#property script_show_inputs input string SourceFile = "filename.txt"; input string IncludesFolder = ""; input bool LoadIncludes = false; void OnStart() { Preprocessor loader(SourceFile, IncludesFolder, LoadIncludes); if(!loader.run()) { Print("Loader failed"); return; } // output entire data as it is assembled from one or many files int handle = FileOpen("dump.txt", FILE_WRITE | FILE_TXT | FILE_ANSI, 0, CP_UTF8); FileWriteString(handle, loader.text().get()); FileClose(handle); }
Почему же "теоретически"? Дело в том, что MetaTrader позволяет нам работать только с файлами в "песочнице" — каталоге MQL5/Files. Однако наша цель — обработка исходных кодов, которые находятся в папках MQL5/Include, MQL5/Scripts, MQL5/Experts, MQL5/Indicators.
Для того чтобы обойти это ограничение, воспользуемся возможностью Windows назначать символические ссылки на объекты файловой системы. В нашем случае, для перенаправления доступа к папкам на локальном компьютере лучше всего подходят так называемые соединения (junction). Они создаются с помощью команды:
mklink /J new_name existing_target
Параметр new_name — имя новой виртуальной "папки", которая будет указывать на реальную папку existing_target.
Для создания соединений с указанными папками с исходными кодами откроем папку MQL5/Files, создадим в ней подпапку Sources и зайдем в неё. Далее копируем в неё файл makelink.bat, прилагаемый к статье. Этот командный сценарий фактически содержит одну строку:
mklink /J %1 "..\..\%1\"
Он принимает один входной параметр %1 — название прикладной папки из числа тех, что есть внутри MQL5 (например, "Include"). Относительный путь "..\..\" предполагает, что командный файл находится в указанной папке MQL5/Files/Sources, и тогда целевая папка (existing_target) сформируется как MQL5/%1. Например, если, находясь в папке Sources, выполнить команду
makelink Include
то в папке Sources появится виртуальная папка Include, зайдя в которую мы окажемся в MQL5/Include. По аналогии можно создать "двойники" для папок Experts, Scripts и других. На картинке ниже показан Проводник с открытой папкой MQL5/Include/Expert со стандартными заголовочными файлами, доступными внутри папки MQL5/Files/Sources.
Символические ссылки Windows для папок исходных кодов MQL5
При необходимости удалить символические ссылки можно как обычные файлы (но, разумеется, следует предварительно убедиться, что удаляется именно папка со значком стрелочки в её левом нижнем углу, т.е. ссылка, а не оригинальная папка).
Можно было бы создать соединение непосредственно на корневую рабочую папку MQL5, но я предпочитаю и рекомендую открывать доступ точечно: ведь все MQL-программы смогут по ссылке прочитать ваши исходные коды, включая, логины, пароли и суперсекретные торговые системы, если они там хранятся.После создания ссылок параметр IncludesFolder приведенного выше скрипта действительно будет работать: значение "Sources/Include/" указывает на реальную папку MQL5/Include. А в параметре SourceFile можно задать для анализа, например, исходный код какого-нибудь скрипта "Sources/Scripts/test.mq5".
Разбивка на токены
Типы токенов, которые требуется различать в MQL, сведены в единое перечисление TokenType, в одноименном заголовочном файле (прилагается). Приводить его в статье не будем. Обратим лишь внимание, что среди токенов есть односимвольные, например, такие как различные виды скобок ('(', '[', '{'), знак равно '=', плюс '+' или минус '-', а также двухсимвольные, например, '==', '!=' и т.д. Кроме того, отдельными токенами станут числа, строки, даты (т.е. константы поддерживаемых типов), все зарезервированные в MQL слова (операторы, типы, this, модификаторы вроде input, const и т.д.), а также идентификаторы (прочие слова). Дополнительно имеется токен EOF для обозначения конца входных данных.
Token
При просмотре текста сканер будет определять тип каждого следующего токена по специальному алгоритму (мы рассмотрим его ниже) и создавать объект класса Token. Это очень простой класс.
class Token { private: TokenType type; int line; int offset; int length; public: Token(const TokenType _type, const int _line, const int _offset, const int _length = 0) { type = _type; line = _line; offset = _offset; length = _length; } TokenType getType() const { return type; } int getLine() const { return line; } ... string content(const Source *source) const { return source.get(offset, length); } };
Объект хранит тип токена, его смещение в тексте и длину. При необходимости получить строковое значение токена мы передаем в метод content указатель на строку source и вырезаем из неё соответствующий фрагмент.
Теперь настало время обратиться к сканеру, который еще называют на английский лад "токенайзером".
Scanner (tokenizer)
В классе Scanner опишем статический массив с ключевыми словами MQL:
class Scanner { private: static string reserved[];
и далее в исходном коде проинициализируем его с помощью подключения текстового файла:
static string Scanner::reserved[] = { #include "reserved.txt" };
Дополним этот массив статической картой соответствия между строковым представлением и типом каждого токена.
static Map<string, TokenType> keywords;
Заполнение карты произведем в конструкторе (приведен чуть ниже).
В сканере нам также потребуется указатель на входные данные, результирующий список токенов, а также многочисленные счетчики.
const Source *source; // wrapped string List<Token *> *tokens; int start; int current; int line;
Переменная start будет всегда указывать на начало следующего, ожидающего обработки токена. Переменная current — это курсор перемещения по тексту. Он будет всегда "убегать" вперед от start по мере проверки текущих символов на соответствие какому-либо токену, и как только совпадение будет обнаружено, подстрока от start до current попадет в новый токен. Переменная line — номер текущей строки в общем тексте.
Конструктор класса Scanner:
public: Scanner(const Source *_source): line(0), current(0) { tokens = new List<Token *>(); if(keywords.getSize() == 0) { for(int i = 0; i < ArraySize(reserved); i++) { keywords.put(reserved[i], TokenType(BREAK + i)); } } source = _source; }
Здесь BREAK — это идентификатор типа токена для первого по алфавиту зарезервированного слова. Порядок строк в файле reserved.txt и идентификаторов в перечислении TokenType должен совпадать. Например, элементу BREAK в перечислении соответствует, очевидно, "break".
Центральное место в классе занимает метод scanTokens.
List<Token *> *scanTokens() { while(!isAtEnd()) { // We are at the beginning of the next lexeme start = current; scanToken(); } start = current; addToken(EOF); return tokens; }
В нем в цикле, пока не достигнут конец текста, генерируются новые и новые токены. Методы isAtEnd и addToken просты:
bool isAtEnd() const { return (uint)current >= source.length(); } void addToken(TokenType type) { tokens.add(new Token(type, line, start, current - start)); }
Всю черновую работу выполняет метод scanToken, но прежде чем его представить, необходимо познакомиться с несколькими простыми вспомогательными методами — они похожи на те, что мы уже видели в классе Preprocessor, поэтому их назначение, вероятно, не нужно объяснять.
bool match(ushort expected) { if(isAtEnd()) return false; if(source[current] != expected) return false; current++; return true; } ushort previous() const { if(current > 0) return source[current - 1]; return 0; } ushort peek() const { if(isAtEnd()) return '\0'; return source[current]; } ushort peekNext() const { if((uint)(current + 1) >= source.length()) return '\0'; return source[current + 1]; } ushort advance() { current++; return source[current - 1]; }
А вот теперь вернемся к методу scanToken.
void scanToken() { ushort c = advance(); switch(c) { case '(': addToken(LEFT_PAREN); break; case ')': addToken(RIGHT_PAREN); break; ...
Он читает следующий символ и в зависимости от его кода создает токен. Мы не будем приводить все односимвольные токены — их создание аналогично.
Если токен предполагает два символа, обработка усложняется:
case '-': addToken(match('-') ? DEC : (match('=') ? MINUS_EQUAL : MINUS)); break; case '+': addToken(match('+') ? INC : (match('=') ? PLUS_EQUAL : PLUS)); break; ...
Здесь показано формирование токенов для лексем '--', '-=', '++', '+='.
Текущая версия сканера пропускает комментарии:
case '/': if(match('/')) { // A comment goes until the end of the line while(peek() != '\n' && !isAtEnd()) advance(); }
Желающие могут сохранять их в специальных токенах.
Блочные конструкции вроде строк, литералов, директив препроцессора обрабатываются в выделенных вспомогательных методах, мы не будем рассматривать их подробно:
case '"': _string(); break; case '\'': literal(); break; case '#': preprocessor(); break;
Вот, например, как сканируется строка:
void _string() { while(!(peek() == '"' && previous() != '\\') && !isAtEnd()) { if(peek() == '\n') { line++; } advance(); } if(isAtEnd()) { error("Unterminated string"); return; } advance(); // The closing " addToken(CONST_STRING); }
Если ни один из типов токенов не сработал, выполняется проверка по-умолчанию — в неё попадают числа, идентификаторы и ключевые слова.
default: if(isDigit(c)) { number(); } else if(isAlpha(c)) { identifier(); } else { error("Unexpected character `" + ShortToString(c) + "` 0x" + StringFormat("%X", c) + " @ " + (string)current + ":" + source.get(MathMax(current - 10, 0), 20)); } break;
Реализации isDigit, isAlpha очевидны. Приведем здесь лишь метод identifier.
void identifier() { while(isAlphaNumeric(peek())) advance(); // See if the identifier is a reserved word string text = source.get(start, current - start); TokenType type = keywords.get(text); if(type == null) type = IDENTIFIER; addToken(type); }
Полные реализации всех методов можно посмотреть в прилагаемых исходных кодах. Чтобы не изобретать велосипед, я взял часть кода из книги Crafting Interpreters, хотя, конечно, потребовались некоторые исправления.
Вот, собственно, и весь сканер. При отсутствии ошибок метод scanTokens возвратит пользователю список токенов, который можно передавать парсеру. Однако парсер должен иметь грамматику, чтобы по ней разбирать список токенов. Поэтому прежде чем переходить к парсеру, необходимо рассмотреть описание грамматики. Оно у нас формируется из объектов класса Terminal и производных от него.Описание грамматики
Давайте для начала представим себе, что нужно описать грамматику не MQL, а некоего простого языка для вычисления арифметических выражений, калькулятора. Вот допустимая формула для вычисления:
(10 + 1) * 2
Разрешим только целые числа и операции '+', '-', '*', '/', причем без расстановки приоритетов: для приоритетов будем использовать скобки '(' ')'.
Входной точкой грамматики должен быть нетерминал, описывающий всё выражение целиком. Предположим для этого достаточно будет написать:
NonTerminal expression;
Выражение состоит из операндов — целочисленных значений — и символов операций. Всё это — терминалы, т.е. они могут быть созданы на основе токенов, которые поддерживает сканер.
Предположим, мы опишем их так:
Terminal plus(PLUS), star(STAR), minus(MINUS), slash(SLASH); Terminal value(CONST_INTEGER);
Как мы видим, конструктор терминалов должен допускать передачу типа токена в качестве параметра.
Самое простое выражение, какое может быть, это просто число. Логично обозначить это так:
expression = value;
Это перегрузка оператора присваивания. В ней нам потребуется сохранить внутри expression в какой-то переменной ссылку на объект value (дадим ей имя eq, от слова equivalence). Когда парсер получит задание проверить expression на соответствие введенной строке, он делегирует проверку нетерминалу, тот "увидит" у себя ссылку на value, попросит парсер проверить value, и проверка наконец дойдет до терминала, где просто произойдет сверка токенов — токена в терминале и токена во входном потоке.
Однако выражение может дополнительно иметь операцию и второй операнд — поэтому необходимо расширить правило expression. Для это предварительно опишем новый нетерминал:
NonTerminal operation; operation = (plus | star | minus | slash) + value;
Здесь происходит много интересных вещей за кадром. Оператор '|' должен быть перегружен в классе, чтобы обеспечить объединение элементов в логическую группу по ИЛИ. Однако оператор вызывается у терминала, простого символа, а нам нужна группа элементов. Поэтому первый элемент группы, для которого среда выполнения вызовет оператор (в данном случае — plus), должен проверить, является ли он членом какой-либо группы, и если группы еще нет — динамически создать её в виде объекта класса HiddenNonTerminalOR. Затем реализация перегруженного оператора должна включить this и соседний правый терминал star (переданный в качестве аргумента в функцию-оператор) в новосозданную группу. Оператор возвращает ссылку на эту группу, чтобы последующие (нанизанные цепочкой) операторы '|' вызывались уже для HiddenNonTerminalOR.
Для поддержания массива с членами группы, очевидно, предусмотрим в классе массив — next. Его название означает следующий уровень детализации элементов грамматики. У каждого элемента, который мы внесем в этот массив дочерних узлов, следует установить встречную ссылку на родительский узел — назовем его parent. Наличие ненулевого parent как раз и будет означать членство в группе. В результате выполнения приведенного кода внутри скобок мы получим HiddenNonTerminalOR с массивом, содержащим все 4 символа операций.
Далее в игру вступает перегруженный оператор '+'. Он должен работать по аналогии с оператором '|', то есть тоже создавать неявную группу элементов, но на этот раз — класса HiddenNonTerminalAND, и на стадии разбора они должны проверяться по правилу логического И.
Обратите внимание, что у нас формируется иерархия подчиненности терминалов и нетерминалов — в данном случае объект HiddenNonTerminalAND будет содержать два дочерних элемента: созданную только что группу HiddenNonTerminalOR и value. HiddenNonTerminalAND, в свою очередь, подчинен нетерминалу operation.
Приоритет операций '|' и '+' таков, что в отсутствии скобок И обрабатывается сперва, а ИЛИ потом. Именно поэтому в operation нам пришлось взять все варианты символов в скобки.
Имея определение нетерминала operation, мы можем подправить грамматику выражения:
expression = value + operation;
Она якобы описывает выражения вида A @ B, где A и B — целые числа, а @ — действие. Но здесь есть "засада".
У нас уже два правила, в которых участвует объект value. Это означает, что ссылка на родителя, установленная в первом правиле, будет переписана во втором. Чтобы этого не происходило, необходимо вставлять в правила не объекты, а их копии.
Мы для этого предусмотрим перегрузку двух операторов: '~' и '^'. Первый из них, унарный, ставится перед операндом. В объекте, получившем вызов соответствующей функции-оператора, будем динамически создавать объект-посредник и возвращать его в вызывающий код. Второй оператор — бинарный. В него помимо объекта будем передавать текущий номер строки в исходном коде грамматики, т.е. предопределенную компилятором MQL константу __LINE__. Таким образом, мы получим возможность отличать неявно описанные экземпляры объектов по номеру строк, где они создаются. Это поможет при отладке сложных грамматик. Иначе говоря, операторы '~' и '^' выполняют одну и ту же работу, но первый — в режиме релиза, а второй — в режиме отладки.
Копии-посредники представляют собой объект класса HiddenNonTerminal, в котором упомянутая ранее переменная eq ссылается на оригинальный объект.
Таким образом перепишем грамматику выражений с учетом создания объектов-посредников.
operation = (plus | star | minus | slash) + ~value; expression = ~value + operation;
Поскольку operation используется только один раз, для него можно не делать двойника. Каждая логическая ссылка увеличивает на единицу рекурсию при раскрытии выражения. Однако в целях избежания ошибок в больших грамматиках рекомендуется везде делать ссылки. Даже если сейчас какой-то нетерминал используется только раз, он может позднее появиться в другом месте грамматики. Мы предусмотрим в исходном коде проверку на переопределение родительского узла, чтобы выдавать сообщение об ошибке.
Теперь наша грамматика может обработать "10+1", но потеряла возможность прочитать отдельное число. Действительно, нетерминал operation должен быть опциональным. Для этих целей реализуем перегрузку оператора '*'. Если элемент грамматики умножен на 0, значит, его можно при проверке опустить (его отсутствие не приводит к ошибке).
expression = ~value + operation*0;
Перегрузка оператора умножения позволит реализовать и другую важную вещь — повторение элемента произвольное количество раз. В этом случае будем умножать элемент на 1. В классе терминала это свойство — множественность или опциональность — хранится в переменной mult. Случаи, когда некий элемент и опционален, и может повторяться много раз, легко реализуются двумя ссылками: первая должна быть опциональной (optional*0), а вторая — множественной (optional = element*1).
В текущей грамматике калькулятора есть еще один изъян. Она не приспособлена для длинных выражений с несколькими операциями, такими как 1+2+3+4+5. Чтобы исправить этот недостаток, следует изменить нетерминал operation.
operation = (plus | star | minus | slash) + ~expression;
Мы заменили value на сам expression, тем самым разрешив циклический разбор все новых и новых концовок выражений.
Остался последний штрих — поддержка выражений в скобках. Как не трудно догадаться, они выполняют ту же роль, что и единичное значение value. Поэтому переопределим его как альтернативу из двух вариантов: целого числа или подвыражения в скобках. Вся грамматика целиком будет выглядеть следующим образом:
NonTerminal expression; NonTerminal value; NonTerminal operation; Terminal number(CONST_INTEGER); Terminal left(LEFT_PAREN); Terminal right(RIGHT_PAREN); Terminal plus(PLUS), star(STAR), minus(MINUS), slash(SLASH); value = number | left + expression^__LINE__ + right; operation = (plus | star | minus | slash) + expression^__LINE__; expression = value + operation*0;
Рассмотрим более подробно, как указанные классы устроены внутри.
Terminal
В классе Terminal опишем поля для типа токена (me), свойства множественности (mult), опционального имени (name, для идентификации нетерминалов в логах), ссылок на продукцию (eq), на родителя (parent) и подчиненные элементы (массив next).
class Terminal { protected: TokenType me; int mult; string name; Terminal *eq; BaseArray<Terminal *> next; Terminal *parent;
Поля заполняются в конструкторах, а также в методах-"сеттерах", и читаются с помощью методов-"геттеров", которые здесь опустим для краткости.
Перегрузку операторов будем осуществлять по такому принципу:
virtual Terminal *operator|(Terminal &t) { Terminal *p = &t; if(dynamic_cast<HiddenNonTerminalOR *>(p.parent) != NULL) { p = p.parent; } if(dynamic_cast<HiddenNonTerminalOR *>(parent) != NULL) { parent.next << p; p.setParent(parent); } else { if(parent != NULL) { Print("Bad OR parent: ", parent.toString(), " in ", toString()); ... error } else { parent = new HiddenNonTerminalOR("hiddenOR"); p.setParent(parent); parent.next << &this; parent.next << p; } } return parent; }
Здесь показана группировка по ИЛИ. По И — все аналогично.
Установка признака множественности — в операторе '*':
virtual Terminal *operator*(const int times) { mult = times; return &this; }
О корректном удалении динамически созданных экземпляров позаботимся в деструкторе.
~Terminal() { Terminal *p = dynamic_cast<HiddenNonTerminal *>(parent); while(CheckPointer(p) != POINTER_INVALID) { Terminal *d = p; if(CheckPointer(p.parent) == POINTER_DYNAMIC) { p = dynamic_cast<HiddenNonTerminal *>(p.parent); } else { p = NULL; } CLEAR(d); } }
И наконец — главный метод класса Terminal, ответственный за парсинг.
virtual bool parse(Parser *parser) { Token *token = parser.getToken(); bool eqResult = true;
Здесь мы получили ссылку на парсер, прочитали из него текущий токен (класс парсера рассмотрим ниже).
if(token.getType() == EOF && mult == 0) return true;
Если токен — EOF, а текущий элемент — опциональный, значит обнаружен корректный конец текста.
Далее проверим, есть ли ссылка из перегруженного оператора '=' на оригинальный экземпляр элемента, если мы находимся в копии. Если ссылка есть, отправим её на проверку парсеру в метод match.
if(eq != NULL) // redirect { eqResult = parser.match(eq); bool lastResult = eqResult; // if multiple tokens expected and while next tokens are successfully consumed while(eqResult && eq.mult == 1 && parser.getToken() != token && parser.getToken().getType() != EOF) { token = parser.getToken(); eqResult = parser.match(eq); } eqResult = lastResult || (mult == 0); return eqResult; // redirect was fulfilled }
Кроме того, здесь обрабатывается ситуация, когда элемент может повторяться (mult = 1): парсер вызывается снова и снова, пока метод match возвращает успех.
Признак успеха — true или false — возвращается из метода parse как в этой ветке, так и в других ситуациях, например, для терминала:
if(token.getType() == me) // token match { parser.advance(parent); return true; }
Для терминала просто сравниваем его токен me с текущим токеном во входных данных, и, если есть соответствие, поручаем парсеру с помощью метода advance передвинуть курсор на следующий входной токен. В этом же методе парсер сообщает клиентской программе, что произошла продукция в нетерминале parent.
Для группы элементов все несколько сложнее. Рассмотрим случай логического И, вариант для ИЛИ будет похож. С помощью виртуального метода hasAnd (в классе Terminal он возвращает false, а в наследниках перекрыт) определяем, заполнен ли массив с подчиненными элементами для проверки по И.
else if(hasAnd()) // check AND-ed conditions { parser.pushState(); for(int i = 0; i < getNext().size(); i++) { if(!parser.match(getNext()[i])) { if(mult == 0) { parser.popState(); return true; } else { parser.popState(); return false; } } } parser.commitState(parent); return true; }
Поскольку данный нетерминал будет считаться правильным, если все его компоненты совпадут с грамматикой, мы вызываем метод match парсера для них всех, в цикле. Если случится хоть один отрицательный результат, вся проверка провалится. Однако есть одно исключение: если нетерминал опциональный, правила грамматики всё равно будут удовлетворены даже при возврате false из метода match.
Обратите внимание, что мы перед циклом сохраняем в парсере текущее состояние (pushState), при досрочном выходе восстанавливаем его (popState), а при полностью завершившейся успешной проверке подтверждаем новое состояние (commitState). Это необходимо для того, чтобы отложить уведомления для клиентского кода о новой "продукции" до тех пор, когда всё правило грамматики сработает целиком. Под словом "состояние" на самом деле скрывается просто текущая позиция курсора в потоке входных токенов.
Если ни токен, ни группы подчиненных элементов не сработали внутри метода parse, нам остается лишь проверить опциональность текущего объекта:
else if(mult == 0) // last chance { // parser.advance(); - don't consume token and proceed to next production return true; }
В противном случае мы "проваливаемся" в окончание метода, которое сигнализирует ошибку — текст не соответствует грамматике.
if(dynamic_cast<HiddenNonTerminal *>(&this) == NULL) { parser.trackError(&this); } return false; }
Теперь опишем классы, унаследованные от класса Terminal.
Нетерминалы — скрытые и явные
Основная задача класса HiddenNonTerminal — создавать динамические копии объектов и чистить мусор.
class HiddenNonTerminal: public Terminal { private: static List<Terminal *> dynamic; // garbage collector public: HiddenNonTerminal(const string id = NULL): Terminal(id) { } HiddenNonTerminal(HiddenNonTerminal &ref) { eq = &ref; } virtual HiddenNonTerminal *operator~() { HiddenNonTerminal *p = new HiddenNonTerminal(this); dynamic.add(p); return p; } ... };
Класс HiddenNonTerminalOR обеспечивает перегрузку оператора '|' (более простую, чем в классе Terminal, потому что HiddenNonTerminalOR — сам является "контейнером" — владельцем группы подчиненных элементов грамматики).
class HiddenNonTerminalOR: public HiddenNonTerminal { public: virtual Terminal *operator|(Terminal &t) override { Terminal *p = &t; next << p; p.setParent(&this); return &this; } ... };
Класс HiddenNonTerminalAND реализован аналогично.
Класс NonTerminal обеспечивает перегрузку оператора '=' ("продукцию" в правилах).
class NonTerminal: public HiddenNonTerminal { public: NonTerminal(const string id = NULL): HiddenNonTerminal(id) { } virtual Terminal *operator=(Terminal &t) { Terminal *p = &t; while(p.getParent() != NULL) { p = p.getParent(); if(p == &t) { Print("Cyclic dependency in assignment: ", toString(), " <<== ", t.toString()); p = &t; break; } } if(dynamic_cast<HiddenNonTerminal *>(p) != NULL) { eq = p; } else { eq = &t; } eq.setParent(this); return &this; } };
Наконец, есть еще класс Rule — наследник NonTerminal, но вся его роль заключается в том, чтобы при описании грамматики можно было некоторые правила помечать как основные (если они порождают объект Rule) или второстепенные (если их результат - NonTerminal).
Для удобства описания нетерминалов созданы макросы:
// debug #define R(Y) (Y^__LINE__) // release #define R(Y) (~Y) #define _DECLARE(Cls) NonTerminal Cls(#Cls); Cls #define DECLARE(Cls) Rule Cls(#Cls); Cls #define _FORWARD(Cls) NonTerminal Cls(#Cls); #define FORWARD(Cls) Rule Cls(#Cls);
В качестве аргумента макросов указывается строка — уникальное имя. Форвад-декларация потребуется в тех случаях, когда нетерминалы ссылаются друг на друга — мы видели это в грамматике калькулятора.
Кроме того, для порождения терминалов с токенами реализован специальный класс Keywords с поддержкой сборки мусора.
class Keywords { private: static List<Terminal *> keywords; public: static Terminal *get(const TokenType t, const string value = NULL) { Terminal *p = new Terminal(t, value); keywords.add(p); return p; } };
А для его использования при описании грамматики — свои макросы:
#define T(X) Keywords::get(X) #define TC(X,Y) Keywords::get(X,Y)
Посмотрим, как рассмотренная ранее грамматика калькулятора описывается с применением реализованных программных интерфейсов.
FORWARD(expression);
_DECLARE(value) = T(CONST_INTEGER) | T(LEFT_PAREN) + R(expression) + T(RIGHT_PAREN);
_DECLARE(operation) = (T(PLUS) | T(STAR) | T(MINUS) | T(SLASH)) + R(expression);
expression = R(value) + R(operation)*0;
Наконец, мы готовы изучить класс Parser.
Parser
Класс Parser имеет члены для хранения входного списка токенов (tokens), текущей позиции в нем (cursor), максимально известной позиции (maxcursor, она используется для диагностики ошибок), стека позиций перед вызовами вложенных групп элементов (states, для отката, вспоминаем про backtracking) и ссылки на входной текст (source, для печати логов и других целей).
class Parser { private: BaseArray<Token *> *tokens; // input stream int cursor; // current token int maxcursor; BaseArray<int> states; const Source *source;
Кроме того, парсер отслеживает всю иерархию вызовов по элементам грамматики с помощью стека stack. Применяемый в этом шаблоне класс TreeNode — простой контейнер для пары (терминал,токен) — его исходный код можно посмотреть в прилагаемом архиве. Ошибки накапливаются для диагностики в другом стеке — errors.
// current stack, how the grammar unwinds Stack<TreeNode *> stack; // holds current stack on every problematic point Stack<Stack<TreeNode *> *> errors;
Конструктор парсера принимает список токенов, исходный текст и опциональный флаг включения постройки синтаксического дерева в процессе разбора.
public: Parser(BaseArray<Token *> *_tokens, const Source *text, const bool _buildTree = false)
Когда режим дерева включен, все успешные "продукции", попадавшие на стек в виде объектов TreeNode нанизываются на корень дерева — переменную tree:
TreeNode *tree; // concrete syntax tree (optional result)
Для этих целей класс TreeNode поддерживает массив дочерних узлов. После окончания работы парсера дерево (если оно было включено) можно получить с помощью метода:
const TreeNode *getCST() const { return tree; }
Основной метод парсера — match — в упрощенном виде выглядит так.
bool match(Terminal *p) { TreeNode *node = new TreeNode(p, getToken()); stack.push(node); int previous = cursor; bool result = p.parse(&this); stack.pop(); if(result) // success { if(stack.size() > 0) // there is a holder to bind to { if(cursor > previous) // token was consumed { stack.top().bind(node); } else { delete node; } } } else { delete node; } return result; }
Методы advance и commitState, которые мы видели при знакомстве с классами терминалов, реализованы примерно так (кое-какие нюансы опущены).
void advance(const Terminal *p) { production(p, cursor, tokens[cursor], stack.size()); if(cursor < tokens.size() - 1) cursor++; if(cursor > maxcursor) { maxcursor = cursor; errors.clear(); } } void commitState(const Terminal *p) { int x = states.pop(); for(int i = x; i < cursor; i++) { production(p, i, tokens[i], stack.size()); } }
advance продвигает курсор по списку токенов. Если позиция стала больше максимальной, можно удалить накопившиеся ошибки — ведь они записываются при каждой неудачной проверке.
Метод production использует интерфейс обратного вызова, чтобы уведомить пользователя парсера о "продукции" — мы применим его далее в тестах.
void production(const Terminal *p, const int index, const Token *t, const int level) { if(callback) callback.produce(&this, p, index, t, source, level); }
Интерфейс определен как:
interface Callback { void produce(const Parser *parser, const Terminal *, const int index, const Token *, const Source *context, const int level); void backtrack(const int index); };
Объект, реализующий данный интерфейс на стороне клиента, может подключиться к парсеру с помощью метода setCallback — тогда он будет вызываться на каждой "продукции". Альтернативно такой объект можно подключить индивидуально к любому терминалу благодаря перегрузке оператора [Callback *]. Это полезно для отладки, чтобы поставить точки остановки в конкретных точках грамматики.
Попробуем парсер на практике.Практика, часть 1: калькулятор
У нас уже имеется грамматика калькулятора. Создадим для неё отладочный скрипт. Его же будем затем дополнять для тестов с грамматикой MQL.
#property script_show_inputs enum TEST_GRAMMAR {Expression, MQL}; input TEST_GRAMMAR TestMode = Expression;; input string SourceFile = "Sources/calc.txt";; input string IncludesFolder = "Sources/Include/";; input bool LoadIncludes = false; input bool PrintCST = false; #include <mql5/scanner.mqh> #include <mql5/prsr.mqh> void OnStart() { Preprocessor loader(SourceFile, IncludesFolder, LoadIncludes); if(!loader.run()) { Print("Loader failed"); return; } Scanner scanner(loader.text()); List<Token *> *tokens = scanner.scanTokens(); if(!scanner.isSuccess()) { Print("Tokenizer failed"); delete tokens; return; } Parser parser(tokens, loader.text(), PrintCST); if(TestMode == Expression) { testExpressionGrammar(&parser); } else { //... } delete tokens; } void testExpressionGrammar(Parser *p) { _FORWARD(expression); _DECLARE(value) = T(CONST_INTEGER) | T(LEFT_PAREN) + R(expression) + T(RIGHT_PAREN); _DECLARE(operation) = (T(PLUS) | T(STAR) | T(MINUS) | T(SLASH)) + R(expression); expression = R(value) + R(operation)*0; while(p.match(&expression) && !p.isAtEnd()) { Print("", "Unexpected end"); break; } if(p.isAtEnd()) { Print("Success"); } else { p.printState(); } if(PrintCST) { Print("Concrete Syntax Tree:"); TreePrinter printer(p); printer.printTree(); } Comment(""); }
Суть скрипта: прочитать переданный файл в препроцессоре, преобразовать в поток токенов с помощью сканера и проверить парсером на указанную грамматику. Проверка осуществляется вызовом метода match, в который передается корневое правило грамматики — expression.
В качестве опции (PrintCST) мы можем вывести в лог синтаксическое дерево обработанного выражения с помощью служебного класса TreePrinter.
Внимание! Для реальных программ дерево будет очень большое. Данная опция рекомендуется только при отладке мелких фрагментов грамматик или если вся грамматика небольшая, как в случае нашего калькулятора.
Если запустить тестовый скрипт для файла с выражением "(10+1)*2", получим следующее дерево (не забудьте выбрать TestMode равный Expression и PrintCST - true):
Concrete Syntax Tree: | | |Terminal LEFT_PAREN @ ( | | | | |Terminal CONST_INTEGER @ 10 | | | |NonTerminal value | | | | |Terminal PLUS @ + | | | | | | |Terminal CONST_INTEGER @ 1 | | | | | |NonTerminal value | | | | |NonTerminal expression | | | |NonTerminal operation | | |NonTerminal expression | | |Terminal RIGHT_PAREN @ ) | |NonTerminal value | | |Terminal STAR @ * | | | | |Terminal CONST_INTEGER @ 2 | | | |NonTerminal value | | |NonTerminal expression | |NonTerminal operation |NonTerminal expression
Вертикальные линии обозначают уровни обработки тех нетерминалов, которые явно описаны в грамматике (именованные). Пробелы соответствуют уровням, где "раскрывались" неявно созданные нетерминалы классов HiddenXYZ — все такие узлы по умолчанию не выводятся в лог, но в классе TreePrinter есть опция для их включения.
Обратите внимание, что опция PrintCST работает на основе специальной структуры с мета-данными — дереве из объектов TreeNode. Наш парсер способен опционально выдавать её после анализа в ответ на вызов метода getCST. Напомним, что включение режима сборки дерева задается третьим параметром конструктора парсера.
Можно поэкспериментировать с другими выражениями, в том числе и неправильными, чтобы убедиться, что обработка ошибок есть. Например, если испортить выражение, сделав его "10+", получим сообщение:
Failed First 2 tokens read out of 3 Source: EOF (file:Sources/Include/Layouts/calc.txt; line:1; offset:4) `` Expected: CONST_INTEGER in expression;operation;expression;value; LEFT_PAREN in expression;operation;expression;value;
Итак, все классы работают. Можно приступать к основной практической части — синтаксическому анализу MQL.
Практика, часть 2: грамматика MQL
С технической точки зрения все готово для написания грамматики MQL. Однако она — значительно сложнее, чем маленький калькулятор. Создавать её с нуля было бы непосильной задачей. Для решения проблемы воспользуемся тем, что MQL является подобием C++.
Для C++ можно найти много готовых описаний грамматики в публичном доступе. Один из них в виде файла cppgrmr.htm приложен к статье. Перенести его полностью в нашу грамматику также проблематично. Во-первых, многие конструкции в MQL всё же не поддерживаются. Во-вторых, в нотации часто присутствует левая рекурсия, из-за которой правила приходится менять. Наконец, в-третьих, желательно ограничивать размер грамматики, потому что он отрицательно сказывается на скорости обработки: некоторые редко используемые "фичи" имеет смысл оставить для факультативного добавления силами тех, кому они потребуются.
Последовательность, в которой упоминаются альтернативы ИЛИ, имеет значение, так как первый сработавший вариант обрывает последующие проверки. Если варианты могут при некоторых условиях частично совпадать из-за пропуска необязательных элементов, то их нужно либо перекомпоновать, либо сперва указать более длинные и специфические конструкции, а более общие и короткие - потом.
Продемонстрируем, как некоторые нотации из htm-файла преобразованы в грамматику наших правил и терминалов.
В C++ грамматике:
assignment-expression: conditional-expression unary-expression assignment-operator assignment-expression assignment-operator: one of = *= /= %= += –= >= <= &= ^= |=
В MQL грамматике:
_FORWARD(assignment_expression); _FORWARD(unary_expression); ... assignment_expression = R(unary_expression) + R(assignment_operator) + R(assignment_expression) | R(conditional_expression); _DECLARE(assignment_operator) = T(EQUAL) | T(STAR_EQUAL) | T(SLASH_EQUAL) | T(DIV_EQUAL) | T(PLUS_EQUAL) | T(MINUS_EQUAL) | T(GREATER_EQUAL) | T(LESS_EQUAL) | T(BIT_AND_EQUAL) | T(BIT_XOR_EQUAL) | T(BIT_OR_EQUAL);
В C++ грамматике:
unary-expression: postfix-expression ++ unary-expression –– unary-expression unary-operator cast-expression sizeof unary-expression sizeof ( type-name ) allocation-expression deallocation-expression
В MQL грамматике:
unary_expression = R(postfix_expression) | T(INC) + R(unary_expression) | T(DEC) + R(unary_expression) | R(unary_operator) + R(cast_expression) | T(SIZEOF) + T(LEFT_PAREN) + R(type) + T(RIGHT_PAREN) | R(allocation_expression) | R(deallocation_expression);
В C++ грамматике:
statement: labeled-statement expression-statement compound-statement selection-statement iteration-statement jump-statement declaration-statement asm-statement try-except-statement try-finally-statement
В MQL грамматике:
statement = R(expression_statement) | R(codeblock) | R(selection_statement) | R(labeled_statement) | R(iteration_statement) | R(jump_statement);
Правило для declaration_statement в грамматике MQL тоже есть, но перенесено. Многие правила были записаны в упрощенном по сравнению с C++ виде. В принципе, данная грамматика — это живой организм, или, как говорится англичанами, "работа в прогрессе". Весьма вероятно наличие ошибок при интерпретации специфических конструкций в исходных кодах.
Точкой входа для MQL грамматики является правило program, состоящие из 1 или более element-ов:
_DECLARE(element) =
R(class_decl)
| R(declaration_statement) | R(function) | R(sharp) | R(macro);
_DECLARE(program) = R(element)*1;
В нашем тестовом скрипте представленная грамматика MQL описана в функции testMQLgrammar:
void testMQLgrammar(Parser *p) { // all grammar rules go first // ... _DECLARE(program) = R(element)*1;
И в ней же запускается парсинг (по аналогии с калькулятором):
while(p.match(&program) && !p.isAtEnd())
...
При возникновении ошибки следует локализовать проблемный элемент по логам и отлаживать конкретное правило грамматики на отдельном входном фрагменте текста (рекомендуется фрагмент, в котором не более 5-6 токенов). Иными словами следует вызывать метод match парсера для конкретного правила и подавать на вход файл с отдельной языковой конструкцией. Для вывода в лог трейсов парсера необходимо в скрипте раскомментировать директиву:
//#define PRINTX Print
Внимание! Объем выводимой информации очень большой.
Перед отладкой рекомендуется разносить разные элементы правила по разным строкам, т.к. это пометит анонимные копии объектов уникальными номерами исходных строк.Впрочем, парсер создавался не для того, чтобы проверить соответствие текста на синтаксис MQL, а для извлечения семантических данных. Попробуем это сделать.
Практика, часть 3: список методов классов и иерархия классов
В качестве первой прикладной задачи, основанной на синтаксическом анализе MQL, составим перечень всех методов классов. Для этого определим класс, реализующий интерфейс Callback, и будем регистрировать интересующие нас "продукции".
В принципе, синтаксический анализ более логично было бы выполнять на основе синтаксического дерева. Но это — накладные расходы на память для хранения дерева и отдельный алгоритм по обходу этого дерева. Однако обход в том же порядке уже фактически делается самим парсером во время разбора текста (ведь именно в этой последовательности дерево и строилось бы, если включен соответствующий режим). Поэтому проще проводить анализ на лету.
В грамматике MQL есть такое правило:
_DECLARE(method) = R(template_decl)*0 + R(method_specifiers)*0 + R(type) + R(name_with_arg_list) + R(modifiers)*0;
Оно состоит из множества других нетерминалов, которые в свою очередь раскрываются через другие нетерминалы, так что синтаксическое дерево метода — очень разветвленное. В обработчике продукции будем перехватывать все фрагменты, относящиеся к нетерминалу "method" и складывать их в одну общую строку. В тот момент, когда очередная продукция окажется для другого нетерминала, значит, описание метода закончилось и можно вывести в лог результат.
class MyCallback: public Callback { virtual void produce(const Parser *parser, const Terminal *p, const int index, const Token *t, const Source *context, const int level) override { static string method = ""; // collect all tokens from `method` nonterminal if(p.getName() == "method") { method += t.content(context) + " "; } // as soon as other [non]terminal is detected and string is filled, signature is ready else if(method != "") { Print(method); method = ""; } }
Чтобы подключить свой обработчик к парсеру, дополним тестовый скрипт таким образом (в OnStart):
MyCallback myc; Parser parser(tokens, loader.text(), PrintCST); parser.setCallback(&myc);
В дополнение к списку методов соберем информацию о декларации классов — она, в частности, потребуется для определения контекста, в котором определены методы, но также мы сможем построить иерархию наследования.
Для хранения мета-информации о произвольном классе подготовим класс Class ;-).
class Class { private: BaseArray<Class *> subclasses; Class *superclass; string name; public: Class(const string n): name(n), superclass(NULL) { } ~Class() { subclasses.clear(); } void addSubclass(Class *derived) { derived.superclass = &this; subclasses.add(derived); } bool hasParent() const { return superclass != NULL; } Class *operator[](int i) const { return subclasses[i]; } int size() const { return subclasses.size(); } ... };
В нем имеется массив наследников subclasses и ссылка на родителя superclass. Заполнением этих взаимосвязанных полей занимается метод addSubclass. Экземпляры объектов Class будем складывать в карту со строковым ключом в виде имени класса:
Map<string,Class *> map;
Карта находится все в том же объекте MyCallback.
Теперь мы можем дополнить метод produce из интерфейса Callback. Чтобы собирать токены, относящиеся к декларации класса, придется перехватывать чуть больше правил, поскольку нам нужна не просто декларация целиком, но с выделенными специфическими свойствами: именем нового класса, типами его шаблона (если они есть), именем базового класса и типами его шаблона (если они есть).
Добавим соответствующие переменные для сбора данных (внимание, классы в MQL могут быть вложенными, хоть это и встречается редко, но мы здесь для простоты это не учитываем! Вместе с тем, наша грамматика MQL это поддерживает).
static string templName = ""; static string templBaseName = ""; static string className = ""; static string baseName = "";
Идентификаторы в контексте нетерминала "template_decl" - это шаблонные типы:
if(p.getName() == "template_decl" && t.getType() == IDENTIFIER) { if(templName != "") templName += ","; templName += t.content(context); }
Соответствующие правила грамматики для "template_decl", а также используемых далее объектов, можно изучить в прилагаемых исходных кодах.
Идентификатор в контексте нетерминала "class_name" - это имя класса, а если templName к этому времени не пустая строка, значит это шаблонные типы, которые нужно добавить в описание:
if(p.getName() == "class_name" && t.getType() == IDENTIFIER) { className = t.content(context); if(templName != "") { className += "<" + templName + ">"; templName = ""; } }
Первый идентификатор в контексте "derived_clause" (если он есть) — это имя базового класса.
if(p.getName() == "derived_clause" && t.getType() == IDENTIFIER) { if(baseName == "") baseName = t.content(context); else { if(templBaseName != "") templBaseName += ","; templBaseName += t.content(context); } }
Все последующие идентификаторы — шаблонные типы базового класса.
Когда декларация класса завершена, в грамматике срабатывает правило "class_decl". В этот момент все данные уже собраны и их можно заносить в карту классов.
if(p.getName() == "class_decl") // finalization { if(className != "") { if(map[className] == NULL) { map.put(className, new Class(className)); } else { // Class already defined, maybe forward declaration } } if(baseName != "") { if(templBaseName != "") { baseName += "<" + templBaseName + ">"; } Class *base = map[baseName]; if(base == NULL) { // Unknown class, maybe not included, but strange base = new Class(baseName); map.put(baseName, base); } if(map[className] == NULL) { Print("Error: base name `", baseName, "` resolved before declaration of the class: ", className); } else { base.addSubclass(map[className]); } baseName = ""; } className = ""; templName = ""; templBaseName = ""; }
В конце мы очищаем все строки и ждем появления следующих деклараций.
После успешного парсинга программного текста остается любым удобным образом отобразить иерархию классов. В тестовом скрипте класс MyCallback предоставляет функцию print для вывода в лог. Она, в свою очередь, использует метод print в самих объектах класса Class. Мы оставим эти вспомогательные алгоритмы для самостоятельного ознакомления, и кроме того – как еще одну маленькую программистскую задачу для желающих помериться силами (такие состязания часто самопроизвольно возникают на форуме mql5.com). Имеющаяся реализация — чисто утилитарная и не претендует на оптимальность, в ней просто обеспечена цель: отображение древовидной иерархии объектов типа Class в логе наиболее наглядным образом. Но это наверняка можно сделать более эффективно.
Проверим работу тестового скрипта для анализа некоторых MQL-проектов. Здесь и далее установим параметр TestMode = MQL.
Например, для стандартного эксперта "MACD Sample.mq5", задав SourceFile = "Sources/Experts/Examples/MACD/MACD Sample.mq5", а также LoadIncludes = true, то есть со всеми зависимостями, получим следующий результат (список методов сильно сокращен):
Processing Sources/Experts/Examples/MACD/MACD Sample.mq5 Scanning... #include <Trade\Trade.mqh> Including Sources/Include/Trade\Trade.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "StdLibErr.mqh" Including Sources/Include/StdLibErr.mqh #include "OrderInfo.mqh" Including Sources/Include/Trade/OrderInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "SymbolInfo.mqh" Including Sources/Include/Trade/SymbolInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "PositionInfo.mqh" Including Sources/Include/Trade/PositionInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "SymbolInfo.mqh" Including Sources/Include/Trade/SymbolInfo.mqh #include <Trade\PositionInfo.mqh> Including Sources/Include/Trade\PositionInfo.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "SymbolInfo.mqh" Including Sources/Include/Trade/SymbolInfo.mqh Files processed: 8 Source length: 175860 File map: Sources/Experts/Examples/MACD/MACD Sample.mq5 0 Sources/Include/Trade\Trade.mqh 900 Sources/Include/Object.mqh 1277 Sources/Include/StdLibErr.mqh 1657 Sources/Include/Object.mqh 2330 Sources/Include/Trade\Trade.mqh 3953 Sources/Include/Trade/OrderInfo.mqh 4004 Sources/Include/Trade/SymbolInfo.mqh 4407 Sources/Include/Trade/OrderInfo.mqh 38837 Sources/Include/Trade\Trade.mqh 59925 Sources/Include/Trade/PositionInfo.mqh 59985 Sources/Include/Trade\Trade.mqh 75648 Sources/Experts/Examples/MACD/MACD Sample.mq5 143025 Sources/Include/Trade\PositionInfo.mqh 143091 Sources/Experts/Examples/MACD/MACD Sample.mq5 158754 Lines: 4170 Tokens: 18005 Defining grammar... Parsing... CObject :: CObject * Prev ( void ) const CObject :: void Prev ( CObject * node ) CObject :: CObject * Next ( void ) const CObject :: void Next ( CObject * node ) CObject :: virtual bool Save ( const int file_handle ) CObject :: virtual bool Load ( const int file_handle ) CObject :: virtual int Type ( void ) const CObject :: virtual int Compare ( const CObject * node , const int mode = 0 ) const CSymbolInfo :: string Name ( void ) const CSymbolInfo :: bool Name ( const string name ) CSymbolInfo :: bool Refresh ( void ) CSymbolInfo :: bool RefreshRates ( void ) ... CSampleExpert :: bool Init ( void ) CSampleExpert :: void Deinit ( void ) CSampleExpert :: bool Processing ( void ) CSampleExpert :: bool InitCheckParameters ( const int digits_adjust ) CSampleExpert :: bool InitIndicators ( void ) CSampleExpert :: bool LongClosed ( void ) CSampleExpert :: bool ShortClosed ( void ) CSampleExpert :: bool LongModified ( void ) CSampleExpert :: bool ShortModified ( void ) CSampleExpert :: bool LongOpened ( void ) CSampleExpert :: bool ShortOpened ( void ) Success Class hierarchy: CObject ^ +--CSymbolInfo +--COrderInfo +--CPositionInfo +--CTrade +--CPositionInfo CSampleExpert
Теперь попробуем сторонний проект. Я взял эксперт SlidingPuzzle2 вот из этой статьи. Он у меня размещен по пути SourceFile = "Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5". Также подключив все заголовочные файлы (LoadIncludes = true), получим результат (сокращенный):
Processing Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5 Scanning... #include "SlidingPuzzle2.mqh" Including Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh #include <Layouts\GridTk.mqh> Including Sources/Include/Layouts\GridTk.mqh #include "Grid.mqh" Including Sources/Include/Layouts/Grid.mqh #include "Box.mqh" Including Sources/Include/Layouts/Box.mqh #include <Controls\WndClient.mqh> Including Sources/Include/Controls\WndClient.mqh #include "WndContainer.mqh" Including Sources/Include/Controls/WndContainer.mqh #include "Wnd.mqh" Including Sources/Include/Controls/Wnd.mqh #include "Rect.mqh" Including Sources/Include/Controls/Rect.mqh #include <Object.mqh> Including Sources/Include/Object.mqh #include "StdLibErr.mqh" Including Sources/Include/StdLibErr.mqh #include "Scrolls.mqh" Including Sources/Include/Controls/Scrolls.mqh #include "WndContainer.mqh" Including Sources/Include/Controls/WndContainer.mqh #include "Panel.mqh" Including Sources/Include/Controls/Panel.mqh #include "WndObj.mqh" Including Sources/Include/Controls/WndObj.mqh #include "Wnd.mqh" Including Sources/Include/Controls/Wnd.mqh #include <Controls\Edit.mqh> Including Sources/Include/Controls\Edit.mqh #include "WndObj.mqh" Including Sources/Include/Controls/WndObj.mqh #include <ChartObjects\ChartObjectsTxtControls.mqh> Including Sources/Include/ChartObjects\ChartObjectsTxtControls.mqh #include "ChartObject.mqh" Including Sources/Include/ChartObjects/ChartObject.mqh #include <Object.mqh> Including Sources/Include/Object.mqh Files processed: 17 Source length: 243134 File map: Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5 0 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh 493 Sources/Include/Layouts\GridTk.mqh 957 Sources/Include/Layouts/Grid.mqh 1430 Sources/Include/Layouts/Box.mqh 1900 Sources/Include/Controls\WndClient.mqh 2377 Sources/Include/Controls/WndContainer.mqh 2760 Sources/Include/Controls/Wnd.mqh 3134 Sources/Include/Controls/Rect.mqh 3509 Sources/Include/Controls/Wnd.mqh 14312 Sources/Include/Object.mqh 14357 Sources/Include/StdLibErr.mqh 14737 Sources/Include/Object.mqh 15410 Sources/Include/Controls/Wnd.mqh 17033 Sources/Include/Controls/WndContainer.mqh 46214 Sources/Include/Controls\WndClient.mqh 61689 Sources/Include/Controls/Scrolls.mqh 61733 Sources/Include/Controls/Panel.mqh 62137 Sources/Include/Controls/WndObj.mqh 62514 Sources/Include/Controls/Panel.mqh 72881 Sources/Include/Controls/Scrolls.mqh 78251 Sources/Include/Controls\WndClient.mqh 103907 Sources/Include/Layouts/Box.mqh 115349 Sources/Include/Layouts/Grid.mqh 126741 Sources/Include/Layouts\GridTk.mqh 131057 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh 136066 Sources/Include/Controls\Edit.mqh 136126 Sources/Include/ChartObjects\ChartObjectsTxtControls.mqh 136555 Sources/Include/ChartObjects/ChartObject.mqh 137079 Sources/Include/ChartObjects\ChartObjectsTxtControls.mqh 177423 Sources/Include/Controls\Edit.mqh 213551 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mqh 221772 Sources/Experts/Examples/Layouts/SlidingPuzzle2.mq5 241539 Lines: 6102 Tokens: 27248 Defining grammar... Parsing... CRect :: CPoint LeftTop ( void ) const CRect :: void LeftTop ( const int x , const int y ) CRect :: void LeftTop ( const CPoint & point ) ... CSlidingPuzzleDialog :: virtual bool Create ( const long chart , const string name , const int subwin , const int x1 , const int y1 , const int x2 , const int y2 ) CSlidingPuzzleDialog :: virtual bool OnEvent ( const int id , const long & lparam , const double & dparam , const string & sparam ) CSlidingPuzzleDialog :: void Difficulty ( int d ) CSlidingPuzzleDialog :: virtual bool CreateMain ( const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool CreateButton ( const int button_id , const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool CreateButtonNew ( const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool CreateLabel ( const long chart , const string name , const int subwin ) CSlidingPuzzleDialog :: virtual bool IsMovable ( CButton * button ) CSlidingPuzzleDialog :: virtual bool HasNorth ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual bool HasSouth ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual bool HasEast ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual bool HasWest ( CButton * button , int id , bool shuffle = false ) CSlidingPuzzleDialog :: virtual void Swap ( CButton * source ) Success Class hierarchy: CPoint CSize CRect CObject ^ +--CWnd | ^ | +--CDragWnd | +--CWndContainer | | ^ | | +--CScroll | | | ^ | | | +--CScrollV | | | +--CScrollH | | +--CWndClient | | ^ | | +--CBox | | ^ | | +--CGrid | | ^ | | +--CGridTk | +--CWndObj | ^ | +--CPanel | +--CEdit +--CGridConstraints +--CChartObject ^ +--CChartObjectText ^ +--CChartObjectLabel ^ +--CChartObjectEdit | ^ | +--CChartObjectButton +--CChartObjectRectLabel CAppDialog ^ +--CSlidingPuzzleDialog
Здесь иерархия классов — более интересная.
Несмотря на то, что я протестировал парсер на разных проектах, он абсолютно точно будет "спотыкаться" на некоторых программах. Одна из проблем, которая в нем не решена, связана с обработкой макросов. Как уже было сказано ранее, корректный анализ предполагает динамическую интерпретацию и раскрытие макросов с подстановкой результатов в исходный код еще до начала парсинга.
В текущей грамматике MQL сделана попытка обозначить вызов макросов как менее строгий вызов функций, но это работает далеко не всегда.
Например, в библиотеке TypeToBytes параметры макросов используются для генерации мета-типов. Вот один из случаев:
#define _C(A, B) CASTING<A>::Casting(B)
Далее этот макрос используется следующим образом:
Res = _C(STRUCT_TYPE<T1>, Tmp);
Если попробовать запустить парсер на данном коде, он не сможет "переварить" STRUCT_TYPE<T1>, поскольку в реальности этот параметр представляет собой шаблонизированный тип, а парсер подразумевает значение, или в более широком смысле — выражение (и, в частности, трактует символы '<', '>' как операции сравнения). Похожую проблему сейчас будут создавать вызовы макросов, после которых не стоит точка с запятой. Но её можно обойти, вставив ';' в обрабатываемый исходный код.
Желающие могут провести эксперимент номер 3 (первые два упоминались в начале статьи), заключающийся в поиске обходного маневра для модификации текущей грамматики такими правилами макросов, которые позволили бы успешно парсить подобные сложные случаи.Заключение
Мы рассмотрели самый простой, технологичный способ синтаксического анализа данных, включая и анализ исходных кодов на MQL. Для этого была представлена грамматика языка MQL и реализация стандартных инструментов — сканера и парсера. Получение с помощью них структуры исходных кодов позволяет рассчитывать их статистику, определять показатели качества, строить зависимости, автоматически менять форматирование.
Вместе с тем, представленная реализация требует ряда усовершенствований для достижения 100%-совместимости со сложными проектами MQL, в частности, в плане поддержки раскрытия макросов.
При более глубокой подготовке — сохранении информации о найденных сущностях в таблице имен — данный подход позволит также проводить кодогенерацию, контроль типичных ошибок, и выполнять другие более сложные задачи.
![Библиотека для простого и быстрого создания программ для MetaTrader (Часть I): Концепция, организация данных, первые результаты](https://c.mql5.com/2/35/MQL5-avatar-doeasy.png)
![ZigZag всему голова (Часть II): Примеры получения, обработки и отображения данных](https://c.mql5.com/2/35/MQL5-avatar-zigzag_head__1.png)
![Исследование методов свечного анализа (Часть II): Автопоиск новых паттернов](https://c.mql5.com/2/35/Pattern_I__3.png)
![Создание графических интерфейсов для экспертов и индикаторов на базе .Net Framework и C#](https://c.mql5.com/2/35/icon__3.png)
![MQL5 - Язык торговых стратегий для клиентского терминала MetaTrader 5](https://c.mql5.com/i/registerlandings/logo-2.png)
- Бесплатные приложения для трейдинга
- 8 000+ сигналов для копирования
- Экономические новости для анализа финансовых рынков
Вы принимаете политику сайта и условия использования
Наверное, с помощью данного метода возможно написание конвертера mq4->mq5 для Маркета:
Выкладываю обновленные исходники.
Обеспечена компилируемость в последних билдах.
Исправлено несколько трудноуловимых ошибок.
Выкладываю обновленные исходники.