Написание рекурсивного потомка парсера для моей грамматики
Я должен построить выражение, используя Recursive Descendent Parser Builder.
Вот моя грамматика:
----RULES----
<cond> → <termb> [OR <termb>]*
<termb>→<factb>[AND <factb>]*
<factb>→<expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → [PLUS | MINUS] <term> [(PLUS <term>) | (MINUS <term>)]*
<term> → <termp> [(MULT <termp>) | (DIV <termp>) | (REM <termp>)]*
<termp> → <fact> [POWER <fact>]*
<fact> → ID | NUM | OPAR1 <expr> CPAR1
----TERMINALS----
ID → ("A" | ... | "Z" | "a" | ...| "z") [("A"| ... | "Z" | "a" | ...| "z" | "0" | ... | "9")]*
NUM → ("0" | ... | "9") [("0" | ... | "9")]*
OPAR → "("
CPAR → ")"
OPAR1 → "["
CPAR1 → "]"
RELOP → EQ | NEQ | GT | GE | LT | LE
EQ → "= ="
NEQ → "!="
GT → ">"
GE → ">="
LT → "<"
LE → "<="
POWER → "^"
DIV → "/"
REM → "%"
MULT → "*"
MINUS → "−"
PLUS → "+"
AND → “and” or “&&”
OR → “or” or “||”
NOT → “not” or “!”
Теперь у меня есть составная структура с одним классом для каждого терминала, и я пытаюсь построить ее, следуя правилам приведенной выше грамматики.
Идея состоит в том, что мне нужен метод для каждого правила грамматики, и каждый из этих методов должен строить свою часть дерева выражений.
Хотя он работает с более простой грамматикой (например, грамматика, которая допускает только логические выражения), у меня есть некоторые проблемы с этим.
Основная проблема исходит от expr Правило, которое заставляет меня работать даже с унарными версиями моих + и -, позволяя такие выражения +3-4, Это требует, чтобы я выяснил, когда операнд должен считаться унарным, а когда - двоичным!
Вот код моего класса Builder. Пожалуйста, обратите внимание, что что-то на итальянском, но я объяснил ВСЕ, даже мои проблемы, используя комментарии. Также обратите внимание, что есть одна строка, в которой я использовал псевдокод, так что эта НЕ компилируется!
package espressioniCondizionali;
import espressioniCondizionali.espressioni.*;
/**
*
* @author Stefano
*/
public class Builder6 {
/**
* This one is used just to parse the input String.
* It has a prossimoSimbolo() method (something like a nextSymbol()) that returns a String with the next Symbol in the String
*/
private GestoreInput gestoreInput;
/**
* Espressione is the Composite structure that represents and expression
*/
private Espressione root = null;
private String symbol = null;
public Builder6(GestoreInput gestoreInput) {
this.gestoreInput = gestoreInput;
}
public Espressione build() {
buildCond();
return root;
}
private void buildCond() {
buildTermb();
//I'm unsing a class named Simboli that holds every terminal symbol of my grammar. Symbol names are the same defined in the grammar.
while (symbol.equalsIgnoreCase(Simboli.OR1) || symbol.equalsIgnoreCase(Simboli.OR2)) {
Or or = new Or();
or.setLeft(root);
buildTermb();
or.setRight(root);
root = or;
}
}
private void buildTermb() {
buildFactb();
while (symbol.equalsIgnoreCase(Simboli.AND1) || symbol.equalsIgnoreCase(Simboli.AND2)) {
And and = new And();
and.setLeft(root);
buildFactb();
and.setRight(root);
root = and;
}
}
private void buildFactb() {
buildExpr();
if (symbol.equalsIgnoreCase(Simboli.EQ) || symbol.equalsIgnoreCase(Simboli.NEQ) || symbol.equalsIgnoreCase(Simboli.GT) || symbol.equalsIgnoreCase(Simboli.LT) || symbol.equalsIgnoreCase(Simboli.LE) || symbol.equalsIgnoreCase(Simboli.GE)) {
Operatore op = null;
switch (symbol) {
case Simboli.EQ: {
op = new Eq();
break;
}
case Simboli.NEQ: {
op = new Neq();
break;
}
case Simboli.GT: {
op = new Gt();
break;
}
case Simboli.GE: {
op = new Ge();
break;
}
case Simboli.LT: {
op = new Lt();
break;
}
case Simboli.LE: {
op = new Le();
break;
}
default: {
//Symbol not recognized, abort!
throw new RuntimeException("\"" + symbol + "\" non è un simbolo valido.");
}
}
op.setLeft(root);
buildExpr();
op.setRight(root);
root = op;
} else if (symbol.equalsIgnoreCase(Simboli.NOT1) || symbol.equals(Simboli.NOT2)) {
Not not = new Not();
buildFactb();
not.setRight(root);
root = not;
} else if (symbol.equalsIgnoreCase(Simboli.OPAR)) {
buildCond();
if (!symbol.equalsIgnoreCase(Simboli.CPAR)) { //If there's no closgin square bracket it means that our expression is not well formed
throw new RuntimeException("Espressione non valida. Attesa una \")\", trovato \"" + symbol + "\"");
}
}
}
private void buildExpr() {
Operatore op = null;
if (symbol != null) { //Let's check if our expression starts with a + or a -
if (symbol.equalsIgnoreCase(Simboli.PLUS)) {
op = new Plus();
} else if (symbol.equalsIgnoreCase(Simboli.MINUS)) {
op = new Minus();
}
}
buildTerm();
//If our op is still null, we didn't found a + or a - so our operand will be a binary one
//If op != null, our + or - is unary and we've got to manage it! A unary operand doesn't have a left son!
if (op != null) {
op.setRight(root);
root = op;
}
//Since we can have something like -3+2+s-x we've got to check it
while (symbol.equalsIgnoreCase(Simboli.PLUS) || symbol.equalsIgnoreCase(Simboli.MINUS)) {
Operatore op1 = null; //We define a new Operatore that will be a + or a -
switch (symbol) {
case Simboli.PLUS: {
op1 = new Plus();
break;
}
case Simboli.MINUS: {
op1 = new Minus();
break;
}
}
/*
* Here comes a BIG problem. We used the first if/else to check if
* our unary operand was at the beginning of the string, but now
* we've got to see if our current operand is either binary or
* unary! That's because we can have both a==-1+d and a==3-1+d. In
* the first case, the - is unary, while is binary in the second.
* So, how do we choose it?
*
* EXAMPLE : (-a>2 || -b-12>0)
* This one will be evaluated to -a > 2 || -12 > 0 that's clearly wrong!
* -b is missing before -12. That's because the -12 is used as unary
* and so it won't have a left child (the -b part)
*/
//--PSEUDOCODE
if (op1 is not unary) {
op1.setLeft(root);
}
//--END PSEUDOCODE
//CURRENT IMPLEMENTATION OF THE PSEUDOCODE PART
if (root != null && (root.getClass().equals(Num.class) || root.getClass().equals(Id.class))) { //It is binary if the previous value is a constant or a variable but not if it is an operand!
op1.setLeft(root);
}
//END OF CURRENT IMPLEMENTATION OF THE PSEUDOCODE PART
//Setting the right child must be done in both cases
buildTerm();
op1.setRight(root);
root = op1;
}
}
private void buildTerm() {
buildTermp();
while (symbol.equalsIgnoreCase(Simboli.MULT) || symbol.equalsIgnoreCase(Simboli.DIV) || symbol.equalsIgnoreCase(Simboli.REM)) {
Operatore op = null;
switch (symbol) {
case Simboli.MULT: {
op = new Mult();
break;
}
case Simboli.DIV: {
op = new Div();
break;
}
case Simboli.REM: {
op = new Rem();
break;
}
}
op.setLeft(root);
buildTermp();
op.setRight(root);
root = op;
}
}
private void buildTermp() {
buildFact();
while (symbol.equalsIgnoreCase(Simboli.POWER)) {
Power p = new Power();
p.setLeft(root);
buildFact();
p.setRight(root);
root = p;
}
}
private void buildFact() {
symbol = gestoreInput.prossimoSimbolo();
if (symbol.equalsIgnoreCase(Simboli.OPAR1)) { //Sottoespressione
buildExpr();
if (!symbol.equalsIgnoreCase(Simboli.CPAR1)) { //Se non c'è una parentesi chiusa vuol dire che l'espressione non valida
throw new RuntimeException("Espressione non valida. Attesa una \"]\", trovato \"" + symbol + "\"");
}
} else if (symbol.matches("[A-Za-z][A-Za-z | 0-9]*")) { //Nome di una variabile!
root = new Id(symbol);
symbol = gestoreInput.prossimoSimbolo();
} else if (symbol.matches("[0-9]*")) { //E' una costante!
root = new Num(symbol);
symbol = gestoreInput.prossimoSimbolo();
}
}
}
Известные проблемы:
(a<=b && c>1) || a==4 оценивает a <= b && c > 1
a==[-4] оценивает a == a - 4
-4+3>c-2 оценивает +3 > c - 2
Вероятно, есть еще некоторые ошибки, но они являются наиболее распространенными.
Итак, вот мои вопросы:
Прежде всего, вы думаете, что этот код имеет некоторые логические проблемы? Я имею в виду, это делает то, что говорит грамматика, или я сделал что-то действительно неправильно? Как бы вы исправить expr способ заставить его работать с одинарными и двоичными + или - операндами?
Если мой код полностью неверен, есть ли кто-нибудь, кто может помочь мне написать рабочую версию? Как видно из названия класса, это шестая реализация, которую я написал, и я действительно не знаю, что делать дальше!
Благодарю.
1 ответ
Шаг 1: Подумайте о грамматике по-другому
Я думаю, что у вас есть проблемы с реализацией вашего парсера рекурсивного спуска, потому что ваша грамматика очень сложна. Произвольная итерация, представленная [ ... ]* формы трудно обернуть голову вокруг. Попробуйте думать об этом так:
<cond> → <termb> <cond-tail>
<cond-tail> → OR <termb> <cond-tail> | EPSILON
<termb> → <factb> <termb-tail>
<termb-tail> → AND <factb> <termb-tail> | EPSILON
<factb> → <expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → <unary-op> <term> <expr-tail>
<unary-op> → PLUS | MINUS | EPSILON
<expr-tail> → ((PLUS <term>) | (MINUS <term>)) <expr-tail> | EPSILON
<term> → <termp> <term-tail>
<term-tail> → ((MULT <termp>) | (DIV <termp>) | (REM <termp>)) <term-tail> | EPSILON
<termp> → <fact> <termp-tail>
<termp-tail> → POWER <fact> <termp-tail> | EPSILON
<fact> → ID | NUM | OPAR1 <expr> CPAR1
EPSILON → ""
Эта грамматика такая же, как вы опубликовали, но я разделил [ ... ]* правила в свои собственные нетерминалы. Для этого я добавил EPSILON правило, которое позволяет нетерминалу совпадать на "" (пустая строка). Это в основном то же самое, что и ваш [ ... ] правила, которые могут или не могут действительно соответствовать чему-то. Правило epsilon - это всего лишь последняя альтернатива, которая гласит: "Прекратите пытаться сопоставить сейчас". Например, если вы в настоящее время разбираете для cond-tail тогда вы бы сначала проверить на OR на входе. Если вы не видите OR Затем вы переходите к следующей альтернативе, которая EPSILON, Это означает, что больше нет OR условия в этой условной цепочке, так что это cond-tail соответствует пустой строке.
Вы можете еще больше упростить грамматику, сгруппировав операторы в expr-tail а также term-tail:
<cond> → <termb> <cond-tail>
<cond-tail> → OR <termb> <cond-tail> | EPSILON
<termb> → <factb> <termb-tail>
<termb-tail> → AND <factb> <termb-tail> | EPSILON
<factb> → <expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → <unary-op> <term> <expr-tail>
<unary-op> → PLUS | MINUS | EPSILON
<expr-tail> → (PLUS | MINUS) <term> <expr-tail> | EPSILON
<term> → <termp> <term-tail>
<term-tail> → (MULT | DIV | REM) <termp> <term-tail> | EPSILON
<termp> → <fact> <termp-tail>
<termp-tail> → POWER <fact> <termp-tail> | EPSILON
<fact> → ID | NUM | OPAR1 <expr> CPAR1
EPSILON → ""
Теперь вам нужно вернуться и реорганизовать свое решение, чтобы добавить новые методы для каждого из новых правил. (Вместо этого вы можете оставить код новых правил в исходных правилах, но, по крайней мере, четко пометьте различные разделы комментариями, чтобы помочь вам отслеживать, какие части кода делают что.)
Теперь должно быть очень очевидно, в каких случаях + а также - унарные операторы, потому что они будут проанализированы вашим новым buildUnaryOp метод (соответствующий новому unary-op правило в грамматике).
Что касается нового *-tail правила, вы можете реализовать их строго рекурсивно, или вы можете реализовать их с помощью цикла внутри тела функции, если вы беспокоитесь о том, что ваш стек будет вытеснен из длинных выражений.
Шаг 2: Исправьте отслеживание вашего состояния
Это ваша главная проблема прямо здесь:
/**
* Espressione is the Composite structure that represents and expression
*/
private Espressione root = null;
private String symbol = null;
Вы используете поля уровня экземпляра для хранения состояния вашего анализатора рекурсивного спуска. Я никогда не видел парсер рекурсивного спуска, методы которого имеют тип возврата void- по крайней мере, если на самом деле создается абстрактное синтаксическое дерево. Пример в Википедии имеет void return-types, но это потому, что все, что он делает - проверяет ввод и отбрасывает результаты, а не строит AST из ввода.
Поскольку вы сохраняете свое состояние в полях уровня класса, поле перезаписывается при каждом вызове одного из buildExpr() и вы теряете свои данные. Это моя теория в любом случае. Вы можете проверить это, сделав длинную строку exprкак "1+2+3+4+5", Это должно закончить тем, что бросило все условия на фронт.
Я бы порекомендовал построить парсер функционально (без использования каких-либо .set*() методы), где каждый build*() Метод возвращает проанализированный узел из AST. Это будет включать в себя изменение всех ваших конструкторов для принятия дочерних узлов. Вы все еще можете использовать мутацию вместо этого, если это более понятно для вас. Вот переделал buildCond:
private Espressione buildCond() {
Espressione leftHandSide = buildTermb();
if (symbol.equalsIgnoreCase(Simboli.OR1) || symbol.equalsIgnoreCase(Simboli.OR2)) {
Or or = new Or();
or.setLeft(leftHandSide);
or.setRight(buildTermb());
return or;
}
return leftHandSide;
}
Вот что нового build() будет выглядеть так:
public Espressione build() {
return buildCond();
}
Если вы переделаете остальную часть своего кода, чтобы построить дерево таким образом (вместо того, чтобы использовать поля уровня экземпляра для хранения вашего состояния), тогда он должен работать намного лучше.
Удачи!