Как определить синтаксис, который использует несколько черточек для вложенных инструкций "если"?

Question

Я пытаюсь создать синтаксический анализатор в Java (используя CUP), который мог бы распознать этот кусок кода:

if ¿b? then
~ a = 2;
~ if ¿b && c? then
~ ~ a = 3;
else
~ a = 4;

Мои произведения, использованные оператором if, следующие:

Instr ::= ...
       | IF CONOP Exp:e CONCL THEN CondInstrList:l
       ...
       ;
...
CondInstrList ::= CondInstrList CondInstr
       | /*empty*/
       ;
...
CondInstr ::= CONTROLD Instr
       | CONTROLD CondInstr
       ;

где Instr обозначает инструкцию / оператор, CondInstrList обозначает Список условных инструкций, а CONTROLD обозначает Control Dash (~). (CONOP и CONCL означают состояние Open/Close)

Проблема заключается в том, что с этой грамматикой сгенерированный AST выглядит следующим образом:

if
|-condition b
|-condInstrListT
  |---asig a = 2
  |---if
      |---condition b and c
      |---condInstrListT 
      |   |---asig a = 2
      |---condInstrListF
          |---asig a = 4

и так, часть "else" связана с внутренним "if".

Я просто не знаю, как написать грамматику, которая соответствует моему языку.

Любая помощь приветствуется.

Я могу дать более подробную информацию, если это необходимо.

Answer 1

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

Вот что нужно сделать: вместо того, чтобы обрабатывать метки ~ как отдельные символы грамматики, пусть лексический анализатор превратит последовательности ~ в начале строки в токены INDENT и OUTDENT, которые будут работать в вашей грамматике так же, как работают {и} в Джава. Вы отслеживаете "текущий уровень отступа", который начинается с нуля. В начале каждой строки считайте символы ~. Для каждого ~ сверх текущего уровня отступа сгенерируйте токен INDENT и увеличьте текущий уровень отступа; для каждого ~ меньшего, чем текущий уровень отступа, сгенерируйте токен OUTDENT и уменьшите текущий уровень отступа.

Итак, ваш пример текста

if ¿b? then
~ a = 2;
~ if ¿b && c? then
~ ~ a = 3;
else
~ a = 4;

будет маркирован как:

// Indent level = 0 and no ~, so no INDENT here
[IF] [CONOP] [ID b] [CONCL] [THEN]
// Indent level = 0, one ~, so one INDENT
[INDENT]
    // Indent level = 1
    [ID a] [OP =] [CONST 2] [SEMICOLON]
    // Indent level = 1, one ~, so no INDENT here
    [IF] [CONOP] [ID b] [OP &&] [ID c] [CONCL] [THEN]
    // Indent level = 1, two ~, so one INDENT
    [INDENT]
        // Indent level = 2
        [ID a] [ASSIGN] [CONST 3] [SEMICOLON]
        // Indent level = 2, lines starts with no ~, two OUTDENTs
    [OUTDENT]
    // Indent level = 1
[OUTDENT]
//Indent level = 0
[ELSE] // No ~ at start of this line, so no INDENT
// Indent level = 0; one ~, so one INDENT
[INDENT] 
    // Indent level = 1
    [ID a] [ASSIGN] [CONST 4] [SEMICOLON]
// End-of-input.  Indent level = 1, so 1 OUTDENT
[OUTDENT]
// Done; indent level = 0;

Токены INDENT и OUTDENT будут действовать в вашей грамматике, как левые и правые скобки в Java, поэтому ваша грамматика может выглядеть примерно так:

Instr ::= ...
       | IF CONOP Exp:e CONCL THEN INDENT CondInstrList:l OUTDENT
       ...
       ;
...
CondInstrList ::= CondInstrList Instr
       | /*empty*/
       ;
...

Язык Python делает то же самое, но с пробелами вместо ~. Вы можете скачать исходники Python здесь, если вам интересно. Искать файлы Grammar\Grammar а также Parser\tokenizer.c,