- PVSM.RU - https://www.pvsm.ru -
Добрый день.
В заключительной части про написание собственного генератора LALR-парсеров я бы хотел описать возможные особенности и фичи. Кроме того я опишу чего мне не хватало в существующих решениях и ради чего я начал писать свой велосипед.
Дабы задать контекст, сообщу, что грамматика для анализа — это ECMAScript, так же известный как JavaScript. Конкретная спецификация — ECMA-262, редакция 5.1 от июня 2011 года.
Когда я впервые столкнулся с сложностями написания, я не сразу бросился писать код компилятора. Вначале я изучил как решили данные проблемы крупные компании: Mozilla и Google (исходников Opera и IE — нету в открытом доступе). Как оказалось, они не особо парились с формализацией грамматики и писали код как есть, то есть так, как я предостерегал делать в первой части. Пример обработки if'a в v8 (JS-движок Chrome):
IfStatement* Parser::ParseIfStatement(ZoneStringList* labels, bool* ok) {
// IfStatement ::
// 'if' '(' Expression ')' Statement ('else' Statement)?
Expect(Token::IF, CHECK_OK);
Expect(Token::LPAREN, CHECK_OK);
Expression* condition = ParseExpression(true, CHECK_OK);
Expect(Token::RPAREN, CHECK_OK);
Statement* then_statement = ParseStatement(labels, CHECK_OK);
Statement* else_statement = NULL;
if (peek() == Token::ELSE) {
Next();
else_statement = ParseStatement(labels, CHECK_OK);
} else {
else_statement = factory()->NewEmptyStatement();
}
return factory()->NewIfStatement(condition, then_statement, else_statement);
}
Зачем они так сделали? Есть несколько причин:
Конечно, есть и ряд минусов:
#define CHECK_OK ok);
if (!*ok) return NULL;
((void)0
Теперь можно и перейти к тем подводным камням грамматики и моим ожиданиям. Сразу скажу, что некоторые пункты вполне выполняются сторонним софтом. Но в сумме нет целостной программы, да и есть пункты, на которые я не нашёл решения.
В своей задаче мне нужно было сохранить текст и позицию комментариев, а не отбрасывать их. ANTLR и bison/flex это умеют. Первый за счет мультиплексирования лексера, второй — за счет мощности flex'a. Так как писать свой лексер я пока не начал, я использую flex. И решил данную задачу следующим образом:
/* [Comment] = [MultiLineComment] | [SingleLineComment] */
/* [MultiLineComment] */
/* start of multiline, grab whole comment, that's why i use yymore() */
"/*" {
BEGIN(multilinecomment);
yymore();
m_loc.setMore(true);
}
/* skip all comments chars except "*" */
<multilinecomment>[^*nr]* { yymore(); }
/* skip all "*", that not followed by "/" */
<multilinecomment>"*"+[^*/nr]* { yymore(); }
/* end of comment */
<multilinecomment>"*"+"/" {
m_comments.push_back(CParser::Comment(yytext, m_loc.tokenLine(), m_loc.tokenCol()));
m_loc.setMore(false);
BEGIN(INITIAL);
}
/* [SingleLineComment] increment lineNo */
("//"([^rn])*{LineTerminator})|("//"([^rn])*) {
m_comments.push_back(CParser::Comment(yytext, m_loc.tokenLine(), m_loc.tokenCol()));
m_loc.linc();
}
Ничего особенного здесь нет. Используем внутренние состояния лексера и yymore() который позволяет создать целостную лексему из нескольких правил.
JS имеет особую форму задания reg-exp'ов. Их можно писать просто так в исходном коде, и сигналом является "/". Но одновременно это еще и знак деления. Соответственно и поток лексем сильно отличается в этих случаях. Слэш трактуется как знак деления если парсер в данной позиции разрешает его увидеть. И как знак начала reg-exp — во всех остальных случаях:
// здесь слэш означает начало regexp'a
/asd[^c]/i.match(s);
// а уже здесь - знак деления
a = b / c;
То есть парсер должен уметь ставит флажок, если в данный момент может придти оператор деления. На уровне flex'a решается просто:
/* [RegularExpressionLiteral] it has more length then [DivPunctor] (at least 3 == "/X/" versus 2 == "/="), that's why it would be proceeded first, before [DivPunctor] */
"/"{RegularExpressionFirstChar}({RegularExpressionFirstChar}|"*")*"/"({IdentifierStart}|[0-9])* {
if (m_mode != Mode::M_REGEXP)
REJECT;
yylval->assign(yytext, yyleng);
return token::T_REGEXP;
}
/* [DivPunctuator]: "/" or "/=" */
"/" return token::T_DIV;
"/=" return token::T_DIVAS;
Так как flex жадный лексер и старается обработать как можно более длинные лексемы, то сначала он попадёт в правило для regexp'ов, а там если задан режим для деления он перейдет к следующему правилу.
Мне очень хотелось бы получить именно parser tree в результате анализа. С ним очень удобно работать в рамках моей задачи. AST тоже подходит, но увы единственный поддерживающий данный формат ANTLR требует задавать явные правила для его постройки поверх грамматики. Каких-либо особых действий не требовалось. Разве что небольшие добавления к алгоритму анализатора:
while (!accepted && !error)
{
...
switch (act.type)
{
...
case Action::ACTION_SHIFT:
...
node.col = m_loc.tokenCol();
node.line = m_loc.tokenLine();
node.type = ParseNode::NODE_TERM;
node.termVal = s;
node.symb.term = tok;
nodes.push(tree.create(node));
break;
case Action::ACTION_REDUCE:
...
node.type = ParseNode::NODE_NONTERM;
node.symb.nonTerm = (Symbols::SymbolsType)act.reduce.nonTerm;
CTree<ParseNode>::TreeNode * parent = tree.create(node);
unsigned long ruleLen = act.reduce.ruleLength;
while (ruleLen)
{
tree.add(parent, nodes.top(), true);
nodes.pop();
ruleLen--;
}
nodes.push(parent);
break;
}
}
if (nodes.top())
tree.SetRoot(nodes.top());
В грамматике можно встретить вот такую штуку
ExpressionStatement = [lookahead ∉ {{, function}] Expression ;
Нет, это не стандартный expect-символ свертки, о котором я говорил в предыдущей части. Это наоборот попытка фильтрации первого символа Expression. То есть по этому правилу мы должны из Expression выкинуть лишние дочерние продукции, которые начинаются с терминала "{". В данном случае это сделано для того чтобы избежать конфликта между Block, который может выглядеть как "{}" и одним из порождений просто Expression: "{}" как задание пустого javascript-объекта Object. Аналогично для «function».
Решение можно сделать и без магии парсера, а только подправив грамматику:
ExpressionStatement = ExpressionWithoutBracket
ExpressionWithoutBracket = ... | AssignmentExpressionWithoutBracket | ...
...
И так пока не дойдем до правила которое начинается с терминала "{", и исключим это правила из предпоследней грамматики. Проблема в том, что промежуточных шагов около 20. Кроме того, умножаем это на 2 (еще же и «function»!) а затем еще на 2 потому что такой приём используется для этого же правила но в другой ситуации (2 линейки — Expression и ExpressionNoIn). Не, меня это не радует совсем.
Технически же в моём парсере это решается довольно просто:
ExpressionStatement = Expression {filter: [objectLiteral, functionDeclaration]}
...
ObjectLiteral = {commonId: objectLiteral} '{' '}' | '{ 'PropertyNameAndValueList '}' | '{' ',' '}'
При замыкании мы провешиваем ярлычек фильтрации от родительского пункта к дочернему если нужно. И когда встречаем правило подпадающее под фильтрацию просто не включаем его в замыкание.
Это почти что подвид предыдущего пункта, но здесь нужно смотреть не только на первый символ, но и на произвольный. Иллюстрация — вышеупомянутый ExpressionNoIn и схожий с ним VariableDeclarationListNoIn. Если разобраться подробнее, то корни проблемы уходят в 2 вида for'a для примера:
// первый синтаксис
for (var id in obj) alret(id);
// второй синтаксис
for (var id = 1; id < 10; id) alert(id);
В обычных условиях при инициализации переменных мы можем использовать in, а-ля a = 'eval' in window; Этот оператор проверяет существование члена в заданном объекте (гусары, молчать!). Однако в цикле он используется для перебора всех членов объекта. И, собственно, очень легко может возникнуть путаница, поэтому внутри второго синтаксиса запрещено использовать in. На самом деле LALR-парсер легко всё это разрулит благодаря свертке с проверкой следующего символа (';' или ')'), но создатели грамматики видно ориентировались на более широкий класс парсеров и поэтому введи дублирующие 20 правил для случая без оператора «in». Однако нужно следовать грамматике, поэтому также необходим механизм выключения неугодных дочерних (пра-пра-...) правил.
У меня он полностью аналогичен предыдущему пункту, разве что отличия в мелочах:
ExpressionNoIn = Expression {filter: [RelationalExpression_6]}
...
RelationalExpression = ShiftExpression | RelationalExpression '<' ShiftExpression | RelationalExpression '>' ShiftExpression | RelationalExpression '<=' ShiftExpression | RelationalExpression '>=' ShiftExpression | RelationalExpression 'instanceof' ShiftExpression | {id: RelationalExpression_6} RelationalExpression 'in' ShiftExpression
Это опциональная фича, которая просто облегчает жизнь. А насколько именно показывают примеры ошибок. В самой грамматике забыли добавить NoIn в одном из правил:
ConditionalExpressionNoIn = LogicalORExpressionNoIn ? AssignmentExpression : AssignmentExpressionNoIn
Второй AssignmentExpression должен быть очевидно с постфиксом.
Еще одна занятная фишка JavaScript'a — это необязательность завершения Statement'ов точкой с запятой. Даже в тех местах где этого требует грамматика. Правила вставки одновременно просты в описание и сложны в реализации:
Вставка же происходит довольно просто — если определили необходимость данного действия, то просто заходим на новый круг FSM'a, подменив последний считанный токен точкой с запятой. Ну и в следующем shift'е не читаем новый токен, а используем тот, который вызвал ошибку.
JS очень грамотный в этом плане язык. Поддержка utf16 прописана жестко в стандарте. Вплоть до того, что перед парсингом весь исходник должен быть переконвертирован в utf16. Однако, к сожалению, flex не умеет такого (не, xXX не подходит. навскидку, порядка тысячи символов нужно будет кодировать). Поэтому, пока данное условие не выполнено.
Еще одна довольно большая тема, которая облегчает работу с грамматикой. Мне в первую очередь нужны были следующие квантификаторы: "|" — варианты правил, где левая часть общая, а правые различны; "?" — опциональность символа в правиле; "*" — символ повторяется 1 или более раз. Да они вполне разрешаются на уровне BNF-грамматик:
A = B | C
// превращается в
A = B
A = C
A = B? C
// превращается в
A = B C
A = C
A = B*
// превращается в
A = A B
A = B
Здесь всё отлично за исключением последнего примера. В данном случае мы получаем ступеньки в дереве. То есть если B повторится 5 раз, то получим узел A с глубиной равной 5. Это весьма неудобно. Поэтому опять же я решил ввести модификации в парсер обеспечивающие удобное линейное представление — B B B B B образуют один узел A с 5 листьями B. На практике это выглядит как введение нового типа операций — ReduceRepeated. И модификации функций замыкания и определения сверток. В closeItem() закольцовываем элемент.
А вот, что получиться, если сделать как принято:
На этом всё. Спасибо за то, что читали эту статью.
Автор: mark_ablov
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/3997
Ссылки в тексте:
[1] Часть 1. Базовая теория: http://habrahabr.ru/post/140058/
[2] Часть 2. Описание LR-генераторов: http://habrahabr.ru/topic/edit/140339/
Нажмите здесь для печати.