Уменьшить / уменьшить конфликт с нетипизированными переменными и вызовами функций

Question

Я хочу создать парсер для динамически типизированного языка.

в моем файле бизонов у меня есть правило для runtimetyped который является именем переменной или вызовом функции.

runtimetyped : T_ID { $$ = create_identifier($1); }
             | call { $$ = $1; }
             ;

я также хочу сделать некоторые базовые проверки типов во время компиляции. например, я не хочу позволять такие вещи, как

x = "string" + 42 <= true;

в исходном коде я хочу создать ошибку времени компиляции.

но такие вещи, как

s = "string";
i = 42;
b = true;
x = s + i <= b;

должен выдавать ошибку во время выполнения.

Мой подход состоял в том, чтобы иметь разные выражения в грамматике:

expression : bool_expression
           | math_expression
           | string_expression
           ;

и любой из них expressions создаются terms, factors, и так далее.
factor всегда может быть runtimetyped что приводит к reduce/reduce ошибки.

math_factor : numeric_literal                   { $$ = $1; }
            | runtimetyped                      { $$ = $1; }
            | T_LPAREN math_expression T_RPAREN { $$ = $2; }
            ;

bool_factor : T_BOOL                            { $$ = create_bool($1); }
            | runtimetyped                      { $$ = $1; }
            | compare                           { $$ = $1; }
            | T_LPAREN bool_expression T_RPAREN { $$ = $2; }
            ;

string_expression : T_STRING                                    { $$ = $1; }
                  | runtimetyped                                { $$ = $1; }
                  | string_expression T_STROP string_expression { $$ = create_expression($2, $1, $3); }
                  ;

я запускаю это с bison -v parser.y,

Может ли кто-нибудь дать мне подсказку о том, как этот конфликт может быть разрешен и / или что именно вызывает конфликт.

заранее спасибо.

Answer 1

Лучший способ проверки типов во время компиляции - выполнить анализ по AST. Чтобы предоставить точные сообщения об ошибках, вам нужно будет хранить информацию о местоположении для каждого токена в AST, но это, как правило, полезно в любом случае.

Преимущество семантического анализа после построения AST состоит в том, что код намного чище, потому что он не смешивает семантический анализ с другими задачами. Это также позволяет вам использовать больше информации, такой как объявления типов. Однако, если вы не хотите этого делать, вы можете также выполнить проверку типов в действиях для каждого производства. Это распространяет семантический анализ на всю грамматику, которую ИМХО труднее понять, проверить, протестировать и поддерживать. Тем не менее, это возможно.

Перевод семантической проверки в синтаксическую ошибку - действительно худший способ сделать что-либо. Это излишне усложняет грамматику и усложняет генерирование хороших сообщений об ошибках, потому что ошибка типа действительно не является синтаксической ошибкой, и большинство людей, пытающихся написать код на вашем языке, будут озадачены, получив синтаксическую ошибку для синтаксически правильного, но семантически бессмысленная конструкция.

Тем не менее, это возможно. Тем не менее, вы должны быть очень осторожны, чтобы избежать грамматических двусмысленностей, которые обычно проявляются в уменьшении / уменьшении конфликтов, и это именно то, что вы видите. (Вы не предоставили достаточно грамматики для точной диагностики проблемы, но вы, вероятно, можете сделать это самостоятельно, обработав грамматику -v флаг для bison а затем исследуя полученные .output файл, который покажет вам состояния, в которых есть конфликты.)

Наиболее вероятной причиной конфликтов является разрешение единичных производств в контексте, когда оба x_expression а также y_expression может быть возможно (не глядя на жетон предпросмотра). Здесь вам может понадобиться выполнить одно из произведений x_expression: x_factor или же y_expression: y_factorЭто, в свою очередь, означает, что вам может понадобиться один из x_factor: runtimetyped или же y_factor: runtimetyped и это может быть невозможно сделать это определение. (Это один из случаев, когда LALR(1) объединение государств может создать "загадочный" конфликт.)