Лингвист в экспедиции

Музей языков закончился строкой 2 + 3 * (4 - 1). Python видит в ней число одиннадцать, а не россыпь чисел, знаков и скобок. Для одной формулы мы такое уже умеем: сортировочная станция Дейкстры из главы 15 переставляет знаки по таблице старшинства. Но станция не знает, что делать с if внутри for внутри def, со списком внутри вызова внутри индекса. Нужен способ описать строение любого языка и по этому описанию разбирать любой текст на нём. Такой способ пришёл в программирование из лингвистики, поэтому и учиться ему будем как лингвисты.

Полевой лингвист приезжает к носителям языка, у которого нет ни словаря, ни учебника. Он записывает фразы, пробует строить свои и спрашивает: так сказать можно? Объяснить правила носители не могут, они только чувствуют, что «ка ло ка» звучит нормально, а «ло ка» — дико. Из таких ответов лингвист восстанавливает правила, которых никто ему не диктовал. Остров и язык в этой главе придуманы, а работа — нет: её же делает каждая программа, которая читает другую программу.

День первый: фразы и отказы

Островитяне говорят короткими фразами. Вот первые записи из дневника: в левом столбце — фразы, которые информант одобрил, в правом — те, от которых он поморщился.

Закономерность видна сразу: «ка» повторяется, а между соседними «ка» обязательно стоит «ло». Запишем её как правило: фраза — это «ка», или «ка», за которым идут «ло» и снова фраза. Коротко:

Стрелка читается «может быть», вертикальная черта — «или». S — название того, что мы описываем, «фраза». Такая запись — грамматика: набор правил, по которым складываются все правильные фразы языка, и только они. Слова самого языка, «ка» и «ло», называют терминалами: дальше их разбирать некуда. А имена частей вроде S — нетерминалами: правила говорят, на что их можно заменить.

Правило ссылается само на себя. Как рекурсивная функция из главы 9, оно описывает бесконечно много фраз конечным текстом: в языке острова есть фразы с сотней «ка», хотя никто их не произносил. Проверьте грамматику на дневнике. В полевом журнале ниже грамматику пишете вы, а журнал сверяет её с каждой отметкой информанта.

День второй: скобки

На второй день в фразах появились ещё два слова, «ну» и «ти», и всегда парами: «ну ка ти», «ну ну ка ти ти», «ка ло ну ка ло ка ти». Зато «ну ка» без «ти» информант отверг, как и «ну ка ти ти». Внутри пары «ну … ти» может стоять любая фраза первого дня, и сама пара ведёт себя как одно «ка»: перед ней и после неё бывает «ло».

Значит, у фразы есть части. Назовём частью T то, что стоит между «ло»: это либо «ка», либо «ну», целая фраза и «ти». Грамматика второго дня:

Теперь правила ссылаются друг на друга по кругу: S через T, T через S. И тут пора признаться, что это за язык. «Ка» — число, «ло» — плюс, «ну» и «ти» — открывающая и закрывающая скобки. «Ка ло ну ка ло ка ти» — это 1 + (2 + 3). Вы восстановили грамматику арифметических выражений со сложением и скобками — её понимает каждый язык программирования. Программисты, впрочем, придумали записывать такие правила не на острове, а в Париже.

Париж, 1959–1960: как записывать правила

Вот, с точностью до мелочей, как в отчёте об ALGOL 60 определено целое число без знака:

Целое без знака — это цифра или целое без знака, за которым ещё цифра. Та же рекурсия, что в нашем S. Запись правил в таком виде называют формой Бэкуса — Наура, или БНФ. У каждого правила в левой части ровно один нетерминал, и заменять его можно независимо от того, что стоит вокруг. Грамматики с этим свойством называют контекстно-свободными, и ими описан синтаксис почти всех языков программирования. Описание грамматики Python, которое лежит в его исходниках, — тоже БНФ, только расширенная: в ней есть повторения и необязательные части.

Вывод и дерево

Грамматика проверяет фразу так. Начинаем со стартового нетерминала S и раз за разом заменяем какой-нибудь нетерминал одной из его правых частей, пока не останутся одни слова. Если получилась наша фраза — она правильная. Вот как грамматика второго дня получает «ка ло ну ка ти»; на каждом шаге заменяется самый левый нетерминал:

$$S \Rightarrow T\ \text{ло}\ S \Rightarrow \text{ка ло}\ S \Rightarrow \text{ка ло}\ T \Rightarrow \text{ка ло ну}\ S\ \text{ти} \Rightarrow \text{ка ло ну}\ T\ \text{ти} \Rightarrow \text{ка ло ну ка ти}$$

Такая цепочка замен называется выводом. Сама цепочка длинная и неудобная, но если нарисовать, что на что заменялось, получится дерево: в корне S, под ним три ребёнка T, «ло», S, и так далее до слов в листьях. Это дерево разбора. Прочитанные слева направо, листья дают фразу, а внутренние узлы показывают её строение: что с чем объединено. Нажмите на любую фразу в журнале выше — увидите и вывод, и дерево. Именно дерево и нужно программе. Дерево выражения из главы 17, которое мы обходили точкой по контуру, — это дерево разбора, из которого выкинули лишнее.

Грамматика работает и в обратную сторону. Если на каждом шаге выбирать правило наугад, она будет порождать правильные фразы, которых никто ещё не говорил. Поэтому лингвисты и называют такие грамматики порождающими. Пусть грамматика второго дня наговорит фраз, а мы переведём их в арифметику.

Каждая фраза — правильное выражение: eval вычислил все. Так устроены генераторы тестов для компиляторов: по грамматике языка они порождают тысячи случайных программ и проверяют, что компилятор с ними справляется. А ограничение глубины нужно, чтобы генератор не ушёл в бесконечную вложенность скобок, — рекурсия без базы из главы 9 подстерегает и здесь.

Сколько памяти нужно языку

В 1956 году, за три года до доклада Бэкуса, лингвист Ноам Хомский из MIT напечатал в журнале по теории информации статью «Три модели описания языка». Он сравнивал, какими устройствами можно описать английский: машиной с конечным числом состояний, грамматикой из правил вида «часть → части» и более сильной, трансформационной грамматикой. Хомский утверждал, что первой модели для человеческого языка не хватает. Из этой работы выросла классификация грамматик, которую теперь называют иерархией Хомского.

Разницу между первыми двумя строками вы почувствовали сами. Фразы первого дня можно проверять, помня только одно: что было последним словом, «ка» или «ло». Это конечный автомат из главы 31: состояний два, памяти больше не нужно. А чтобы проверить скобки второго дня, нужно помнить, сколько «ну» открыто, и их может быть сколько угодно. Конечному автомату, у которого состояний, скажем, сто, хватит фразы со ста одним «ну», чтобы сбиться со счёта. Нужен стек, как при проверке скобок в главе 15. Точное доказательство, что конечный автомат скобок не проверит, будет в главе 54.

Читал ли Бэкус Хомского, толком не помнил и он сам. По одним его воспоминаниям, запись выросла из «продукций» логика Эмиля Поста — правил переписывания строк. А в интервью 2006 года Бэкус рассказал, что много лет называл источником Хомского, пока ему не показали, что не сходятся даты. Так или иначе, вскоре после ALGOL 60 заметили, что БНФ и контекстно-свободные грамматики Хомского — одно и то же, и лингвистическая теория стала теорией компиляторов. Эта граница и определяет устройство почти любого разборщика: слова находят конечным автоматом, а строение фразы — с помощью стека или рекурсии.

Человек с биноклем

На третий день информант удивил. Он рассказывал про яблоки, и прозвучало слово «ла» — минус. «Ка ла ка ла ка» он перевёл однозначно: восемь яблок, три съели, потом ещё два — осталось три. А грамматика, которая напрашивается после второго дня, S → S ло S | S ла S | ка, видит в этой фразе два разных дерева: $(8 - 3) - 2 = 3$ и $8 - (3 - 2) = 7$. Грамматику, по которой у одной фразы бывает больше одного дерева, называют неоднозначной. В человеческом языке это обычное дело, и мы разрешаем двусмысленность по смыслу. Классический пример — «я видел человека с биноклем»: бинокль был у меня или у него?

Компьютер по смыслу догадываться не умеет, поэтому в языке программирования у текста должно быть одно-единственное дерево. Неоднозначность убирают в самой грамматике. Для минуса работает такой приём: правая часть разрешает справа только «ка», а продолжение растёт влево — S → S ла ка | ка. Тогда «ка ла ка ла ка» разбирается единственным образом, как $(8 - 3) - 2$.

В языках программирования есть своя знаменитая двусмысленность — висящий else. В C у if может не быть else, и тогда в записи if (a) if (b) x(); else y(); непонятно, чей это else — первого if или второго. Стандарт C решил: ближайшего. А отступы, которые видит человек, компилятору безразличны.

Билета нет, и автор ждал «купите билет», а программа молча печатает только «конец». Отступ врёт: else принадлежит внутреннему if, и раз внешний не выполнился, не выполнилось ничего. В ALGOL 60 эту ловушку закрыли грамматикой: сразу после then другой if стоять не может, его надо заключить в begin … end. Python закрыл её иначе. Блок в нём задаётся отступом, и каждый else стоит на уровне своего if, так что двусмысленности негде появиться.

Кто кого сильнее

На четвёртый день появилось слово «ми» — умножить. Информант считал «ка ло ка ми ка» с двойками как $2 + 2 \cdot 2 = 6$, а не $(2 + 2) \cdot 2 = 8$: «ми» связывает слова крепче, чем «ло». Это приоритет операций, или старшинство. В главе 15 его хранила таблица сортировочной станции. Грамматика хранит его иначе — этажами. На нижнем этаже то, что связано крепче всего: числа и скобки. Выше — произведения из них. Ещё выше — суммы из произведений.

По такой грамматике в «ка ло ка ми ка» умножение может оказаться только внутри T, то есть ниже сложения в дереве, а значит, выполнится раньше. Другого дерева грамматика не допускает. Заодно она решает вопрос о минусе и делении: E → E ла T растёт влево, поэтому $8 - 3 - 2$ — это $(8 - 3) - 2$. Такое поведение называют левой ассоциативностью. Бывает и правая: в Python 2 ** 3 ** 2 — это $2^{(3^2)} = 512$, как в математике. А унарный минус в Python слабее степени: -2 ** 2 равно −4.

Сначала слова

Островитяне говорили с паузами между словами, и это была поблажка. Текст программы так не устроен: в x1=12+y**2 нет ни одного пробела, а слов — семь. Живая речь, кстати, тоже звучит слитно, и первое, что делает лингвист, — учится резать её на слова. Поэтому разбор программы идёт в два этапа. Сначала лексер режет текст на токены — числа, имена, знаки, — выбрасывая пробелы и комментарии. Потом разборщик строит из токенов дерево по грамматике, и 12 для него — одно слово из двух цифр.

Калькулятор из главы 15 уже умел склеивать цифры в число. Добавим имена и знаки из двух символов.

Лексер всегда берёт самый длинный кусок, который ещё остаётся токеном. Поэтому x1 — одно имя, ** — степень, а <= — один знак, хотя каждый из них можно было бы разрезать надвое. Для этого двухсимвольные знаки и проверяются раньше односимвольных. Последняя строка падает с понятной ошибкой: символа @ в нашем языке нет. Лексер Python устроен так же, только знает больше видов токенов, и у него есть особенность, которой нет у C или Java.

В выводе есть INDENT и DEDENT. Лексер Python сам следит за отступами и, когда строка сдвинута вправо, выдаёт токен «отступ начался», а когда вернулась — «отступ кончился». Для разборщика это те же фигурные скобки C или begin … end ALGOL: грамматика Python пишет блок как INDENT, операторы, DEDENT. Отступы, о которых мы спорили в разделе о висящем else, превращаются в слова языка ещё до разбора.

Разборщик своими руками

Осталось научить программу строить дерево. Самый понятный способ подсказывает сама грамматика: на каждый нетерминал — функция. Функция expr разбирает сумму, term — произведение, factor — число или скобки. Каждая смотрит на очередной токен, решает, какое правило применить, и вызывает функции для частей правила. Скобки внутри скобок означают, что factor вызовет expr, которая вызовет term, которая снова вызовет factor, — рекурсия по кругу, как в грамматике второго дня. Так и появилось название: рекурсивный спуск.

Одна загвоздка. Правило E → E + T начинается с самого E, и функция expr, следуя ему дословно, первым делом вызвала бы саму себя, ничего не прочитав, — и так до переполнения стека. Это та же бесконечность, что в перевёрнутых правилах Пролога из прошлой главы. Лечится она переписыванием: сумма — это слагаемое, за которым сколько угодно раз идут «плюс или минус» и ещё слагаемое. Повторение становится циклом while, а левая ассоциативность сохраняется: каждый новый узел берёт старое дерево левым ребёнком.

Три функции разбора повторяют три правила грамматики четвёртого дня почти слово в слово, и в этом прелесть метода: грамматику видно в коде. Дерево — вложенные кортежи (знак, левое, правое), а вычислить его — пять строк рекурсии. Ошибки тоже получаются осмысленными: разборщик точно знает, чего ждал. Так устроены и промышленные компиляторы: например, разборщик C++ в компиляторе Clang написан вручную рекурсивным спуском. Ниже спуск можно пройти по шагам, а заодно испортить ему грамматику.

Дерево, которое строит Python

Python делает с вашим кодом то же самое, только по грамматике в две с половиной сотни правил. И его дерево можно посмотреть: модуль ast разбирает текст и отдаёт дерево из объектов.

Это наше дерево, только у узлов длинные имена: BinOp — двуместная операция, Add, Mult, Sub — какая именно, Constant — число. Скобок в дереве нет: они нужны были тексту, чтобы показать, что с чем связано, а в дереве это видно по форме. Дерево, из которого выброшено всё, что нужно только для записи, — скобки, запятые, ключевые слова, цепочки промежуточных нетерминалов вроде T → F, — называют абстрактным синтаксическим деревом, по-английски AST; по этим буквам назван и модуль. Последняя строка показывает, что дерево годится не только для картинки: функция compile переводит его в байт-код из главы 33, и Python его выполняет.

Разбирать код Python умеют не только интерпретаторы. По дереву работают программы, которые проверяют стиль, ищут ошибки и переставляют код. Найдём, например, все вызовы функций в программе. Текстовым поиском это сделать трудно, а по дереву легко: каждый вызов — узел Call.

Функция ast.walk обходит все узлы дерева, а нам остаётся отобрать нужные. Среди видов узлов есть Store и Load: так дерево помечает, записывают в имя или читают из него. На этой пометке держится последняя задача главы. Попробуйте то же на собственном коде.

И напоследок — польза на каждый день. Конфиги, настройки и данные часто приходят строкой, похожей на Python: {'width': 800, 'debug': False}. Велик соблазн выполнить её через eval. Но eval выполнит и __import__('os').system(...), если строку прислал злоумышленник. Безопасный путь — ast.literal_eval: она разбирает текст в дерево и соглашается вычислить его, только если в дереве одни литералы — числа, строки, списки, словари.

Отказ получил даже безобидный 2 ** 10: литералом он не считается, это уже вычисление. Зато вызов функции не пройдёт никогда. Тот же принцип — разобрать, посмотреть на дерево и только потом решать, что с ним делать, — лежит под каждым разборщиком конфигов, формул и форматов данных. Один такой формат вам предстоит разобрать самим.

Задачи

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

Напишите tokenize(text) — лексер маленького языка. Функция возвращает список пар (вид, значение). Виды такие. "NUM" — число: цифры, возможно с дробной частью через точку (3.14); значение — int или float. "NAME" — имя: буква или _, дальше буквы, цифры и _. "STR" — строка в двойных кавычках; значение — её содержимое без кавычек, где \", \\, \n и \t заменены на кавычку, обратную черту, перевод строки и табуляцию. "OP" — один из знаков ** <= >= == != + - * / % ( ) < > = , : [ ]. Пробелы и переводы строк пропускаются, от # до конца строки — комментарий. Неизвестный символ, незакрытая строка или неизвестная escape-последовательность — SyntaxError.

Знаки из двух символов проверяйте раньше односимвольных: text[i:i + 2] in ("**", "<=", …). Срез за концом строки ошибки не вызывает — он лишь окажется короче.

Дробь: после цифр проверьте, стоит ли точка и за ней цифра. Только тогда читайте дробную часть и превращайте кусок в float. Комментарий: увидев #, двигайте i до символа "\n" или до конца текста.

Строка: копите символы в список, пока не встретите закрывающую кавычку. Обратная черта значит «следующий символ особый»: найдите его в словаре {'"': '"', "\\": "\\", "n": "\n", "t": "\t"} и сдвиньтесь на два. Если текст кончился раньше кавычки — строка не закрыта.

Лексер — это конечный автомат: в каждый момент он в одном из немногих состояний («между токенами», «внутри числа», «внутри строки», «после обратной черты») и по очередному символу решает, что дальше. В главе 54 такие автоматы будут строиться сами из регулярных выражений, так что лексер можно задать списком регулярок — по одной на каждый вид токена. А посимвольный лексер с понятными ошибками до сих пор пишут вручную — и в этом курсе он вернётся: в интерпретаторе и компиляторе.

Напишите parse(text): по строке с формулой — её дерево. Лексер уже готов, нужен разборщик по грамматике:

Число в дереве — само число, имя — строка, операция — кортеж (знак, левое, правое), унарный минус — ("neg", x). Например, parse("2 + 3 * (4 - 1)") — это ("+", 2, ("*", 3, ("-", 4, 1))), а parse("-2 ** 2") — ("neg", ("**", 2, 2)), как в Python. Минус, деление и остаток группируются слева направо, степень — справа налево. Если текст — не формула, поднимите SyntaxError. Тесты вычисляют ваше дерево на сотнях случайных формул и сверяют с самим Python.

По функции на правило: expr, term, unary, power, atom. Звёздочка в грамматике — цикл while, как в разборщик.py из главы; знак вопроса — один if.

Почему power справа вызывает unary, а не power? Чтобы 2 ** -1 разбиралось. А правая ассоциативность получается сама: unary снова дойдёт до power, и 2 ** 3 ** 2 станет ("**", 2, ("**", 3, 2)). В expr и term, наоборот, новый узел берёт старое дерево левым ребёнком.

Ошибки. atom поднимает SyntaxError, если пришло не число, не имя и не скобка, — в том числе когда токены кончились. После скобочного выражения обязательно ). А parse после разбора проверяет, что токенов не осталось: иначе "1 2" тихо разберётся как 1.

Пять правил — пять функций, и старшинство нигде не записано таблицей: оно в том, кто кого вызывает. Сравните со станцией со степенью из главы 15: там правая ассоциативность степени была одним сравнением в таблице, здесь — тем, что power справа вызывает функцию своего же уровня. Тонкое место — -2 ** 2: унарный минус стоит в грамматике выше степени, поэтому применяется к уже готовой степени и даёт −4, как в Python и в математике. В JavaScript, кстати, такую запись без скобок вовсе запретили — слишком многие ошибались.

JSON из главы 8 описан грамматикой, которая умещается на открытке. Напишите parse_json(text), которая разбирает текст JSON и возвращает то же, что json.loads: объект — dict, массив — list, строку — str, число — int или (если есть точка или показатель) float, а true, false, null — True, False, None. Модулем json, eval и literal_eval пользоваться нельзя. Всё, что не JSON, — ValueError: запятая перед ], одинарные кавычки, 01, табуляция или перевод строки прямо внутри строки (их пишут только как \t и \n), лишние символы в конце.

Это рекурсивный спуск: по методу на правило. value смотрит на первый значимый символ — {, [, ", цифра или минус, буква — и вызывает нужный метод. array после [ проверяет, не пустой ли массив, а дальше повторяет «значение, потом запятая или ]».

Число проще всего не вычислять самому: найдите, где кончается его запись по грамматике, и отдайте этот кусок int(...) или float(...). Но проверять запись придётся по грамматике: int("01") и float(".5") Python съест, а JSON — нет.

Подвох в \uXXXX. Символы за пределами первых 65 536, например смайлики, JSON записывает двумя такими кодами — суррогатной парой: смайлик с кодом 1F600 — это \ud83d\ude00. Если первый код от D800 до DBFF, а следом идёт второй от DC00 до DFFF, склейте их: $\text{0x10000} + (h - \text{0xD800}) \cdot 1024 + (l - \text{0xDC00})$.

Методы obj и array вызывают value, а та — снова их: вложенность документа становится глубиной рекурсии. Поэтому документа всего в пятьсот вложенных скобок хватит, чтобы уронить этот разборщик: Python остановит рекурсию ошибкой RecursionError, как в главе 9. Это известный способ атаки на серверы, и промышленные разборщики JSON защищаются от него ограничением глубины. Отдельного лексера здесь нет, он встроен в разборщик: peek пропускает пробелы, а числа и строки читаются посимвольно. Для маленьких форматов так делают часто — грамматика JSON настолько проста, что её «слова» узнаются по первому символу.

Линтеры — программы, которые ищут в коде подозрительные места, — работают по дереву. Напишите unused(source): по тексту программы на Python — отсортированный список имён, которым что-то присваивают, но которые нигде не читают. «Присваивают» и «читают» понимаются так, как их помечает модуль ast: узел ast.Name с пометкой ast.Store — запись (присваивание, переменная цикла, распаковка), с пометкой ast.Load — чтение. Имена, начинающиеся с подчёркивания, по обычаю означают «нарочно не используется» — их не включайте. Если в коде синтаксическая ошибка, пусть вылетит SyntaxError.

Обойдите все узлы ast.walk(tree) и соберите два множества: имена из ast.Name с isinstance(node.ctx, ast.Store) и с ast.Load. Ответ — разность множеств без имён на _, в отсортированном виде.

Искать имена в тексте программы поиском подстроки не выйдет: print("total") содержит слово total, но не читает переменную, а f"{name}" читает её, хотя это строка. Дерево различает оба случая: строка — это Constant, а выражение внутри f-строки — полноценный Name.

Девять строк — и у вас проверка из тех, что делают линтеры вроде pyflakes. Наш мини-линтер грубее: он не различает области видимости, поэтому x в одной функции и x в другой для него одно имя, а запись count += 1 он считает записью без чтения. Pyflakes и его собратья строят по дереву таблицу областей видимости — то, что в следующей главе назовут окружениями. Но начинают они так же: с ast.parse.

Куда дальше

Экспедиция окончена. Строку вы теперь умеете превращать в дерево, а Python делает то же самое с каждой вашей программой, и модуль ast показывает результат.

Но дерево само ничего не делает. ("+", 2, ("*", 3, ("-", 4, 1))) — это только кортежи, а одиннадцать из них получилось потому, что мы написали evaluate. Для формулы хватило пяти строк. А если в дереве есть переменные, которые где-то определены, функции, которые вызывают сами себя, и функции, которые возвращают функции? Где хранить значения имён, как вызов узнаёт свои аргументы, почему функция помнит переменные места, где её создали? Дерево есть. Как заставить его работать? В следующей главе мы напишем интерпретатор — сначала для Лиспа, чьи программы, как мы видели в музее, уже лежат готовыми деревьями.