[Перевод] Нисходящий парсер с операторным предшествованием
Дуглас Крокфорд2007–02–21
ВведениеВ 1973 году на первом ежегодном симпозиуме «Принципы языков программирования» (Principles of Programming Languages Symposium) Вон Пратт представил статью «Нисходящий парсер с операторным предшествованием» (Top Down Operator Precedence). В этой статье Пратт описал метод синтаксического разбора, который объединяет лучшие стороны рекурсивного спуска и метода операторного предшествования Флойда. Метод Пратта очень похож на рекурсивный спуск, но требует меньше кода и работает гораздо быстрее. Пратт заявил, что его метод прост в освоении, реализации и использовании, необычайно эффективен и очень гибок. Благодаря своей динамичности он может использоваться для расширяемых языков.Но если метод действительно безупречен, почему же разработчики компиляторов по сей день его игнорируют? В своей статье Пратт предположил, что БНФ-грамматики и их многочисленные модификации, а также связанные с ними теоремы и автоматы заняли нишу раньше и теперь препятствуют развитию теории синтаксического анализа в других направлениях.
Есть и другое объяснение: этот метод наиболее эффективен для динамических, функциональных языков программирования и использовать его в статическом, процедурном языке куда сложнее. Свою статью Пратт иллюстрирует на примере Lisp и играючи строит синтаксические деревья по потоку лексем. Но методы синтаксического разбора не особо ценятся в сообществе Lisp-программистов, которые проповедуют спартанский отказ от синтаксиса. С момента создания Lisp предпринималось немало попыток придать этому языку богатый синтаксис в стиле ALGOL: CGOL Пратта, Lisp-2, MLISP, Dylan, Interlisp’s Clisp, оригинальные М-выражения Маккарти и так далее. Но все они провалились. Для Lisp-сообщества согласованность программ и данных оказалась важнее выразительного синтаксиса. С другой стороны, подавляющее большинство программистов любит синтаксис, поэтому сам Lisp так и не стал популярен. Методу Пратта нужен динамический язык, но сообщество динамических языков исторически не пользовалось синтаксисом, который так удобно реализуется методом Пратта.
JavaScript Ситуация изменилась с появлением JavaScript. JavaScript — динамический, функциональный язык, но синтаксически он явно принадлежит к семейству Си. Это динамический язык, и его сообщество любит синтаксис.JavaScript ещё и объектно-ориентирован. Статья Пратта предвосхищала объектно-ориентированный подход, но в ней не хватало выразительной нотации для этого. JavaScript — идеальный язык для реализации метода Пратта. Я покажу, как можно быстро и эффективно создавать синтаксические анализаторы на JavaScript.
Одной статьи недостаточно, чтобы разобраться с JavaScript полностью и, возможно, нам этого и не захочется, потому что в этом языке чёрт ногу сломит. Но в нём есть блестящие стороны, вполне достойные рассмотрения. Мы создадим парсер, который может обработать Упрощённый JavaScript. И этот парсер мы напишем на Упрощённом JavaScript. Упрощённый JavaScript — это всё лучшее из языка, в том числе:
Функции как объекты первого класса. В Упрощённом JavaScript функции являются лямбда-выражениями с лексической областью видимости. Динамические объекты с прототипным наследованием. Классов нет. Мы можем добавить новый член в объект с помощью обычного присваивания. Объект может наследовать члены другого объекта. Литералы для объектов и массивов. Для создания новых объектов и массивов эта нотация очень удобна. Литералы JavaScript послужили источником вдохновения для формата JSON. Мы воспользуемся преимуществами прототипов JavaScript, чтобы создавать объекты лексем, которые наследуются от символов. Нашей реализации потребуется метод Object.create (создаёт новый объект, наследующий члены существующего объекта) и лексический анализатор, который по входной строке создаёт массив объектов-лексем. Двигаясь по этому массиву, мы построим дерево синтаксического разбора.Таблица символов Каждая лексема, например, оператор или идентификатор, будет унаследована от символа. Мы запишем все наши возможные символы (которые определяют типы лексем языка) в объект symbol_table. var symbol_table = {}; Объект original_symbol — это прототип для всех остальных символов. Его методы обычно перегружены. Значение методов nud и led, а также силы связывания (binding power) будет объяснено ниже в разделе «Приоритеты». var original_symbol = { nud: function () { this.error («Undefined.»); }, led: function (left) { this.error («Missing operator.»); } }; Определим функцию, которая создаёт символы. Она принимает на вход идентификатор символа (id) и силу связывания (необязательный параметр bp, по умолчанию — нуль), а возвращает объект символа для данного id. Если символ уже есть в symbol_table, функция его и возвращает. Иначе она создаёт новый символ, который унаследован от original_symbol, сохраняет его в таблице символов и возвращает. Объект символа изначально содержит id, значение, левую силу связывания (lbp) и всё, что пришло из original_symbol. var symbol = function (id, bp) { var s = symbol_table[id]; bp = bp || 0; if (s) { if (bp >= s.lbp) { s.lbp = bp; } } else { s = Object.create (original_symbol); s.id = s.value = id; s.lbp = bp; symbol_table[id] = s; } return s; }; Объявим часто встречающиеся разделители и завершающие символы. symbol (»:»); symbol (»;»); symbol (»,»); symbol (»)»); symbol (»]»); symbol (»}»); symbol («else»); Символ (end) указывает на окончание потока лексем. Символ (name) — прототип для новых имён, к примеру, имён переменных. Я включил в их идентификаторы скобки, чтобы избежать возможных совпадений с пользовательскими лексемами. symbol (»(end)»); symbol (»(name)»); Лексемы Мы предполагаем, что исходный текст уже преобразован в массив tokens примитивных лексем, в которых содержится поле type («name», «string», «number», или «operator»), и поле value (строка или число). Переменная token всегда ссылается на текущую лексему. var token; Функция advance создаёт новый объект лексемы из следующей примитивной лексемы и присваивает его переменной token. Если передан необязательный параметр id, функция проверяет, что лексема имеет соответствующий идентификатор. Прототип нового объекта лексемы — это символ (name) в текущей области видимости или символ из таблицы символов. Поле arity новой лексемы будет равняться либо «name», либо «literal», либо «operator». Впоследствии, когда мы узнаем больше о роли лексемы в программе, это значение может измениться на «binary», «unary» или «statement». var advance = function (id) { var a, o, t, v; if (id && token.id!== id) { token.error («Expected '» + id + »'.»); } if (token_nr >= tokens.length) { token = symbol_table[»(end)»]; return; } t = tokens[token_nr]; token_nr += 1; v = t.value; a = t.type; if (a === «name») { o = scope.find (v); } else if (a === «operator») { o = symbol_table[v]; if (! o) { t.error («Unknown operator.»); } } else if (a === «string» || a === «number») { a = «literal»; o = symbol_table[»(literal)»]; } else { t.error («Unexpected token.»); } token = Object.create (o); token.value = v; token.arity = a; return token; }; Область видимости У большинства языков имеется нотация для определения новых символов (например, имён переменных). В простом языке, когда мы встречаем новое слово, мы автоматически определяем его и помещаем в таблицу символов. В более сложных языках имеется область видимости, которая позволяет программисту контролировать доступ к переменной и время её жизни.Область видимости (scope) — это та часть программы, в которой переменная определена и доступна. Области видимости могут быть вложенными. Переменная, определённая в некой области видимости, не видна за её пределами.
Мы будем хранить текущую область видимости в отдельной переменной scope.
var scope; Объект original_scope — это прототип для всех объектов, представляющих собой область видимости. Он содержит метод define, который позволяет определять новые переменные. Метод define преобразует лексему-имя в лексему-переменную. Он выдаёт ошибку, если переменная уже была определена в области видимости или имя является зарезервированным словом. var itself = function () { return this; };
var original_scope = { define: function (n) { var t = this.def[n.value]; if (typeof t === «object») { n.error (t.reserved? «Already reserved.» : «Already defined.»); } this.def[n.value] = n; n.reserved = false; n.nud = itself; n.led = null; n.std = null; n.lbp = 0; n.scope = scope; return n; }, Метод find используется, чтобы найти определение по имени. Он начинает поиск с текущей области видимости и идёт, если необходимо, вверх по цепочке, заканчивая таблицей символов. Если определение найти не удалось, он возвращает symbol_table[»(name)»]. Метод проверяет, что значение с данным именем не равно undefined (что означало бы обращение к необъявленному имени) и что это не функция (что указывало бы на коллизию с унаследованным методом). find: function (n) { var e = this, o; while (true) { o = e.def[n]; if (o && typeof o!== 'function') { return e.def[n]; } e = e.parent; if (! e) { o = symbol_table[n]; return o && typeof o!== 'function' ? o: symbol_table[»(name)»]; } } }, Метод pop закрывает область видимости, заменяя её родительской. pop: function () { scope = this.parent; }, Метод reserve используется, чтобы указать, что данное имя является зарезервированным словом в текущей области видимости. reserve: function (n) { if (n.arity!== «name» || n.reserved) { return; } var t = this.def[n.value]; if (t) { if (t.reserved) { return; } if (t.arity === «name») { n.error («Already defined.»); } } this.def[n.value] = n; n.reserved = true; } }; Теперь нам нужна стратегия обработки зарезервированных слов. В некоторых языках слова, описывающие структуру программы (например, if), зарезервированы и не могут быть использованы в качестве имён переменных. Гибкость нашего синтаксического анализатора позволяет достичь большего. К примеру, мы можем сказать, что в любой функции любое взятое имя может быть использовано либо как оператор языка, либо как имя переменной. Мы будем резервировать слова локально только после того, как их использовали в качестве зарезервированных. Это упрощает жизнь создателю языка, потому что добавление новых ключевых слов не сломает существующие программы, и упрощает жизнь программистам, потому что им не мешают ненужные ограничения на использование имён.Когда мы хотим создать новую область видимости для функции или блока, мы вызываем функцию new_scope, которая создаёт новый экземпляр прототипа original_scope.
var new_scope = function () { var s = scope; scope = Object.create (original_scope); scope.def = {}; scope.parent = s; return scope; }; Приоритет Объекты лексем содержат методы, которые позволяют принимать решения о приоритетах, подбирать другие лексемы и строить деревья (а в более сложных проектах ещё и проверять типы, оптимизировать и генерировать код). Основная задача приоритетов следующая: для заданного операнда между двумя операторами определить, относится операнд к левому оператору или к правому: d A e B f
Если A и B — операторы, к какому из них относится операнд e? Другими словами, мы должны выбрать между (d A e) B fи d A (e B f).
В конечном счёте основная сложность синтаксического разбора заключается в разрешении этой неопределённости. Объекты лексем из нашего метода хранят силу связывания (или уровень приоритета), и простые методы nud (null denotation, нуль-соответствие) и led (left denotation, левое соответствие). Методу nud неважно, какие лексемы стоят левее, а методу led — важно. Метод nud используется значениями (переменными и литералами) и префиксными операторами. Метод led используется инфиксными и постфиксными операторами. У лексемы могут быть определены оба метода nud и led. Например, минус (-) может быть как префиксным (смена знака числа), так и инфиксным (вычитание), поэтому для него определены оба метода.
В нашем парсере используются следующие силы связывания:
0 операторы без связи: ; и т. д. 10 операторы присваивания: = и т. д. 20 ?: 30 || && 40 операторы сравнения: === и т. д. 50 + - 60 * / 70 унарные операторы: ! и т. д. 80 . [ ( Выражения Основной компонент метода Пратта — функция expression. Она принимает на вход правую силу связывания, которая указывает, насколько активно выражение связывается с лексемами справа. var expression = function (rbp) { var left; var t = token; advance (); left = t.nud (); while (rbp < token.lbp) { t = token; advance(); left = t.led(left); } return left; } Функция expression вызывает метод nud текущей лексемы token, который обрабатывает литералы, переменные и префиксные операторы. Затем, до тех пор, пока правая сила связывания меньше, чем левая сила связывания следующей лексемы, у неё вызывается метод led. Этот метод обрабатывает инфиксные и постфиксные операторы. Процесс может быть рекурсивным, так как методы nud и led сами могут вызывать expression.Инфиксные операторы Оператор + — это инфиксный оператор, поэтому у него есть метод led, превращающий объект лексемы в дерево, две ветви которого (first и second) — это операнды слева и справа от знака +. Метод led принимает левый операнд в качестве параметра, а правый находит с помощью вызова expression. symbol("+", 50).led = function (left) { this.first = left; this.second = expression(50); this.arity = "binary"; return this; }; Символ * аналогичен + за исключением значения id и силы связывания. Он крепче связан с операндами, поэтому его сила связывания выше. symbol("*", 60).led = function (left) { this.first = left; this.second = expression(60); this.arity = "binary"; return this; }; Не все инфиксные операторы будут выглядеть так же, но многие будут. Поэтому мы можем упростить себе работу, определив функцию infix, которая поможет нам создавать инфиксные операторы. Функция infix принимает id, силу связывания и опционально функцию led. Если функция не задана, infix создаёт функцию led по умолчанию, которая годится в большинстве случаев. var infix = function (id, bp, led) { var s = symbol(id, bp); s.led = led || function (left) { this.first = left; this.second = expression(bp); this.arity = "binary"; return this; }; return s; } Теперь мы можем описать инфиксные операторы в более декларативном стиле: infix("+", 50); infix("-", 50); infix("*", 60); infix("/", 60); === — это оператор точного сравнения в JavaScript. infix("===", 40); infix("!==", 40); infix("<", 40); infix("<=", 40); infix(">», 40); infix (»>=», 40); Тернарный оператор принимает три выражения, разделённые? и :. Это не обычный инфиксный оператор, поэтому здесь придётся задать функцию led. infix (»?», 20, function (left) { this.first = left; this.second = expression (0); advance (»:»); this.third = expression (0); this.arity = «ternary»; return this; }); Оператор точка (.) используется, чтобы обратиться к члену объекта. Справа от него обязательно должно быть имя, но использоваться оно будет как литерал. infix (».», 80, function (left) { this.first = left; if (token.arity!== «name») { token.error («Expected a property name.»); } token.arity = «literal»; this.second = token; this.arity = «binary»; advance (); return this; }); Оператор [ используется, чтобы обратиться к члену объекта или элементу массива динамически. За выражением справа должна следовать закрывающая скобка ]. infix (»[», 80, function (left) { this.first = left; this.second = expression (0); this.arity = «binary»; advance (»]»); return this; }); Все эти инфиксные операторы левоассоциативны. Мы можем также создать правоассоциативные операторы (например, логические || и &&), уменьшив правую силу связывания. var infixr = function (id, bp, led) { var s = symbol (id, bp); s.led = led || function (left) { this.first = left; this.second = expression (bp — 1); this.arity = «binary»; return this; }; return s; } Оператор && возвращает первый операнд, если он ложен, иначе возвращает второй. Оператор || возвращает первый операнд, если он истинен, иначе возвращает второй. Ложное значение — это 0, пустая строка », false или null. Любое другое значение (в том числе любой объект) считается истинным. infixr (»&&», 30); infixr (»||», 30); Префиксные операторы Код, который мы использовали для правоассоциативных инфискных операторов, может быть адаптирован для префиксных операторов. Префиксные операторы правоассоциативны. Префикс не имеет левой силы связывания, потому что он не связывается ни с чем слева. Иногда префиксные операторы являются зарезервированными словами. var prefix = function (id, nud) { var s = symbol (id); s.nud = nud || function () { scope.reserve (this); this.first = expression (70); this.arity = «unary»; return this; }; return s; } prefix (»-»); prefix (»!»); prefix («typeof»); Метод nud для скобки (вызывает advance (»)»), чтобы найти парную скобку). Сама лексема (не попадает в синтаксическое дерево, потому что nud возвращает только содержимое скобок. prefix (»(», function () { var e = expression (0); advance (»)»); return e; }); Операторы присваивания Для определения операторов присваивания мы могли бы воспользоваться функцией infixr. Но лучше мы напишем отдельную функцию assignment, потому что нам хочется сделать ещё кое-что: убедиться, что выражение слева является lvalue, то есть ему действительно можно что-то присвоить, и установить поле assignment, чтобы в дальнейшем мы могли легко найти все присваивания. var assignment = function (id) { return infixr (id, 10, function (left) { if (left.id!== ».» && left.id!== »[» && left.arity!== «name») { left.error («Bad lvalue.»); } this.first = left; this.second = expression (9); this.assignment = true; this.arity = «binary»; return this; }); };
assignment (»=»); assignment (»+=»); assignment (»-=»); Заметьте: мы реализовали что-то вроде наследования. Функция assignment возвращает результат вызова infixr, а infixr — результат вызова symbol.Константы Функция constant создаёт константы языка. Метод nud превращает лексему-имя в лексему-литерал. var constant = function (s, v) { var x = symbol (s); x.nud = function () { scope.reserve (this); this.value = symbol_table[this.id].value; this.arity = «literal»; return this; }; x.value = v; return x; };
constant («true», true); constant («false», false); constant («null», null); constant («pi», 3.141592653589793); Символ (literal) — это прототип для всех строковых и численных литералов. Метод nud лексемы-литерала возвращает саму лексему. symbol (»(literal)»).nud = itself; Предложения В оригинале метод Пратта создавался для функциональных языков, где есть только выражения. Большинство популярных языков используют предложения (statements), которые не настолько сложно вкладываются друг в друга как выражения. Мы можем легко обработать и предложения, если добавим новый метод к лексемам: std (statement denotation, соответствие предложения). Метод std похож на nud, но вызывается он только в начале предложения.Функция statement разбирает одно предложение. Если текущая лексема содержит метод std, лексема резервируется и этот метод вызывается. Иначе мы считаем, что предложение представляет собой выражение, заканчивающееся точкой с запятой. Для надёжности мы будем считать за ошибку выражения, которые не являются присваиваниями или вызовами функций.
var statement = function () { var n = token, v; if (n.std) { advance (); scope.reserve (n); return n.std (); } v = expression (0); if (! v.assignment && v.id!== »(») { v.error («Bad expression statement.»); } advance (»;»); return v; }; Функция statements разбирает предложения, пока не встретит лексему (end) или }, которая обозначает конец блока. Функция возвращает предложение, массив предложений или null, если ни одного предложения не найдено. var statements = function () { var a = [], s; while (true) { if (token.id === »}» || token.id === »(end)») { break; } s = statement (); if (s) { a.push (s); } } return a.length === 0? null: a.length === 1? a[0] : a; }; Функция stmt используется, чтобы добавить символы предложений в таблицу символов. В качестве параметров она принимает id и функцию std. var stmt = function (s, f) { var x = symbol (s); x.std = f; return x; }; Предложение-блок — это список предложений в фигурных скобках, для которых определена новая область видимости. В обычном JavaScript нет областей видимости для блоков, но в нашем Упрощённом JavaScript они будут. stmt (»{», function () { new_scope (); var a = statements (); advance (»}»); scope.pop (); return a; }); Функция block разбирает блок.
var block = function () { var t = token; advance (»{»); return t.std (); }; Предложение var определяет одну или несколько переменных в текущем блоке. За именем переменной может следовать знак равенства = и начальное значение переменной. stmt («var», function () { var a = [], n, t; while (true) { n = token; if (n.arity!== «name») { n.error («Expected a new variable name.»); } scope.define (n); advance (); if (token.id === »=») { t = token; advance (»=»); t.first = n; t.second = expression (0); t.arity = «binary»; a.push (t); } if (token.id!== »,») { break; } advance (»,»); } advance (»;»); return a.length === 0? null: a.length === 1? a[0] : a; }); Предложение while определяет цикл. Оно включает выражение в скобках и блок. stmt («while», function () { advance (»(»); this.first = expression (0); advance (»)»); this.second = block (); this.arity = «statement»; return this; }); Предложение if создаёт условную конструкцию. Если после блока следует символ else, тогда мы анализируем также следующий блок или следующее предложение if. stmt («if», function () { advance (»(»); this.first = expression (0); advance (»)»); this.second = block (); if (token.id === «else») { scope.reserve (token); advance («else»); this.third = token.id === «if» ? statement () : block (); } else { this.third = null; } this.arity = «statement»; return this; }); Предложение break используется, чтобы завершить цикл раньше времени. stmt («break», function () { advance (»;»); if (token.id!== »}») { token.error («Unreachable statement.»); } this.arity = «statement»; return this; }); Предложение return используется, чтобы выйти из функции. Оно может содержать необязательное выражение (возвращаемое значение функции). stmt («return», function () { if (token.id!== »;») { this.first = expression (0); } advance (»;»); if (token.id!== »}») { token.error («Unreachable statement.»); } this.arity = «statement»; return this; }); Функции Функции — это исполняемые значения. Функция может иметь необязательное имя (чтобы она могла вызвать себя рекурсивно), список имён параметров в скобках и тело — список предложений в фигурных скобках. У функции есть своя область видимости. prefix («function», function () { var a = []; new_scope (); if (token.arity === «name») { scope.define (token); this.name = token.value; advance (); } advance (»(»); if (token.id!== »)») { while (true) { if (token.arity!== «name») { token.error («Expected a parameter name.»); } scope.define (token); a.push (token); advance (); if (token.id!== »,») { break; } advance (»,»); } } this.first = a; advance (»)»); advance (»{»); this.second = statements (); advance (»}»); this.arity = «function»; scope.pop (); return this; }); Функции выполняются с помощью оператора (. При вызове можно указать некоторое количество аргументов. Мы будем проверять левый операнд, чтобы отсечь ситуации, когда значение слева не может быть функцией. infix (»(», 80, function (left) { var a = []; if (left.id === ».» || left.id === »[») { this.arity = «ternary»; this.first = left.first; this.second = left.second; this.third = a; } else { this.arity = «binary»; this.first = left; this.second = a; if ((left.arity!== «unary» || left.id!== «function») && left.arity!== «name» && left.id!== »(» && left.id!== »&&» && left.id!== »||» && left.id!== »?») { left.error («Expected a variable name.»); } } if (token.id!== »)») { while (true) { a.push (expression (0)); if (token.id!== »,») { break; } advance (»,»); } } advance (»)»); return this; }); Символ this — это особая переменная. При вызове метода в ней хранится ссылка на объект. symbol («this»).nud = function () { scope.reserve (this); this.arity = «this»; return this; }; Литералы для объектов и массивов Литерал для массива — это набор выражений в квадратных скобках, разделённых запятыми. Каждое выражение вычисляется, и все результаты образуют новый массив. prefix (»[», function () { var a = []; if (token.id!== »]») { while (true) { a.push (expression (0)); if (token.id!== »,») { break; } advance (»,»); } } advance (»]»); this.first = a; this.arity = «unary»; return this; }); Литерал для объекта — это набор пар в фигурных скобках, разделённых запятыми. Пара состоит из ключа и выражения, которые разделены двоеточием (:). Ключ — это литерал или имя, которое интерпретируется как литерал. prefix (»{», function () { var a = []; if (token.id!== »}») { while (true) { var n = token; if (n.arity!== «name» && n.arity!== «literal») { token.error («Bad key.»); } advance (); advance (»:»); var v = expression (0); v.key = n.value; a.push (v); if (token.id!== »,») { break; } advance (»,»); } } advance (»}»); this.first = a; this.arity = «unary»; return this; }); О чём подумать и что поделать Созданное дерево можно передать в генератор кода или интерпретатор. Для создания дерева требуется минимум вычислений. И, как мы видим, требуется не так уж много усилий от программиста, чтобы написать такой парсер.Мы можем добавить в функцию infix параметр кода операции, который поможет генератору кода. Мы можем также передавать туда дополнительные методы для свёртки констант и генерации кода.
Мы можем добавить другие предложения (например, for, switch и try), метки, больше кода для проверок на ошибки, восстановления после ошибок и кучу новых операторов. Мы можем добавить задание и вывод типов.
Мы можем сделать наш язык расширяемым. Мы можем позволить программисту объявлять новые операторы и предложения так же легко, как объявлять новые переменные.
Испытайте сами парсер, описанный в этой статье.
Ещё один пример использования этого метода синтаксического разбора вы можете найти в проекте JSLint.
От переводчика: ковырял исходники JSLint и решил, что русский перевод этой замечательной статьи не помешает. Парсер в JSLint действительно исключительно понятный, мощный и легко расширяемый. Большое спасибо KVie за редактирование перевода.
