Добро пожаловать в Главу 2 учебника «Создание языка программирования с LLVM». В этой главе мы увидим, как использовать лексический анализатор, созданный в Главе 1, чтобы построить полный синтаксический анализатор для нашего языка Kaleidoscope. После того, как у нас будет готов парсер, мы будем строить Abstract Syntax Tree (AST) (Абстрактное синтаксическое дерево).
Парсер для языка Калейдоскоп мы будем разрабатывать, используя сочетание разбора рекурсивным спуском и разбора первенства операторов (последнее для бинарных выражений и первое для всего остального). Прежде чем мы перейдем к самому парсингу, поговорим о том, что получим на выходе: Abstract Syntax Tree.
AST отображает программу таким образом, что для более поздних стадий компилятора (например, генерации кода) она легко интерпретируется. Нам нужен один объект для каждой конструкции языка. В Kaleidoscope у нас есть выражения, прототипы и функции. Начнём с выражений:
В вышеприведённом коде показано определение базового класса ExprAST и его подкласс, который мы используем для числовых литералов.
Сейчас мы создадим только AST без различных полезных методов работы с ним. Если понадобится, то можно, например, довольно легко добавить виртуальный метод форматированного вывода кода. Вот определения узлов для других выражений AST, которые мы будем использовать в Kaleidoscope:
Всё просто: переменная содержит имя переменной, бинарный оператор содержит свой опкод (например, '+') и левое и правое выражения (узлы AST), а вызовы функций содержат имя функции и список всех аргументов. Одна из замечательных вещей в AST — это то, что он охватывает языковые особенности вне зависимости от синтаксиса языка программирования. Обратите внимание, что нет никаких спорных моментов о приоритете бинарных операторов, лексической структуре и т.д.
Мы определили все узлы для выражений нашего языка. Он не является тьюринг-полным, так как не имеет условного потока управления, мы исправим это в следующей части. Следующие две вещи, которые нам необходимы — это интерфейс функций и сами функции:
В Kaleidoscope функции типизированы только количеством своих аргументов. Так как все значения — это действительные числа двойной точности, то тип каждого аргумента нет смысла нигде хранить. В реальном языке программирования класс «ExprAST», вероятно, содержал бы ещё поле с типом.
Теперь мы, наконец, можем поговорить о разборе выражений и функций в Kaleidoscope.
Теперь, когда у нас есть элементы AST, нам необходимо определить синтаксический анализатор кода, чтобы его построить. Идея здесь в том, что мы хотим разобрать что-то вроде «x + y» (которое возвращается в виде трёх токенов при лексическом разборе) в AST, который может быть сгенерирован чем-то вроде этого:
Прежде чем сделать это, мы определим несколько вспомогательных процедуры:
Этот код реализует простейший буфер токенов поверх лексического анализатора. Это позволяет нам смотреть вперёд на один токен, который будет возвращён лексическим анализатором. Каждая функция в нашем парсере будет считать, что CurTok является текущим токеном для разбора.
Это вспомогательные процедуры, которые наш парсер будет использовать для обработки ошибок. Исправление ошибок в нашем парсере будет далеко не лучшим и не особо удобным для пользователя, но будет достаточным в рамках этого учебника.
С этими вспомогательными функциями мы можем реализовать первую часть нашей грамматики: числовые литералы.
Начнем с числовых литералов, так как с ними проще всего. Для каждого правила грамматики мы определим функцию, которая анализирует это правило. Для числовых литералов имеем:
Функция очень проста: при вызове она ожидает, что текущий токен — это tok_number. Она создает узел NumberExprAST, передавая ему значение текущего числа, перемещает лексический анализатор к следующему токену и возвращает созданный узел.
Здесь есть несколько интересных аспектов. Наиболее важным является то, что эта функция получает любые токены, которые соответствуют правилу нашей грамматики и возвращает буфер лексического анализатора со следующим токеном (который не является частью правила грамматики), готовым к обработке. Это стандартный путь для парсинга рекурсивным спуском. Чтобы лучше разобраться в этом, рассмотрим парсинг выражения в скобках:
Эта функция иллюстрирует ряд интересных вещей о синтаксическом анализаторе:
Эта функция работает так же, как и предыдущие. (При вызове ожидает, что текущий токен — это tok_identifier). Она также использует рекурсию и обработку ошибок. Один интересный момент состоит в том, что ей приходится заглядывать вперёд, чтобы определить, является текущий идентификатор ссылкой на переменную или вызовом функции. Это проверка в зависимости от того, является ли следующий за идентификатором токен знаком '(', вызывает либо VariableExprAST, либо CallExprAST.
Теперь, когда у нас есть вся логика для разбора простейших выражений, мы можем определить вспомогательную функцию, чтобы обернуть ей в одну точку входа. Мы назовём этот класс выражения «primary» (первичным) по причинам, которые станут более ясными к концу учебника. Для разбора произвольного первичного выражения, мы должны определить, что это за выражение:
Теперь, когда мы видим определение этой функции, становится более очевидно, почему мы можем предполагать какие-либо допустимые состояния CurTok в различных функциях. При этом используется заглядывание вперёд, чтобы определить, какой вид выражения нужно проверять, а затем в соответственно вызванной функции анализируется само выражение.
Теперь, когда основные выражения могут быть обработаны, мы сможем работать с бинарными выражениями. Они гораздо сложнее.
Двоичные выражения значительно труднее разобрать, потому что они часто неоднозначны. Например, для строку «x + y * z» парсер может разобрать либо как "(x + y) * z", либо как «x + (y * z)». Зная основы математики, мы ожидаем второй вариант, потому что "*" (умножение) имеет более высокий приоритет, чем "+" (сложение).
Есть много вариантов решения, но наиболее элегантным и эффективным способом является парсинг первенства (приоритета) операторов. Этот техника парсинга использует рекурсию для приоритетов операций. Для начала нам нужна таблица приоритетов:
Kaleidoscope будет поддерживать только 4 бинарных оператора (но он, очевидно, может быть расширен нашим храбрым и бесстрашным читателем). Функция GetTokPrecedence возвращает приоритет текущего токена или -1, если токен не является бинарный оператором. Наличие такой таблицы позволяет легко добавлять новые операторы и, естественно, алгоритм не зависит от конкретных операторов. Можно запросто убрать таблицу приоритетов и делать сравнения в функции GetTokPrecedence.
Теперь мы можем начать разбор бинарных выражений. Основная идея парсинга первенства операторов заключается в разбиении выражения с потенциально неоднозначными бинарными операторами на части. Рассмотрим, например, выражение «a+b+(c+d)*e*f+g». Парсер приоритета операторов рассматривает его как поток первичных выражений, разделенных бинарными операторами. Таким образом, при первичном парсинге, сначала разбирается ведущее первичное выражение «а», и он будет видеть пары [+, b] [+, (c+d)] [*, е] [*, f] и [+, g]. Обратите внимание на скобки: парсеру не нужно беспокоиться о вложенных выражениях вроде (c+d).
Для начала, выражение — это первичное выражение, потенциально сопровождаемое последовательностью пар [binop, primaryexpr]:
ParseBinOpRHS — функция, которая анализирует последовательность пар. Он принимает приоритет и указатель на выражение для анализа. Обратите внимание, что «x» является абсолютно допустимым выражением: таким образом, «binoprhs» может быть пустым, в этом случае функция возвращает выражение, которое ей было передано. В нашем примере выше, код передает в ParseBinOpRHS выражение «a» и текущий токен "+".
Значение приоритета, передаваемое в ParseBinOpRHS указывает минимальный приоритет операторов, необходимый чтобы он были приняты. Например, если текущая пара в потоке [+, х] и в ParseBinOpRHS передается приоритет 40, он не будет принимать токены (поскольку приоритет "+" только 20). Поэтому ParseBinOpRHS начинается с:
Этот код получает приоритет текущего токена и проверяет, насколько он низкий. Так как мы определили недопустимыми токены, которые имеют приоритет -1, то происходит неявная проверка, определяющая, когда поток пар заканчивается. Если эта проверка успешно пройдена, мы знаем, что токен точно является бинарным оператором и что он будет включен в выражение:
Таким образом, этот код получает (и запоминает) бинарный оператор, а затем анализирует первичное выражение, которое за ним следует. Он создает пары, первой из которых в нашем примере будет [+, b].
Теперь, когда мы разобрали левую часть выражения и одну пару из последовательности RHS, мы должны решить каким образом связывать выражение. В частности, у нас может быть как "(a+b) binop unparsed", так и «a + (b binop unparsed)» (где binop — бинарный оператор, unparsed — неразобранная часть). Чтобы определиться, мы смотрим вперед ещё на один «binop» (бинарный оператор), чтобы определить его приоритет и сравнить его с приоритетом BinOp (которым в данном случае является "+"):
Если приоритет бинарного оператора справа от «RHS» меньше или равен приоритету нашего текущего оператора, то мы знаем, что у нас случай "(a+b) binop ...". В нашем примере, текущий оператор "+" и следующий оператор "+" имеют одинаковый приоритет. Поэтому мы создадим узел AST для «a+b», а затем продолжим разбор:
В нашем примере «a+b+» будет возвращено как "(a+b)" и выполнится следующая итерация цикла, с "+" в качестве текущего токена. Эта часть будет принята и далее, насколько вы помните, должно быть разобрано "(c+d)" в качестве первичного выражения, то есть текущей парой будет [+, (c+d)]. Затем будет получено выражение с "*" в качестве бинарного оператора. В этом случае приоритет "*" выше, чем приоритет "+", так что вышеприведённая условная конструкция будет выполнена.
Важнейшим вопросом здесь для левой части будет «как в этом условии разобрать правую часть в полном объеме»? В частности, для правильного построения AST для нашего примера, он должен получить полное выражение "(c+d)*e*f" в качестве переменной выражения RHS. Код для этого удивительно прост (код из двух вышеупомянутых блоков дублируется для контекста):
На данный момент мы знаем, что бинарный оператор в правой части нашего первичного выражения имеет более высокий приоритет, чем бинарный оператор, разбираемый в данный момент. Таким образом, мы знаем, что любые последовательности пар операторов, имеющих более высокий приоритет, чем "+", должны быть разобраны вместе и возвращается как «RHS». Для этого мы рекурсивно вызываем функцию ParseBinOpRHS с параметром «TokPrec+1» в качестве минимального приоритета, необходимого для продолжения. В нашем многострадальном примере это будет причиной возврата узла AST для "(c+d)*e*f" как RHS, который затем становится правой частью для выражения с '+'.
Наконец, на следующей итерации цикла while, часть "+g" анализируется и добавляется в AST. С помощью этого небольшого фрагмента кода (14 строк), мы корректно обрабатываем любые бинарные выражения элегантным методом разбора. Это был лишь беглый обзор кода, поэтому я рекомендую вам попробовать его позапускать с несколькими примерами, чтобы посмотреть, как он работает.
На этом завершаем обработку выражений. На данный момент мы уже можем указать анализатору произвольного поток токенов и построить из него выражение, останавливаясь на первом токене, который не является частью выражения. Теперь нам нужно разобраться с объявлением функций и т.д.
Следующее, чего у нас не хватает, так это обработки прототипов функций. В Kaleidoscope, они используются как для объявления «внешних» (extern) функций, так и для объявления тела функций. Код для этой части парсинга будет прямолинейным и не очень-то интересным (после того, как вы пережили разбора выражений):
Учитывая простоту объявления функции, тело функции будет содержать в себе прототип + выражение:
Кроме того нужна поддержка «extern» для объявления функций вроде «sin» и «cos», а также для поддержки преждевременного объявления пользовательских функций. 'extern' будет состоять только из прототипа без тела:
Наконец, нам нужно позволить пользователю вводить произвольные выражения верхнего уровня и вычислять их «на лету». Мы будем их обрабатывать, определяя для них анонимные нульарные (без аргументов) функции:
Теперь, когда у нас есть все части, давайте создадим маленькую управляющую программу, которая позволит опробовать нам весь код, который мы написали!
Управляющая программа просто вызывает парсинг циклически. Здесь нет ничего интересного, поcмотрите ниже в полном коде секцию «Парсинг верхнего уровня».
Наиболее интересная частью в этом коде является то, что мы игнорируем верхнеуровневые точки с запятой. Вы спрашиваете почему? Основная причина в том, что если вы введете «4 + 5» в командной строке, парсер не знает, что это конец, будете ли вы продолжать вводить текст. Например, на следующей строке можно ввести «def foo ...», в этом случае 4 +5 — это окончание выражения верхнего уровня, или вы могли бы ввести "* 6", продолжая выражение. Наличие точек с запятой верхнего уровня позволяет напечатать «4+5;» и парсер будет знать, что вы имели ввиду.
С помощью всего лишь 400 строк комментированного кода (240 строк без комментариев и пустых строк), мы полностью определили наш минималистичный язык программирования, включающий лексический и синтаксический анализаторы и построение AST. С помощью всего этого Kaleidoscope при выполнении проверит код и сообщит нам, если он грамматически неверен. Вот пример интерактивной сессии:
Здесь есть много способов для улучшения. Вы можете определить новые узлы AST, расширить язык многими способами, и т.д. В следующей части мы рассмотрим, какиз AST генерировать LLVM Intermediate Representation (IR) (Промежуточное представление).
Здесь представлен полный листинг кода для этой и предыдущей главы. Отметим, что код полностью автономен: вам не нужен LLVM или какие-либо внешние библиотеки. (Кроме, конечно же, стандартных библиотек C и C++). Собрать этот код можно так:
Ну, и сам код:
P.S.
Перевод этой главы дался очень сложно, так что прошу прощения за не очень качественный перевод и немного «нерусские обороты», обещаю исправиться в следующей главе (она полегче). Как и всегда, с удовольствием принимаю в личку исправления, уточнения, пожелания и угрозы :)
Парсер для языка Калейдоскоп мы будем разрабатывать, используя сочетание разбора рекурсивным спуском и разбора первенства операторов (последнее для бинарных выражений и первое для всего остального). Прежде чем мы перейдем к самому парсингу, поговорим о том, что получим на выходе: Abstract Syntax Tree.
Абстрактное синтаксическое дерево (AST)
AST отображает программу таким образом, что для более поздних стадий компилятора (например, генерации кода) она легко интерпретируется. Нам нужен один объект для каждой конструкции языка. В Kaleidoscope у нас есть выражения, прототипы и функции. Начнём с выражений:
/// ExprAST - Базовый класс для всех узлов выражений. class ExprAST { public: virtual ~ExprAST() {} }; /// NumberExprAST - Класс узла выражения для числовых литералов (Например, "1.0"). class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {} };
В вышеприведённом коде показано определение базового класса ExprAST и его подкласс, который мы используем для числовых литералов.
Сейчас мы создадим только AST без различных полезных методов работы с ним. Если понадобится, то можно, например, довольно легко добавить виртуальный метод форматированного вывода кода. Вот определения узлов для других выражений AST, которые мы будем использовать в Kaleidoscope:
/// VariableExprAST - Класс узла выражения для переменных (например, "a"). class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST - Класс узла выражения для бинарных операторов. class BinaryExprAST : public ExprAST { char Op; ExprAST *LHS, *RHS; public: BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) : Op(op), LHS(lhs), RHS(rhs) {} }; /// CallExprAST - Класс узла выражения для вызова функции. class CallExprAST : public ExprAST { std::string Callee; std::vector<ExprAST*> Args; public: CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) : Callee(callee), Args(args) {} };
Всё просто: переменная содержит имя переменной, бинарный оператор содержит свой опкод (например, '+') и левое и правое выражения (узлы AST), а вызовы функций содержат имя функции и список всех аргументов. Одна из замечательных вещей в AST — это то, что он охватывает языковые особенности вне зависимости от синтаксиса языка программирования. Обратите внимание, что нет никаких спорных моментов о приоритете бинарных операторов, лексической структуре и т.д.
Мы определили все узлы для выражений нашего языка. Он не является тьюринг-полным, так как не имеет условного потока управления, мы исправим это в следующей части. Следующие две вещи, которые нам необходимы — это интерфейс функций и сами функции:
/// PrototypeAST - Этот класс представляет "прототип" для функции, /// который хранит её имя и имена аргументов (и, таким образом, /// неявно хранится число аргументов). class PrototypeAST { std::string Name; std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} }; /// FunctionAST - Представляет определение самой функции class FunctionAST { PrototypeAST *Proto; ExprAST *Body; public: FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {} };
В Kaleidoscope функции типизированы только количеством своих аргументов. Так как все значения — это действительные числа двойной точности, то тип каждого аргумента нет смысла нигде хранить. В реальном языке программирования класс «ExprAST», вероятно, содержал бы ещё поле с типом.
Теперь мы, наконец, можем поговорить о разборе выражений и функций в Kaleidoscope.
Основа парсера
Теперь, когда у нас есть элементы AST, нам необходимо определить синтаксический анализатор кода, чтобы его построить. Идея здесь в том, что мы хотим разобрать что-то вроде «x + y» (которое возвращается в виде трёх токенов при лексическом разборе) в AST, который может быть сгенерирован чем-то вроде этого:
ExprAST *X = new VariableExprAST("x"); ExprAST *Y = new VariableExprAST("y"); ExprAST *Result = new BinaryExprAST('+', X, Y);
Прежде чем сделать это, мы определим несколько вспомогательных процедуры:
/// CurTok/getNextToken - Предоставляет простой буфер токенов. CurTok - это текущий /// токен, просматриваемый парсером. getNextToken получает следующий токен от /// лексического анализатора и обновляет CurTok. static int CurTok; static int getNextToken() { return CurTok = gettok(); }
Этот код реализует простейший буфер токенов поверх лексического анализатора. Это позволяет нам смотреть вперёд на один токен, который будет возвращён лексическим анализатором. Каждая функция в нашем парсере будет считать, что CurTok является текущим токеном для разбора.
/// Error* - Это небольшие вспомогательные функции для обработки ошибок. ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
Это вспомогательные процедуры, которые наш парсер будет использовать для обработки ошибок. Исправление ошибок в нашем парсере будет далеко не лучшим и не особо удобным для пользователя, но будет достаточным в рамках этого учебника.
С этими вспомогательными функциями мы можем реализовать первую часть нашей грамматики: числовые литералы.
Парсинг выражений
Начнем с числовых литералов, так как с ними проще всего. Для каждого правила грамматики мы определим функцию, которая анализирует это правило. Для числовых литералов имеем:
/// numberexpr ::= number static ExprAST *ParseNumberExpr() { ExprAST *Result = new NumberExprAST(NumVal); getNextToken(); // получаем число return Result; }
Функция очень проста: при вызове она ожидает, что текущий токен — это tok_number. Она создает узел NumberExprAST, передавая ему значение текущего числа, перемещает лексический анализатор к следующему токену и возвращает созданный узел.
Здесь есть несколько интересных аспектов. Наиболее важным является то, что эта функция получает любые токены, которые соответствуют правилу нашей грамматики и возвращает буфер лексического анализатора со следующим токеном (который не является частью правила грамматики), готовым к обработке. Это стандартный путь для парсинга рекурсивным спуском. Чтобы лучше разобраться в этом, рассмотрим парсинг выражения в скобках:
/// parenexpr ::= '(' expression ')' static ExprAST *ParseParenExpr() { getNextToken(); // получаем (. ExprAST *V = ParseExpression(); if (!V) return 0; if (CurTok != ')') return Error("expected ')'"); getNextToken(); // получаем ). return V; }
Эта функция иллюстрирует ряд интересных вещей о синтаксическом анализаторе:
- Она показывает, как использовать процедуры ошибок. При вызове функция ожидает, что текущий токен — это знак '(', но после разбора подвыражения, вполне возможно, что нет ожидаемого ')'. Например, если пользователь вводит в "(4 х" вместо "(4)", то анализатор должен показать ошибку. Поскольку подобные ошибки могут возникать, синтаксическому анализатору нужен способ указать, что они произошли: в нашем парсере в случае ошибки мы возвращаемся null.
- Другой интересным аспект этой функции является использование рекурсии при вызове ParseExpression (мы вскоре увидим, что ParseExpression может вызвать ParseParenExpr). Это мощный механизм, поскольку он позволяет нам обрабатывать рекурсивные грамматики и очень просто справляться с любыми правилами таких грамматик. Обратите внимание, что для скобок не строятся узлы AST. Важная роль скобок — обеспечить синтаксическому анализатору возможность группировки. Когда парсер строит AST, скобки больше не нужны.
/// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' static ExprAST *ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); // получаем идентификатор. if (CurTok != '(') // Ссылка на переменную. return new VariableExprAST(IdName); // Вызов функции. getNextToken(); // получаем ( std::vector<ExprAST*> Args; if (CurTok != ')') { while (1) { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); if (CurTok == ')') break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); } } // получаем ')'. getNextToken(); return new CallExprAST(IdName, Args); }
Эта функция работает так же, как и предыдущие. (При вызове ожидает, что текущий токен — это tok_identifier). Она также использует рекурсию и обработку ошибок. Один интересный момент состоит в том, что ей приходится заглядывать вперёд, чтобы определить, является текущий идентификатор ссылкой на переменную или вызовом функции. Это проверка в зависимости от того, является ли следующий за идентификатором токен знаком '(', вызывает либо VariableExprAST, либо CallExprAST.
Теперь, когда у нас есть вся логика для разбора простейших выражений, мы можем определить вспомогательную функцию, чтобы обернуть ей в одну точку входа. Мы назовём этот класс выражения «primary» (первичным) по причинам, которые станут более ясными к концу учебника. Для разбора произвольного первичного выражения, мы должны определить, что это за выражение:
/// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr static ExprAST *ParsePrimary() { switch (CurTok) { default: return Error("unknown token when expecting an expression"); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); } }
Теперь, когда мы видим определение этой функции, становится более очевидно, почему мы можем предполагать какие-либо допустимые состояния CurTok в различных функциях. При этом используется заглядывание вперёд, чтобы определить, какой вид выражения нужно проверять, а затем в соответственно вызванной функции анализируется само выражение.
Теперь, когда основные выражения могут быть обработаны, мы сможем работать с бинарными выражениями. Они гораздо сложнее.
Парсинг бинарных выражений
Двоичные выражения значительно труднее разобрать, потому что они часто неоднозначны. Например, для строку «x + y * z» парсер может разобрать либо как "(x + y) * z", либо как «x + (y * z)». Зная основы математики, мы ожидаем второй вариант, потому что "*" (умножение) имеет более высокий приоритет, чем "+" (сложение).
Есть много вариантов решения, но наиболее элегантным и эффективным способом является парсинг первенства (приоритета) операторов. Этот техника парсинга использует рекурсию для приоритетов операций. Для начала нам нужна таблица приоритетов:
/// BinopPrecedence - Содержит приоритеты для бинарных операторов static std::map<char, int> BinopPrecedence; /// GetTokPrecedence - Возвращает приоритет текущего бинарного оператора. static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; // Удостоверимся, что это объявленный бинарный оператор. int TokPrec = BinopPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; } int main() { // Задаём стандартные бинарные операторы // 1 - наименьший приоритет. BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; // высший приоритет. ... }
Kaleidoscope будет поддерживать только 4 бинарных оператора (но он, очевидно, может быть расширен нашим храбрым и бесстрашным читателем). Функция GetTokPrecedence возвращает приоритет текущего токена или -1, если токен не является бинарный оператором. Наличие такой таблицы позволяет легко добавлять новые операторы и, естественно, алгоритм не зависит от конкретных операторов. Можно запросто убрать таблицу приоритетов и делать сравнения в функции GetTokPrecedence.
Теперь мы можем начать разбор бинарных выражений. Основная идея парсинга первенства операторов заключается в разбиении выражения с потенциально неоднозначными бинарными операторами на части. Рассмотрим, например, выражение «a+b+(c+d)*e*f+g». Парсер приоритета операторов рассматривает его как поток первичных выражений, разделенных бинарными операторами. Таким образом, при первичном парсинге, сначала разбирается ведущее первичное выражение «а», и он будет видеть пары [+, b] [+, (c+d)] [*, е] [*, f] и [+, g]. Обратите внимание на скобки: парсеру не нужно беспокоиться о вложенных выражениях вроде (c+d).
Для начала, выражение — это первичное выражение, потенциально сопровождаемое последовательностью пар [binop, primaryexpr]:
/// expression /// ::= primary binoprhs /// static ExprAST *ParseExpression() { ExprAST *LHS = ParsePrimary(); if (!LHS) return 0; return ParseBinOpRHS(0, LHS); }
ParseBinOpRHS — функция, которая анализирует последовательность пар. Он принимает приоритет и указатель на выражение для анализа. Обратите внимание, что «x» является абсолютно допустимым выражением: таким образом, «binoprhs» может быть пустым, в этом случае функция возвращает выражение, которое ей было передано. В нашем примере выше, код передает в ParseBinOpRHS выражение «a» и текущий токен "+".
Значение приоритета, передаваемое в ParseBinOpRHS указывает минимальный приоритет операторов, необходимый чтобы он были приняты. Например, если текущая пара в потоке [+, х] и в ParseBinOpRHS передается приоритет 40, он не будет принимать токены (поскольку приоритет "+" только 20). Поэтому ParseBinOpRHS начинается с:
/// binoprhs /// ::= ('+' primary)* static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { // Если это бинарный оператор, получаем его приоритет while (1) { int TokPrec = GetTokPrecedence(); // Если этот бинарный оператор связывает выражения по крайней мере так же, // как текущий, то используем его if (TokPrec < ExprPrec) return LHS;
Этот код получает приоритет текущего токена и проверяет, насколько он низкий. Так как мы определили недопустимыми токены, которые имеют приоритет -1, то происходит неявная проверка, определяющая, когда поток пар заканчивается. Если эта проверка успешно пройдена, мы знаем, что токен точно является бинарным оператором и что он будет включен в выражение:
// Отлично, мы знаем, что это бинарный оператор. int BinOp = CurTok; getNextToken(); // получить бинарный оператор // Разобрать первичное выражение после бинарного оператора ExprAST *RHS = ParsePrimary(); if (!RHS) return 0;
Таким образом, этот код получает (и запоминает) бинарный оператор, а затем анализирует первичное выражение, которое за ним следует. Он создает пары, первой из которых в нашем примере будет [+, b].
Теперь, когда мы разобрали левую часть выражения и одну пару из последовательности RHS, мы должны решить каким образом связывать выражение. В частности, у нас может быть как "(a+b) binop unparsed", так и «a + (b binop unparsed)» (где binop — бинарный оператор, unparsed — неразобранная часть). Чтобы определиться, мы смотрим вперед ещё на один «binop» (бинарный оператор), чтобы определить его приоритет и сравнить его с приоритетом BinOp (которым в данном случае является "+"):
// Если BinOp связан с RHS меньшим приоритетом, чем оператор после RHS, // то берём часть вместе с RHS как LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) {
Если приоритет бинарного оператора справа от «RHS» меньше или равен приоритету нашего текущего оператора, то мы знаем, что у нас случай "(a+b) binop ...". В нашем примере, текущий оператор "+" и следующий оператор "+" имеют одинаковый приоритет. Поэтому мы создадим узел AST для «a+b», а затем продолжим разбор:
... Тело условия пока опущено ... } // Собираем LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } }
В нашем примере «a+b+» будет возвращено как "(a+b)" и выполнится следующая итерация цикла, с "+" в качестве текущего токена. Эта часть будет принята и далее, насколько вы помните, должно быть разобрано "(c+d)" в качестве первичного выражения, то есть текущей парой будет [+, (c+d)]. Затем будет получено выражение с "*" в качестве бинарного оператора. В этом случае приоритет "*" выше, чем приоритет "+", так что вышеприведённая условная конструкция будет выполнена.
Важнейшим вопросом здесь для левой части будет «как в этом условии разобрать правую часть в полном объеме»? В частности, для правильного построения AST для нашего примера, он должен получить полное выражение "(c+d)*e*f" в качестве переменной выражения RHS. Код для этого удивительно прост (код из двух вышеупомянутых блоков дублируется для контекста):
// Если BinOp связан с RHS меньшим приоритетом, чем оператор после RHS, // то берём часть вместе с RHS как LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) {RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0;} // Собираем LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } }
На данный момент мы знаем, что бинарный оператор в правой части нашего первичного выражения имеет более высокий приоритет, чем бинарный оператор, разбираемый в данный момент. Таким образом, мы знаем, что любые последовательности пар операторов, имеющих более высокий приоритет, чем "+", должны быть разобраны вместе и возвращается как «RHS». Для этого мы рекурсивно вызываем функцию ParseBinOpRHS с параметром «TokPrec+1» в качестве минимального приоритета, необходимого для продолжения. В нашем многострадальном примере это будет причиной возврата узла AST для "(c+d)*e*f" как RHS, который затем становится правой частью для выражения с '+'.
Наконец, на следующей итерации цикла while, часть "+g" анализируется и добавляется в AST. С помощью этого небольшого фрагмента кода (14 строк), мы корректно обрабатываем любые бинарные выражения элегантным методом разбора. Это был лишь беглый обзор кода, поэтому я рекомендую вам попробовать его позапускать с несколькими примерами, чтобы посмотреть, как он работает.
На этом завершаем обработку выражений. На данный момент мы уже можем указать анализатору произвольного поток токенов и построить из него выражение, останавливаясь на первом токене, который не является частью выражения. Теперь нам нужно разобраться с объявлением функций и т.д.
Парсинг всего остального
Следующее, чего у нас не хватает, так это обработки прототипов функций. В Kaleidoscope, они используются как для объявления «внешних» (extern) функций, так и для объявления тела функций. Код для этой части парсинга будет прямолинейным и не очень-то интересным (после того, как вы пережили разбора выражений):
/// prototype /// ::= id '(' id* ')' static PrototypeAST *ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; getNextToken(); if (CurTok != '(') return ErrorP("Expected '(' in prototype"); // Считываем список наименований аргументов. std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); // Все отлично. getNextToken(); // получаем ')'. return new PrototypeAST(FnName, ArgNames); }
Учитывая простоту объявления функции, тело функции будет содержать в себе прототип + выражение:
/// definition ::= 'def' prototype expression static FunctionAST *ParseDefinition() { getNextToken(); // получаем def. PrototypeAST *Proto = ParsePrototype(); if (Proto == 0) return 0; if (ExprAST *E = ParseExpression()) return new FunctionAST(Proto, E); return 0; }
Кроме того нужна поддержка «extern» для объявления функций вроде «sin» и «cos», а также для поддержки преждевременного объявления пользовательских функций. 'extern' будет состоять только из прототипа без тела:
/// external ::= 'extern' prototype static PrototypeAST *ParseExtern() { getNextToken(); // получаем extern. return ParsePrototype(); }
Наконец, нам нужно позволить пользователю вводить произвольные выражения верхнего уровня и вычислять их «на лету». Мы будем их обрабатывать, определяя для них анонимные нульарные (без аргументов) функции:
/// toplevelexpr ::= expression static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { // Создаём анонимный прототип. PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; }
Теперь, когда у нас есть все части, давайте создадим маленькую управляющую программу, которая позволит опробовать нам весь код, который мы написали!
Управляющая программа
Управляющая программа просто вызывает парсинг циклически. Здесь нет ничего интересного, поcмотрите ниже в полном коде секцию «Парсинг верхнего уровня».
/// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; case ';': getNextToken(); break; // игнорируем ';' верхнего уровня. case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } }
Наиболее интересная частью в этом коде является то, что мы игнорируем верхнеуровневые точки с запятой. Вы спрашиваете почему? Основная причина в том, что если вы введете «4 + 5» в командной строке, парсер не знает, что это конец, будете ли вы продолжать вводить текст. Например, на следующей строке можно ввести «def foo ...», в этом случае 4 +5 — это окончание выражения верхнего уровня, или вы могли бы ввести "* 6", продолжая выражение. Наличие точек с запятой верхнего уровня позволяет напечатать «4+5;» и парсер будет знать, что вы имели ввиду.
Выводы
С помощью всего лишь 400 строк комментированного кода (240 строк без комментариев и пустых строк), мы полностью определили наш минималистичный язык программирования, включающий лексический и синтаксический анализаторы и построение AST. С помощью всего этого Kaleidoscope при выполнении проверит код и сообщит нам, если он грамматически неверен. Вот пример интерактивной сессии:
$ ./a.out
ready> def foo(x y) x+foo(y, 4.0);
Parsed a function definition.
ready> def foo(x y) x+y y;
Parsed a function definition.
Parsed a top-level expr
ready> def foo(x y) x+y );
Parsed a function definition.
Error: unknown token when expecting an expression
ready> extern sin(a);
ready> Parsed an extern
ready> ^D
$
Здесь есть много способов для улучшения. Вы можете определить новые узлы AST, расширить язык многими способами, и т.д. В следующей части мы рассмотрим, какиз AST генерировать LLVM Intermediate Representation (IR) (Промежуточное представление).
Полный листинг кода
Здесь представлен полный листинг кода для этой и предыдущей главы. Отметим, что код полностью автономен: вам не нужен LLVM или какие-либо внешние библиотеки. (Кроме, конечно же, стандартных библиотек C и C++). Собрать этот код можно так:
# Компиляция
g++ -g -O3 toy.cpp
# Запуск
./a.out
Ну, и сам код:
#include <cstdio> #include <cstdlib> #include <string> #include <map> #include <vector> //===----------------------------------------------------------------------===// // Lexer (Лексический анализатор) //===----------------------------------------------------------------------===// // Лексический анализатор возвращает токены [0-255], если это неизвестны, // иначе одну из известных единиц кода enum Token { tok_eof = -1, // команды (ключевые слова) tok_def = -2, tok_extern = -3, // операнды (первичные выражения: идентификаторы, числа) tok_identifier = -4, tok_number = -5 }; static std::string IdentifierStr; // Заполняется, если tok_identifier static double NumVal; // Заполняется, если tok_number /// gettok - Возвращает следующий токен из стандартного потока ввода. static int gettok() { static int LastChar = ' '; // Пропускаем пробелы. while (isspace(LastChar)) LastChar = getchar(); if (isalpha(LastChar)) { // идентификатор: [a-zA-Z][a-zA-Z0-9]* IdentifierStr = LastChar; while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; if (IdentifierStr == "def") return tok_def; if (IdentifierStr == "extern") return tok_extern; return tok_identifier; } if (isdigit(LastChar) || LastChar == '.') { // Число: [0-9.]+ std::string NumStr; do { NumStr += LastChar; LastChar = getchar(); } while (isdigit(LastChar) || LastChar == '.'); NumVal = strtod(NumStr.c_str(), 0); return tok_number; } if (LastChar == '#') { // Комментарий до конца строки do LastChar = getchar(); while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) return gettok(); } // Проверка конца файла. if (LastChar == EOF) return tok_eof; // В противном случае просто возвращаем символ как значение ASCII int ThisChar = LastChar; LastChar = getchar(); return ThisChar; } //===----------------------------------------------------------------------===// // Abstract Syntax Tree (Абстрактное Синтаксическое Дерево или Дерево Парсинга) //===----------------------------------------------------------------------===// /// ExprAST - Базовый класс для всех узлов выражений. class ExprAST { public: virtual ~ExprAST() {} }; /// NumberExprAST - Класс узла выражения для числовых литералов (Например, "1.0"). class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {} }; /// VariableExprAST - Класс узла выражения для переменных (например, "a"). class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST - Класс узла выражения для бинарных операторов. class BinaryExprAST : public ExprAST { char Op; ExprAST *LHS, *RHS; public: BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) : Op(op), LHS(lhs), RHS(rhs) {} }; /// CallExprAST - Класс узла выражения для вызова функции. class CallExprAST : public ExprAST { std::string Callee; std::vector<ExprAST*> Args; public: CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) : Callee(callee), Args(args) {} }; /// PrototypeAST - Этот класс представляет "прототип" для функции, /// который хранит её имя и имена аргументов (и, таким образом, /// неявно хранится число аргументов). class PrototypeAST { std::string Name; std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} }; /// FunctionAST - Представляет определение самой функции class FunctionAST { PrototypeAST *Proto; ExprAST *Body; public: FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {} }; //===----------------------------------------------------------------------===// // Parser (Парсер или Синтаксический Анализатор) //===----------------------------------------------------------------------===// /// CurTok/getNextToken - Предоставляет простой буфер токенов. CurTok - это текущий /// токен, просматриваемый парсером. getNextToken получает следующий токен от /// лексического анализатора и обновляет CurTok. static int CurTok; static int getNextToken() { return CurTok = gettok(); } /// BinopPrecedence - Содержит приоритеты для бинарных операторов static std::map<char, int> BinopPrecedence; /// GetTokPrecedence - Возвращает приоритет текущего бинарного оператора. static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; // Удостоверимся, что это объявленный бинарный оператор. int TokPrec = BinopPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; } /// Error* - Это небольшие вспомогательные функции для обработки ошибок. ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } static ExprAST *ParseExpression(); /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' static ExprAST *ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); // получаем идентификатор. if (CurTok != '(') // Обычная переменная. return new VariableExprAST(IdName); // Вызов функции. getNextToken(); // получаем ( std::vector<ExprAST*> Args; if (CurTok != ')') { while (1) { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); if (CurTok == ')') break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); } } // Получаем ')'. getNextToken(); return new CallExprAST(IdName, Args); } /// numberexpr ::= number static ExprAST *ParseNumberExpr() { ExprAST *Result = new NumberExprAST(NumVal); getNextToken(); // получаем число return Result; } /// parenexpr ::= '(' expression ')' static ExprAST *ParseParenExpr() { getNextToken(); // получаем (. ExprAST *V = ParseExpression(); if (!V) return 0; if (CurTok != ')') return Error("expected ')'"); getNextToken(); // получаем ). return V; } /// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr static ExprAST *ParsePrimary() { switch (CurTok) { default: return Error("unknown token when expecting an expression"); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); } } /// binoprhs /// ::= ('+' primary)* static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { // Если это бинарный оператор, получаем его приоритет while (1) { int TokPrec = GetTokPrecedence(); // Если этот бинарный оператор связывает выражения по крайней мере так же, // как текущий, то используем его if (TokPrec < ExprPrec) return LHS; // Отлично, мы знаем, что это бинарный оператор. int BinOp = CurTok; getNextToken(); // eat binop // Разобрать первичное выражение после бинарного оператора ExprAST *RHS = ParsePrimary(); if (!RHS) return 0; // Если BinOp связан с RHS меньшим приоритетом, чем оператор после RHS, // то берём часть вместе с RHS как LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) { RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0; } // Собираем LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } } /// expression /// ::= primary binoprhs /// static ExprAST *ParseExpression() { ExprAST *LHS = ParsePrimary(); if (!LHS) return 0; return ParseBinOpRHS(0, LHS); } /// prototype /// ::= id '(' id* ')' static PrototypeAST *ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; getNextToken(); if (CurTok != '(') return ErrorP("Expected '(' in prototype"); // Считываем список наименований аргументов. std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); // Все отлично. getNextToken(); // получаем ')'. return new PrototypeAST(FnName, ArgNames); } /// definition ::= 'def' prototype expression static FunctionAST *ParseDefinition() { getNextToken(); // Получаем def. PrototypeAST *Proto = ParsePrototype(); if (Proto == 0) return 0; if (ExprAST *E = ParseExpression()) return new FunctionAST(Proto, E); return 0; } /// toplevelexpr ::= expression static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { // Создаём анонимный прототип. PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; } /// external ::= 'extern' prototype static PrototypeAST *ParseExtern() { getNextToken(); // получаем extern. return ParsePrototype(); } //===----------------------------------------------------------------------===// // Top-Level parsing (Парсинг верхнего уровня) //===----------------------------------------------------------------------===// static void HandleDefinition() { if (ParseDefinition()) { fprintf(stderr, "Parsed a function definition.\n"); } else { // Пропускаем токен для восстановления после ошибки. getNextToken(); } } static void HandleExtern() { if (ParseExtern()) { fprintf(stderr, "Parsed an extern\n"); } else { // Пропускаем токен для восстановления после ошибки. getNextToken(); } } static void HandleTopLevelExpression() { // Рассчитываем верхнеуровневое выражение в анонимной функции. if (ParseTopLevelExpr()) { fprintf(stderr, "Parsed a top-level expr\n"); } else { // Пропускаем токен для восстановления после ошибки. getNextToken(); } } /// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; case ';': getNextToken(); break; // игнорируем верхнеуровневые точки с запятой. case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } } //===----------------------------------------------------------------------===// // Main driver code (Код основной программы) //===----------------------------------------------------------------------===// int main() { // Задаём стандартные бинарные операторы. // 1 - наименьший приоритет. BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; // highest. fprintf(stderr, "ready> "); getNextToken(); // Теперь запускаем основной "цикл интерпретатора". MainLoop(); return 0; }
P.S.
Перевод этой главы дался очень сложно, так что прошу прощения за не очень качественный перевод и немного «нерусские обороты», обещаю исправиться в следующей главе (она полегче). Как и всегда, с удовольствием принимаю в личку исправления, уточнения, пожелания и угрозы :)