Как уже указывалось в комментариях, ваш метод C известен как рекурсивный спуск и является путем к go, но не может обрабатывать левую рекурсию. Так как с этим справиться?
Вы можете переписать свою грамматику, чтобы удалить левую рекурсию, и у вас получится что-то вроде этого:
<Expression> -> <Term> <ExpressionTail>
<ExpressionTail> -> + <Term> <ExpressionTail> | - <Term> <ExpressionTail> | ε
Если вы прямо перевели это в код вы бы получили что-то вроде:
Expression* parseExpression() {
Expression* operand = parseTerm();
ExpressionTail* tail = parseExpressionTail();
return new Expression(operand, tail);
}
ExpressionTail* parseExpressionTail() {
if (current token is '+' or '-') {
char operator = current token;
move to next token;
Expression* operand = parseTerm();
ExpressionTail* tail = parseExpressionTail();
return new OperatorExpressionTail(operator, operand, tail);
} else {
return new EmptyExpressionTail();
}
}
Однако есть несколько проблем с этим:
Прежде всего, переписанная грамматика определенно менее читаема, чем оригинал. Конечно, вы могли бы избежать этой проблемы, документировав одну версию грамматики и реализовав другую, но структура кода все еще содержит ту же сложность. Наличие отдельных parseFooTail() методов для каждого уровня леворекурсивных определений, безусловно, может раздражать и загромождать код.
Однако самое важное предостережение - это структура дерева, которое мы генерируем: Приведенный выше код сгенерированного дерева напрямую основан на переписанной грамматике и не будет выглядеть так, как оригинальная грамматика. С этим деревом неудобно работать, потому что мы даже не можем напрямую получить доступ к нужным операндам оператора - вместо этого мы должны перебирать хвостовые указатели. Нам нужно создать дерево, в котором каждое выражение инфикса представляется в виде узла с оператором и двумя операндами, как в исходной грамматике.
Для этого мы могли бы заменить return new Expression(operand, tail) кодом, который перебирает хвост и строит из этого правильное дерево выражений. Или мы могли бы полностью избавиться от структуры ExpressionTail и сгенерировать это дерево непосредственно внутри parseExpressionTail, передав левый операнд в качестве аргумента:
Expression* parseExpression() {
Expression* operand = parseTerm();
return parseExpressionTail(operand);
}
Expression* parseExpressionTail(Expression* leftOperand) {
if (current token is '+' or '-') {
char operator = current token;
move to next token;
Expression* rightOperand = parseTerm();
Expression* newLeftOperand = new InfixExpression(operator, leftOperand, rightOperand);
return parseExpressionTail(newLeftOperand);
} else {
return leftOperand;
}
}
Теперь получится дерево, которое нам нужно , но это все еще не особенно приятно читать. Вы можете заметить, что parseExpressionTail теперь является хвост-рекурсивным, что означает, что его можно легко переписать как al oop. Как только мы это сделаем, функция больше не будет напрямую рекурсивной, поэтому ее можно вставить в parseExpression. Итак, давайте сделаем это:
Expression* parseExpression() {
Expression* leftOperand = parseTerm();
while (current token is '+' or '-') {
char operator = current token;
move to next token;
Expression* rightOperand = parseTerm();
expression = new InfixExpression(operator, leftOperand, rightOperand);
}
return leftOperand;
}
Если мы оглянемся на грамматику, мы могли бы заметить, что expressionTail лучше всего можно описать как «соответствует шаблону (+ | -) <Term> ноль или более раз». Поэтому, если мы введем оператор повторения (например, * в регулярных выражениях или {}, используемый в EBNF) в нашу грамматическую нотацию, мы можем переписать его как
<Expression> -> <Term> ((+ | -) <Term>)*
или
<Expression> -> <Term> {(+ | -) <Term>}
в зависимости от того, какую запись вы предпочитаете. Теперь, если вы пишете свою грамматику с использованием этой нотации в первую очередь, вы можете придумать приведенный выше код более прямым способом, чем сначала записав его рекурсивно, а затем переписав хвостовую рекурсию: вы можете написать свою грамматику, используя операторы повторения где бы это ни имело смысл, а затем просто используйте while l oop везде, где вы видите оператор повторения при переводе грамматики в код.
Теперь мы нашли совершенно выполнимый способ анализа выражений инфиксов в синтаксический анализатор с рекурсивным спуском, но наличие отдельного метода parseFoo для каждого уровня приоритета может все еще стать раздражающим, если у вас много уровней приоритета, и то же самое касается наличия нетерминала в грамматике для каждого уровня приоритета. На уровне грамматики мы можем решить эту проблему, просто записав грамматику двусмысленно, как это:
<Expression> -> <Expression> + <Expression>
| <Expression> - <Expression>
| <Expression> * <Expression>
| <Expression> / <Expression>
| <Factor>
Затем вы можете устранить неоднозначность, перечислив приоритет каждого оператора и ассоциативность отдельно от грамматики. Для кода синтаксического анализатора мы хотели бы сделать то же самое: иметь таблицу, содержащую каждый оператор, его приоритет и ассоциативность, а затем иметь единственную функцию, которая может анализировать все выражения инфикса, просто просматривая эту таблицу.
Способ достижения sh, который заключается в использовании рекурсивного спуска для всего остального, но с использованием специализированного алгоритма внутри функции, которая анализирует инфиксные выражения, такого как восхождение по приоритетам (см. это сообщение в блоге Эли Бендерского и / или объяснение в Википедии ).