Поэтому в самой знакомой мне IDE парсеры пишутся обычно руками, рекурсивным спуском, скучно, занудно и однообразно (чего стоит один практически идентичный код, раскопированный для каждой бинарной операции). Восстановление после ошибок тогда получается достаточно несложно.
Так вот, не рекурсивным спуском единым жив человек. Уже почти устоялось API для другого метода, придуманного когда-то Праттом, примененного Крокфордом, до боли напоминающего вдохновленный языком Forth метод Тузова, наконец, дошедшего до меня и творчески переработанного. Про это API и расскажу.
Итак, по старинной фортовской привычке мы начинаем с объявления данных кодом. Данные у нас - это поток токенов от лексера, вот они-то и будут кодом. У каждого токена будет свой собственный маленький кодик, вот такого вида:
interface TokenParser {
boolean parseToken(PrattBuilder builder);
}
ПраттБилдер (лучшие варианты названия принимаются) - это интерфейс к системе, он - наше все, двигает лексер, хранит промежуточные состояния, строит дерево и запускает токенпарсеры. Построен он поверх идейского PsiBuilder'а и обладает сходной приятной функциональностью по прозванию маркеры. Маркер - это очень легкая штука, позволяющая запомнить место в потоке токенов. Потом к этому месту можно будет откатиться, либо создать новый узел дерева с началом в нем.
С каждым токеном ассоциируется еще и число, приоритет. Самый главный метод праттбилдера носит скромное название parse, принимает одно число, и идет последовательно, каждый раз для текущего лексерного токена вызывая его токенпарсеры, пока приоритеты токенов строго больше числа-параметра либо пока какой-нибудь токенпарсер не вернет false. Сами токенпарсеры внутри себя могут делать что угодно, сдвигать лексер насколько угодно (в том числе путем вызова билдеровского parse рекурсивно), но не в их власти откатиться раньше токена, для которого их вызвали. Билдер всегда помнит место, в котором вызвали его parse, и умеет создавать узлы дерева, начинающиеся там.
Это была фортовская часть. Теперь к Пратту. Самый частый вариант токенпарсера, DefaultTokenParser, реализован заветами этого товарища, и умеет различать два случая вызова себя и делегировать всю работу одному из двух подпарсеров - соответствующих своих аргументов конструктора. Первый случай, "свежачок", когда токен встретился сразу же в билдеровском parse, слева от него ничего еще нет, у Пратта это зовется nud, у меня пока - PrefixParser (better name needed!!!). Второй случай, когда слева уже что-то есть, и там даже построился узел дерева с определенным типом, у Пратта - led, у меня пока - ProceedingParser (oh name...). Первое используется, когда по токену можно понять, какую конструкцию он начинает (унарная префиксная операция), второй - какую конструкцию он продолжает (инфиксная бинарная операция или много чего еще) или закачивает (унарная постфиксная операция).
У токена нечасто определены оба компонента, самый очевидный пример токена, умеющего и начинать и продолжать - "+" или "-". Если nud или led нужен, но отсутствует, генерируется ошибка. Токен, который мы анализировали, нам уже неинтересен, мы с него все, что хотели, получили, поэтому перед вызовом подпарсеров лексер сдвигается вперед. Оба подпарсера возвращают тип узла, который надо построить от стартового маркера до текущего места. Обычно алгоритм разбора токенпарсера по умолчанию получаются следующим: вызываем nud первого токена, а потом, пока не посинеем, вызываем led у текущих токенов.
Пример простого нуда на псевдоязыке:
unary(IElementType type, int priority) = fun (builder) ->
builder.parse(priority);
return type
И еще проще:
tokenElement(IElementType type) = fun (builder) ->
return type
Пример простого леда (бинарная левоассоциативная операция) почти дословно такой же:
binary(IElementType type, int priority) = fun (leftType, builder) ->
builder.parse(priority);
return type
Постфиксная операция еще проще:
postfix(IElementType type) = fun (leftType, builder) ->
return type
Распарсить простые выражения можно теперь с помощью весьма лаконичного кода:
NUMBER: priority=10, nud=tokenElement(NUMBER_LITERAL)
IDENTIFIER: priority=10, nud=tokenElement(QNAME)
"(": priority=10, nud=fun (builder: PrattBuilder) ->
builder.parse(0);
builder.assertToken(")");
return PARENTHESES
".": priority=9, led=binary(QNAME, 9)
"!": priority = 8, nud=unary(NEGATION, 8)
"+","-": priority=8,
nud=unary(ARITHMETIC_UNARY, 8),
led=binary(ARITHMETIC_BINARY, 6)
"*","/": priority=7, led=binary(ARITHMETIC_BINARY, 7)
Парсер, например, для сокращенного определения класса в Java лучше выражается через просто токенпарсеры:
"public", "static", etc.: priority = -100,
tokenParser = fun (builder) ->
builder.advance();
return true;
"class": priority=-100,
tokenParser = fun (builder) ->
builder.finishPrefix(MODIFIER_LIST);
builder.advance();
builder.assertToken(IDENTIFIER);
if (builder.assertToken(EXTENDS)) {
builder.advance();
builder.parse(9);
}
builder.assertToken("{");
builder.parse(-90);
builder.assertToken("}");
return JAVA_CLASS
Это уже достаточно напоминает рекурсивный спуск. В принципе, мне сей метод видится как гармоничное сочетание разбора сверху, снизу и стека приоритетов операторов. В каждом месте программист вправе выбрать, что лучше в данном конкретном случае.
В данный момент на праттовской основе (только, увы, в синтаксисе Java) в достаточной степени написан парсер для языка шаблонов FreeMarker, и процесс мне нравится. Парсер получается более прямолинейный, проверок условий в нем намного меньше, чем в обычном рекурсивном спуске. Это можно рассматривать как паттерн Visitor, он же полиморфизм, мы вместо делания многочисленных проверок на тип вызываем абстрактный метод у самого типа.
Из достоинств еще можно упомянуть модулярность. Можно теоретически взять и поменять парсер или приоритет у токена. Что важнее, можно легко начать парсить не сначала, а из любой середины, почти с любого токена, что открывает неплохие возможности для инкрементального репарса.
Главный недостаток - меньшая понятность. Суть рекурсивного спуска понятна сразу, потом только начинаешь увязать в конкретных бесчисленных флажках, циклах, условиях и маркерах, но это уже детали реализации конкретного парсера. Тут флажков, циклов, условий и маркеров поменьше, но зато основная идея ясна не сразу, непрозрачна. И конкретные числа несколько мешают восприятию.
Еще особенность, уж не знаю, достоинство или недостаток. При написании парсера надо думать. Этот парсер не совсем похож на грамматику, и не пишется на автомате, глядя на таковую. Скорее всего, такие парсеры тоже можно генерировать по грамматике, для этого надо только погрузиться в соответствующую науку. Но это уже совсем другая история.
No comments:
Post a Comment