Как решить эту неоднозначную грамматику?

Question

Я написал эту грамматику:

expr        : multExpr ( ('+' | '-') multExpr )*;
multExpr    : atom ( ('*' | '/') atom )*;
atom    : INT | FLOAT | ID | '(' expr ')';
condition   : cond ('or' cond)*;
cond    : c1 ('and' c1)*;
c1      : ('not')? c2;
c2      : '(' condition ')' | boolean;
boolean : expr (relop expr | ²) | 'true' | 'false';
relop   : '<' | '<=' | '>' | '>=' | '==' | '!=';

Я опустил правила лексера для INT, FLOAT, ID, как это очевидно.

Проблема в правиле c2, она неоднозначна из-за '(', я не смог найти решение, можете ли вы предложить мне решение?

Answer 1

Почему бы просто не сделать:

expr      : orExpr; 
orExpr    : andExpr ('or' andExpr)*;
andExpr   : relExpr ('and' relExpr)*;
relExpr   : addExpr (relop addExpr)?;
relop     : '<' | '<=' | '>' | '>=' | '==' | '!=';
addExpr   : multExpr (('+' | '-') multExpr)*;
multExpr  : unaryExpr (('*' | '/') unaryExpr)*;
unaryExpr : 'not'? atom;
atom      : INT | FLOAT | ID | 'true' | 'false' | '(' expr ')';

Унарный not обычно имеет более высокий приоритет, чем вы пытаетесь сделать сейчас.

Это позволит использовать выражения типа 42 > true, но проверка такой семантики может происходить, когда вы проходите AST / дерево.

РЕДАКТИРОВАТЬ

Вход "not(a+b >= 2 * foo/3.14159) == false" теперь будет анализироваться следующим образом (игнорируяпробелы):

И если вы установите выход AST и смешаете некоторые операторы перезаписи дерева (^ и !):

options {
  output=AST;
}

// ...

expr      : orExpr; 
orExpr    : andExpr ('or'^ andExpr)*;
andExpr   : relExpr ('and'^ relExpr)*;
relExpr   : addExpr (relop^ addExpr)?;
relop     : '<' | '<=' | '>' | '>=' | '==' | '!=';
addExpr   : multExpr (('+' | '-')^ multExpr)*;
multExpr  : unaryExpr (('*' | '/')^ unaryExpr)*;
unaryExpr : 'not'^ atom | atom;
atom      : INT | FLOAT | ID | 'true' | 'false' | '('! expr ')'!;

Вы получите:

Answer 2

Ваша проблема проистекает из того факта, что '(' может быть началом либо первой альтернативы для c2, либо последней альтернативы для atom. Просто, например, с учетом ввода типа ((x+y) > (a+b)), первого открытияparen - это начало c2, а второе - начало atom. [edit: И синтаксический анализатор не имеет указания, по какому пути идти дальше, до какой-то произвольной точки позже - например, он не можетЗнайте, что первое открытое имя - это начало c2, пока оно не встретит >. Например, если бы вместо этого было *, то оба открывающих скобки были бы началами atom с.]

Один из возможных способов справиться с этим - объединить правила для арифметических и логических выражений, поэтому у вас есть только одно правило с '(' expression '), а expression может быть арифметическим или логическим. Это часто, однако,побочным эффектом является довольно свободная типизация с относительно свободным преобразованием между арифметическими и булевыми выражениями (по крайней мере, на уровне парсера - вы можете затем использовать enforce типы жестко, как вам нравится в семантике).

Редактировать: Например, в Pascal правила запускаются примерно так (упрощенно):

expression: simple_expression ( rel_op simple_expression )*

simple_expression: ( '+' | '-')? term ( ('+' | '-' | 'or' ) term )*

term: factor ( ( '/' | '*' | 'div' | 'mod' | 'and') factor )*

factor: constant | variable | function_call | '(' expression ')' | 'not' factor

Answer 3

Один из способов решения этой проблемы - разделить ее на два набора правил лексера и последовательно применить их к входным данным (один для математических операций, другой для логических).

Answer 4

Не могли бы вы определить c1 следующим образом?

('not')? (('(' condition ')') | boolean)