Отладка грамматики CUP - PullRequest
Новая
       50

Отладка грамматики CUP

0 голосов
/ 11 мая 2018

Я застрял при отладке грамматики CUP.

Итак, у меня есть следующая грамматика в CUP: 

/* Integer operators */
precedence left SUM_OP, SUBS_OP;
precedence left PROD_OP, DIV_OP;

/* Boolean operators */
precedence left EQ_OP, LT_OP, GT_OP, LET_OP, GET_OP;
precedence left OR_OP;
precedence left AND_OP;

start with statements;

statements ::= statement:s 
             | statement:s SEPARATOR
             | SEPARATOR // Empty statement
             | statement:s SEPARATOR statements:ss 
             ;

statement  ::= IF expression:e SEPARATOR statement:s
             | IF expression:e statement:s
             | IF expression:e SEPARATOR then_statement:then ELSE SEPARATOR statement:els 
             | IF expression:e then_statement:then ELSE SEPARATOR statement:els 
             | IF expression:e SEPARATOR then_statement:then ELSE statement:els 
             | IF expression:e then_statement:then ELSE statement:els 
             | WHILE expression:e SEPARATOR statement:s
             | WHILE expression:e statement:s
             | non_if_statement:s
             ;

then_statement ::= IF expression:e SEPARATOR then_statement:then ELSE SEPARATOR then_statement:els 
                   | IF expression:e then_statement:then ELSE SEPARATOR then_statement:els 
                   | IF expression:e SEPARATOR then_statement:then ELSE then_statement:els 
                   | IF expression:e then_statement:then ELSE then_statement:els 
                   | WHILE expression:e SEPARATOR then_statement:s
                   | WHILE expression:e then_statement:s
                   | non_if_statement:s
                   ;

non_if_statement ::= START_BLOCK statements:s END_BLOCK
                   | declaration:d
                   | assignment:a
                   ;

// The statement vs then_statement is for disambiguation purposes
// Solution taken from http://goldparser.org/doc/grammars/example-if-then-else.htm

/* Variable manipulation statements */
declaration ::= type:t IDENTIFIER:id 
              | type:t IDENTIFIER:id ASSIGN_OP expression:rhs 
              ;

assignment  ::= variable:lhs ASSIGN_OP expression:rhs
              ;

/* Variable manipulation auxiliar sintactic elements */
type       ::= T_INT 
             | T_BOOL 
             | type:t T_ARRAY 
             ;

variable   ::= IDENTIFIER:id 
             | variable:id LBRACKET expression:idx RBRACKET
             ;

/* Integer or bool expressions */
expression ::= variable:v 
             | LPAREN expression:e RPAREN

          // Int expressions
             |  INTEGER_LITERAL:c 
             | expression:op1 SUM_OP expression:op2 
             | expression:op1 SUBS_OP expression:op2 
             | expression:op1 PROD_OP expression:op2 
             | expression:op1 DIV_OP expression:op2 

           // Bool expressions
             | BOOL_LITERAL:c
             | expression:op1 OR_OP expression:op2 
             | expression:op1 AND_OP expression:op2 
             | NOT_OP expression:op1 
             | expression:op1 EQ_OP expression:op2 
             | expression:op1 LT_OP expression:op2 
             | expression:op1 GT_OP expression:op2 
             | expression:op1 LET_OP expression:op2 
             | expression:op1 GET_OP expression:op2 
             ;

Лексер подает следующие токены в анализатор CUP: 

 int id:i = intLiteral ;    
 { 
     if id:i == intLiteral id:i = intLiteral ;
 } 


 while id:i < intLiteral ;
 { 
     id:i = id:i + intLiteral ;
 } 
 if id:i <= intLiteral ;    
 { 
     bool id:a ;

     bool id:b = boolLiteral ;
 } 
 else ;
 { 
     int id:j = intLiteral ;
 } 
 if id:i >= intLiteral ;
 { 
     id:i = id:i - intLiteral ;
     { 
         id:i = intLiteral + intLiteral ;

     } 
 } 
 else if id:i > intLiteral id:i = intLiteral ;

 else id:i = intLiteral

(где ; - SEPARATOR и { } - блокировать блоки.

Когда я запускаю его, я получаю следующий вывод: 

 int 
 id:i
type ::= T_INT
 = 
 intLiteral 
 ;

expression ::= INTEGER_LITERAL
declaration ::= type IDENTIFIER ASSIGN_OP expression
non_if_statement ::= declaration
statement ::= non_if_statement
 { 
 if 
 id:i
 == 
variable ::= IDENTIFIER
expression ::= variable
 intLiteral 
 id:i
expression ::= INTEGER_LITERAL
expression ::= expression EQ_OP expression
 = 
variable ::= IDENTIFIER
 intLiteral 
 ;

expression ::= INTEGER_LITERAL
assignment ::= variable ASSIGN_OP expression
non_if_statement ::= assignment
statement ::= non_if_statement
statement ::= IF expression statement
 } 
statements ::= statement SEPARATOR
 while 
Error in line 7, column 1 : Syntax error
Error in line 7, column 1 : Couldn't repair and continue parse

(строки с одним словом представляют вызов лексера, который привел к печати токена. Строки с правилом CUP представляют сопоставляемое правило. Строка 7 - это строка с оператором while.)

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

Однако я не понимаю, почему блоки не анализируются правильно.

Есть идеи, в чем может быть проблема или как провести дальнейшие проверки?

РЕДАКТИРОВАТЬ: В случае, если вам нужна деталь, которую я мог бы опустить, чтобы ответить, полный код доступен в это репо

1 Ответ

0 голосов
/ 11 мая 2018

То, как ваша грамматика использует точки с запятой, немного неортодоксально.И это доставляет вам неприятности.

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

while i < 3; i = i + 1;   // ex. 1
while i < 3 i = i + 1;    // ex. 2

, но вы не можете написать 

 i = 2 j = 3              // ex. 3

, даже если это не более или менее двусмысленно, чем ex.2 выше.

Синтаксис без точки с запятой выглядит менее странно с блоками: 

while i < 3;  { i = i + 1;  } // ex. 4
while i < 3 { i = i + 1;  }  // ex. 5
{ i = 2 } { j = 3 }            // ex. 6 Still illegal

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

{ i = 2 } ; { j = 3 }            // ex. 7

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

...