Создание отдельного правила "логического выражения" для динамического языка

Question

Создание отдельного правила "логического выражения" для динамического языка

Я создаю грамматику в Bison для простого динамически типизированного языка. У меня есть "генерал" expression правило, которое несколько сродни понятию rvalue в C; выражения появляются в правой части присваивания, их также можно отправлять в функции в качестве аргументов и т. д. Далее следует значительно упрощенная версия правила:

constantExpression
    : TOK_INTEGER_CONSTANT
    | TOK_FLOAT_CONSTANT
    | stringLiteral
    ;

expression
    : constantExpression
    | identifier
    | booleanExpression
    | booleanExpression TOK_QUESTION_MARK expression TOK_COLON expression
    | TOK_LPAREN expression TOK_RPAREN
    | expression TOK_PLUS expression
    | expression TOK_MINUS expression
    ;

У меня также есть специальное правило логического выражения; логические выражения используются наиболее заметно в if заявления, но любой другой контекст, который требует двоичного значения истины, конечно, также хорошо:

booleanExpression
    : identifier
    | expression '<' expression
    | expression '<=' expression
    | expression '==' expression
    | expression '!=' expression
    | expression '>' expression
    | expression '>=' expression
    | booleanExpression '&&' booleanExpression
    | booleanExpression '||' booleanExpression
    | '!' booleanExpression
    | 'true'
    | 'false'
    ;

Проблема: очевидно, что вышеперечисленные правила страдают от множества противоречий. Идентификатор в зависимости от контекста должен быть сокращен до expression (например, в таком утверждении, как это: myVar2 = myVar1) или booleanExpression (очевидный пример: if (myBoolVar)).

Мало того, но есть и ошибки сдвига-уменьшения, связанные с тем, что booleanExpresssion сводится к expression; когда синтаксический анализатор проанализировал booleanExpressionи встречает && маркер, он может либо сдвинуться и продолжать движение, либо уменьшиться до expression, booleanExpression необходимо сократить до выражения, чтобы позволить такой код, как

conditionVar = (var1 == 5) || (var2 > 10 && var3 < 20);
if (conditionVar) { ... }

Я знаю о конфликтах сдвига и уменьшения, связанных с приоритетом операторов, здесь это не проблема, я исправил это с помощью %left правила для операторов.

Мой вопрос: как лучше всего решить эту проблему? Мои идеи либо

структурировать правила таким образом, чтобы, несмотря на конфликты, Бизон делал то, что я хочу, и игнорировал предупреждения - довольно некрасиво и немыслимо
удалить отдельный booleanExpression править и переместить все это expression - хорошо, но требует больше проверок на стадии семантического анализа; на моем языке строки неявно преобразуются в логические значения, поэтому код if ("foo") не является законным, но будет принят парсером
использовать анализатор GLR - чувствует себя немного излишним для такого простого варианта использования, но, возможно, я ошибаюсь

Что из вышеперечисленного является лучшей идеей? Есть ли другие возможности, которые я не рассматривал?

2

parsing compiler-construction grammar bison formal-languages

Источник

user1928235 09 апр '17 в 12:01

1 ответ

Решение

Другие вопросы по тегам parsing compiler-construction grammar bison formal-languages

user1566221 09 апр '17 в 15:09 2017-04-09 15:09 · Accepted Answer · 2017-04-09 15:09

Обычная мудрость такова: не пытайтесь делать семантический анализ в вашей грамматике.

Во-первых, это усложняет грамматику, даже если это возможно, как вы видели. Напротив, правила проверки типов очень просты, когда выполняются в обход дерева по AST.

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

Однако, в зависимости от точного характера вашего языка, может быть возможно выбрать золотую середину. Как правило, некоторые операторы - логические операторы и сравнения - определенно возвращают логические значения, в то время как в некоторых контекстах определенно требуются логические значения. Чтобы вы могли добавить boolean_expression нетерминальный, используется для указания того, где результаты обязательно будут булевыми, а где значения должны быть булевыми. Тогда вы могли бы вставить в свою грамматику единичное производство

 boolean_expression: expression

с семантическим действием, которое вставляет узел проверки времени выполнения в AST.

Во время семантического анализа эту проверку можно исключить, если определено, что она всегда будет успешной, или возникнет ошибка, если будет установлено, что она всегда будет неудачной. В противном случае для проверки будет в конечном итоге выдан код.

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

(В приведенных ниже примерах я показываю только один логический оператор, один оператор сравнения и один арифметический оператор. Очевидно, что реальный язык будет иметь больше каждого из них, но это не меняет представление вообще. Я также не беспокоился о пролог, который должен включать объявления приоритетов для операторов.)

program : stmt_list
stmt_list:%empty
        | stmt_list stmt
stmt    : assign
        | call
        | empty
        | while
        | '{' stmt_list '}'
assign  : IDENTIFIER '=' expr ';'
call    : expr '(' expr_list ')' ';'
        | expr '(' ')' ';'
empty   : ';'
while   : "while" '(' boolean_expr ')' stmt
expr_list
        : expr
        | expr_list ',' expr
boolean_expr
        : boolean_term
        | boolean_expr "or" boolean_expr
        | expr '<' expr
boolean_term
        : "true" | "false"
        | expr               { /* insert conversion from expr to boolean */ }

expr    : term
        | expr '+' expr
term    : INTEGER
        | IDENTIFIER
        | '(' expr ')'

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

Кроме того, приведенная выше грамматика не допускает избыточных скобок вокруг логических выражений.

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

В большинстве языков логические значения могут быть созданы в соответствии с определенными правилами из других значений; условно, значение, которое преобразуется в логическое значение true называется истинной ценностью. Это может быть очень удобно, хотя это также может быть немного опасно, если в характере принуждения слишком много широты. [Примечание 1] Чтобы контролировать ущерб, мы можем разрешить автоматическое приведение логического значения только к явно логическому контексту и никогда не разрешать автоматическое приведение логического значения к небулевому. Если вы готовы принять эти ограничения, мы все равно можем использовать грамматику в качестве инструмента для документирования логических контекстов и приведения.

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

expr: небулево выражение
boolean_exprспецифически логическое выражение; соответствующие произведения перечисляют синтаксисы, которые должны иметь логический результат.
truthy_expr: либо логическое выражение, либо не логическое выражение, которое может быть приведено к логическому выражению. Этот нетерминал используется в местах, где требуется логическое значение. [Заметка 2]
either_expr: либо логическое выражение, либо не логическое выражение в контексте, в котором любое из них может появляться без принуждения (например, присваивания и аргументы функции).

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

Кроме определения вышеупомянутых нетерминалов и их использования в различных контекстах, грамматика не сильно изменилась:

program : stmt_list
stmt_list:%empty
        | stmt_list stmt
stmt    : assign
        | call
        | empty
        | while
        | '{' stmt_list '}'
assign  : IDENTIFIER '=' either_expr ';'
call    : expr '(' expr_list ')' ';'
        | expr '(' ')' ';'
empty   : ';'
while   : "while" '(' truthy_expr ')' stmt
expr_list
        : either_expr
        | expr_list ',' either_expr

truthy_expr
        : boolean_expr
        | expr               { /* insert conversion from expr to boolean */ }

either_expr
        : boolean_expr
        | expr

boolean_expr
        : boolean_term
        | truthy_expr "or" truthy_expr
        | expr '<' expr
boolean_term
        : "true"
        | "false"
        | '(' boolean_expr ')'

expr    : term
        | expr '+' expr
term    : INTEGER
        | IDENTIFIER
        | '(' expr ')'

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

Заметки:

Схема не зависит от существования какого-либо "истинного" принуждения, но если логические значения относятся к первому классу, будут выражения, которые могут быть определены только как логические во время выполнения (логические переменные, функции, возвращающие логические значения и т. Д.). Рассмотрим проверку во время выполнения, что значение, используемое в логическом контексте, является логическим значением, чтобы быть формой принуждения к правдивости, где только true верно и только false ложно, в то время как все другие значения выдают ошибку.
Лично я полюбил ограниченные автоматические булевы принуждения. Для меня совершенно логично, что файловый объект будет ложным, если он, например, находится в состоянии ошибки, или что контейнер будет правдивым, если он не пустой. Ограничение этих преобразований явно булевыми контекстами, такими как условие в условном выражении, делает автоматическое принуждение приемлемым для меня. Но я не настаиваю на идее; если вам это не нравится, игнорируйте эту мысль.
Это не очень хорошее имя, но truthy_or_falsy_expr казалось слишком длинным и boolish_expr казалось слишком странным. Предложения приветствуются.