Простейшим решением является фактически принятое разработчиками C и, следовательно, различными производными C: трактуйте назначение просто как еще один оператор, не ограничивая его тем, что он находится на верхнем уровне инструкции. Таким образом, в C, следующее беспроблемное:
while ((ch = getchar()) != EOF) { ... }
Не все считают, что хороший стиль, но это, конечно, часто (особенно в положениях о for заявления, синтаксис которых более или менее требует, чтобы назначение быть выражением).
Есть две небольшие осложнения, которые относительно легко выполнить:
Логически, и в отличии от большинства операторов присваивания правоассоциативного так, что a = b = 0 анализируются как a = (b = 0) и не (a = b) = 0 (что было бы очень неожиданно). Он также связывает очень слабо, по крайней мере, вправо.
Мнения различаются в зависимости от того, насколько сильно он должен связываться слева. В C, по большей части, применяется строгая модель приоритета, так что a = 2 + b = 3 отклоняется, так как он анализируется как a = ((2 + b) = 3). a = 2 + b = 3 может показаться страшным, но рассмотрим также a < b ? (x = a) : (y = a). В C++, где результат тернарного оператора может быть ссылкой, вы можете написать, что как (a < b ? x : y) = a, в котором требуются скобки, даже назначение мысли имеет более низкий приоритет, чем тройной оператор.
Однако ни один из этих вариантов трудно реализовать в грамматике.
На многих языках левая часть задания имеет ограниченный синтаксис. В C++, который имеет ссылочные значения, ограничение можно считать семантическим, и я считаю, что он обычно реализуется с помощью семантической проверки, но во многих производных C lvalue можно определить синтаксически. Такие определения недвусмысленны, но они часто не поддаются разбору грамматики сверху вниз, и они могут создавать сложности даже для восходящей грамматики. Выполнение проверочного анализа - это простое решение.
Если вы действительно хотите, чтобы различать операторы присваивания из утверждений выражения, то вы действительно столкнулись с проблемой отказа предсказания (не неоднозначности), если вы используете сверху вниз разбор техники, такие как рекурсивный спуск. Поскольку грамматика не является двусмысленной, простым решением является использование генератора парсера LALR (1), такого как bison/yacc, который не имеет проблем с анализом такой грамматики, поскольку он не требует раннего решения относительно того, какой тип утверждения разобран. В целом использование генераторов парсеров LALR (1) или даже GLR упрощает реализацию парсера, позволяя вам указывать грамматику в форме, которая легко читается и соответствует синтаксическому анализу. (Например, парсер LALR (1) может обрабатывать лево-ассоциативные операторы естественным образом, в то время как грамматика LL (1) может производить только право-ассоциативные разборки и поэтому требует какой-то реконструкции дерева синтаксиса.)
A рекурсивный спуск парсер - это компьютерная программа, а не грамматика, и ее выразительность, таким образом, не ограничена формальными ограничениями грамматик LL (1). Это и сила, и слабость: сила в том, что вы можете найти решения, которые не ограничены ограничениями грамматик LL (1); слабость заключается в том, что гораздо сложнее (даже, иногда, невозможно) извлечь ясное утверждение о точном синтаксисе языка. Эта сила, например, позволяет рекурсивным грамматикам спуска обрабатывать левую ассоциативность более или менее естественным образом, несмотря на ограничение, упомянутое выше.
Если вы хотите спуститься по этой дороге, то решение достаточно просто. У вас будет какая-то функция:
/* This function parses and returns a single expression */
Node expr() {
Node left = value();
while (true) {
switch (lookahead) {
/* handle each possible operator token. I left out
* the detail of handling operator precedence since it's
* not relevant here
*/
case OP_PLUS: {
accept(lookahead);
left = MakeNode(OP_PLUS, left, value());
break;
}
/* If no operator found, return the current expression */
default:
return left;
}
}
}
Это легко изменить, чтобы иметь возможность анализировать выражения и выражения. Во-первых, реорганизуйте функцию так, чтобы она анализировала «остаток» выражения, учитывая первый оператор. (. Единственное изменение является новый прототип и удаление первой строки в теле)
/* This function parses and returns a single expression
* after the first value has been parsed. The value must be
* passed as an argument.
*/
Node expr_rest(Node left) {
while (true) {
switch (lookahead) {
/* handle each possible operator token. I left out
* the detail of handling operator precedence since it's
* not relevant here
*/
case OP_PLUS: {
accept(lookahead);
left = MakeNode(OP_PLUS, left, value());
break;
}
/* If no operator found, return the current expression */
default:
return left;
}
}
}
При том, что в месте, это просто реализовать как expr и stmt:
Node expr() {
return expr_rest(value());
}
Node stmt() {
/* Check lookahead for statements which start with
* a keyword. Omitted for simplicity.
*/
/* either first value in an expr or target of assignment */
Node left = value();
switch (lookahead) {
case OP_ASSIGN:
accept(lookahead);
return MakeAssignment(left, expr())
}
/* Handle += and other mutating assignments if desired */
default: {
/* Not an assignment, just an expression */
return MakeExpressionStatement(expr_rest(left));
}
}
}
Ваш вопрос отсутствует только одна важная деталь: какую грамматику вы ищете? И какой инструмент вы используете для генерации парсера? –
Ну, я не уверен, какие типы грамматик есть (мы говорили только об EBNF, контекст бесплатно). Для этого я не буду использовать автоматизированный инструмент. – Dave
Хорошо, а какой парсер вы реализуете для своей контекстно-свободной грамматики? –