Разработка парсера PHP средствами ANTLR

В качестве хобби последние несколько месяцев я разрабатываю парсер языка PHP с помощью ANTLR ^[1]. Сам проект ^[2] для меня скорее просто Just for fun, но в ходе его реализации у меня, разумеется, возникали сложности. Тут сказывается как особенность языка PHP с полным отсутствием спецификаций, так и ограничения алгоритмов LL(k).

В этой статье я бы хотел поделиться техническими решениями и некоторыми хитростями в реализации парсера и процедуры его тестирования. Данная статья будет полезна тем, кто хочет подробнее разобраться в использовании средства ANTLR v2.

Проблематика

Здесь я попробую рассказать, чем интересна данная задача и какие сложности предстояло решить.

1. Отсутствие формальной спецификации языка

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

2. Грамматика PHP не является контекстно-свободной

Это означает, что в чистом виде существующие алгоритмы разбора (группы алгоритмов LL(k) и LR(k)) неприменимы в принципе. Причины следующие:

1. Перемежение исполняемого кода с произвольным текстовым потоком.
2. Нотация HEREDOC — кавычкой является произвольная последовательность символов
3. Ряд ключевых слов языка могут служить обычными идентификаторами.

В список чисто технических сложностей можно смело отнести альтернативный синтаксис управляющих конструкций и неполноту официальной документации.

Реализация

Отделение кода от текстового «мусора»

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

<?php … ?>

Наиболее лаконичным здесь оказалось решение на основе мультиплексирования лексем ^[3] и использование стека лексеров. Для этой цели мне уже понадобилась дополнительная сущность, которая хранит текущее состояние всего парсера (как минимум — состояние «сейчас ожидается код» или «сейчас пробрасываем любой текст», см. ParsingState.java ^[4]).
И, разумеется, две разных грамматики лексеров: phpLexer ^[5] и phpOutTheCode ^[6]. Сигналами для переключения контекста служат непосредственно лексемы <?php, <?= и ?>.

Схематично эта идея изображена ниже.

Строки HEREDOC

Нотация HEREDOC ^[7] представляет собой многострочный строковой литерал, в качестве «кавчек» которого может выступать любой идентификатор. Такой литерал распознается встраеваемым кодом, который выполняется после того, как встречается начало HEREDOC в виде лексемы <<<. Непосредственно этот фрагмент грамматики лексера можно увидеть здесь ^[8].

Keywords как идентификаторы

Ключевые слова в грамматике ANTLR — это не идентификаторы. Если посмотреть на код, который в таких случаях генерируется ANTLR'ом, ключевое слово всегда распознается как обычный идентификатор, а затем образ (строковое представление) проверяется по словарю ключевых слов. Эта операция проводится внутри класса лексера, который на момент распознавания не знает (и не может знать) контекст класса парсера по следующим причинам:

• Парсер берет следующую лексему не из лексера, а из специального буфера. Буфер наполняется загодя, чтобы иметь возможность заглянуть на k лексем вперед, как того требует алгоритм LL(k). Это значит, что в момент распознания лексемы парсер еще может не знать, ожидается ли в данном месте идентификатор или нет: лексер работает с опережением.
• В случае обработки синтаксических предикатов (т. н. Управляемый бектрекинг) парсер может выполнять «откаты» по потоку лексем, и отрабатывать ситуацию отката/доката по предикату извне отловить тяжело.

К счастью, решение есть и достаточно простое: в качестве идентификатора объявить правило на уровне парсера и в качестве возможных значений перечислить помимо «честных» идентификаторов еще и лексемы ключевых слов. Тут, правда, есть другая опасность: возникнет неоднозначность на уровне правил парсера, например операция приведения к типу
(typeName) expression
может трактоваться как
(expression) expression, поскольку, например, ключевое слово int станет в силу описанной причины входной лексемой в expression (поскольку будет являться идентификатором). Конструкция смысла не имеет и приведет к ошибке распознавания.

Такая проблема решилась с помощью дополнительного синтаксического предиката (см. php.g ^[9]).

typeCastExpression[boolean allowComma]:
  (LPAREN typeName RPAREN expression[false, false])  => 
    (LPAREN^ typeName RPAREN { #LPAREN.setType(TYPE_CAST) ;} typeCastExpression[allowComma] ) 
  | (LNOT^ typeCastExpression[allowComma])
  | (DOG^ typeCastExpression[allowComma])
  | (BW_NOT^ typeCastExpression[allowComma] )
  | (MINUS^ {#MINUS.setType(UNARY_MINUS);} typeCastExpression[allowComma]) 
  | (PLUS^ {#PLUS.setType(UNARY_PLUS);} typeCastExpression[allowComma]) 
  | incrementExpression[allowComma]
  ;

Приоритет операций и прочие technical difficulties

Много усилий было потрачено на выяснение и «утрясание» приоритета операций. Официальная документация ^[10] неполна. Так, в числе операторов там числится запятая, которая им в PHP не является.
Интересно, что тернарный оператор в PHP имеет приоритет ниже операторов присваивания. То есть конструкция вида

a = test() ? b = c : d = e;

Не скомпилируется в C/C++, но скомпилируется в PHP (такой пример нашелся в коде phpBB3).

Еще из любопытного: выражение echo (это не функция, а именно выражение) допускает перечисление операндов через запятую. Это сработает как конкатенация при выводе, но благодаря исходникам phpMyAdmin нашлась еще одна схожая конструкция — print, которая похожа на echo, но запятые уже не позволяет.

Лексема ?>, оказывается, эквивалентна точке с запятой. Оператор <?= эквивалентен echo (включая замечание выше про запятую).

Символ доллара часто выглядит как оператор (я задавал ^[11] вопрос на эту тему ранее), но им не является: возможность «применения» нескольких долларов подряд распознаются лексером и потом все равно выглядит как одна лексема — так сделано в официальном компиляторе.

Тестирование

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

Смысл тестов, которые я для этих целей использую, крайне прост: создается простейшая консольная обертка вокруг библиотеки, которая принимает на вход файл php. Если парсер распознал файл без проблем, то обертка не делает ничего, встретилась проблема — печатаем соответствующую информацию.
Программа обертка запускается командой find с выводом в файл.
Примерно так:
$ (find ~/Documents/distr/phpBB3/ -name '*.php' -print -exec java -jar bin/jar/parse-php-test.jar -f {} ; ) &>./out-phpbb.txt

Файлы вывода (в данном случае out-phpbb.txt) можно сохранять и сравнивать с новым результатом. Улучшился результат или ухудшился — можно понять по количеству строк в файле:

$ wc -l ./out-koh.txt*
     498 ./out-koh.txt
     502 ./out-koh.txt.old

Заключение

Проект парсера на данный момент представляет скорее академический интерес. Его можно использовать в качестве основы, например, для расширения функциональности CheckStyle ^[12] или для реализации собственного php beautifier.

Как вы могли заметить, парсер сейчас расчитан на версию языка 5.2, хотя принципиальных проблем в доведении грамматики до уровня 5.3 на мой взгляд нет (с версией 5.4 сложнее: тестовой базы для валидации грамматики сейчас практически нет). На данный момент парсер успешно разбирает весь набор исходников ZF 1.11, Yii Framework 1.1.10 и phpBB 3.0.10.

Буду рад, если данная работа показалась кому-то интересной и/или полезной. Так же будут полезны ваши замечания и критика.

Спасибо за ваше внимание!

Автор: knekrasov