Извлечение рекурсии в ANTLR - PullRequest
Новая
       4

Извлечение рекурсии в ANTLR

0 голосов
/ 19 июля 2011

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

Рекурсивная грамматика во всей ее полноте: 

grammar DeadMG;

options {
    language = C;
}

ID  :   ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;

INT :   '0'..'9'+
    ;

FLOAT
    :   ('0'..'9')+ '.' ('0'..'9')* EXPONENT?
    |   '.' ('0'..'9')+ EXPONENT?
    |   ('0'..'9')+ EXPONENT
    ;

COMMENT
    :   '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
    |   '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
    ;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;

STRING
    :  '"' ( ESC_SEQ | ~('\\'|'"') )* '"'
    ;

CHAR:  '\'' ( ESC_SEQ | ~('\''|'\\') ) '\''
    ;

fragment
EXPONENT : ('e'|'E') ('+'|'-')? ('0'..'9')+ ;

fragment
HEX_DIGIT : ('0'..'9'|'a'..'f'|'A'..'F') ;

fragment
ESC_SEQ
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    |   UNICODE_ESC
    |   OCTAL_ESC
    ;

fragment
OCTAL_ESC
    :   '\\' ('0'..'3') ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7')
    ;

fragment
UNICODE_ESC
    :   '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
    ;

program 
    : namespace_scope_definitions;

namespace_scope_definitions
    : (namespace_definition | type_definition | function_definition | variable_definition)+;

type_scope_definitions
    : (type_definition | function_definition | variable_definition)*;   

namespace_definition
    : 'namespace' ID '{' namespace_scope_definitions '}';

type_definition 
    : 'type' ID? (':' expression (',' expression)+ )? '{' type_scope_definitions '}';

function_definition
    : ID '(' function_argument_list ')' ('(' function_argument_list ')')? ('->' expression)? compound_statement;

function_argument_list
    : expression? ID (':=' expression)? (',' function_argument_list)?;

variable_definition
    : 'static'? expression? ID ':=' expression 
    | 'static'? expression ID ('(' (expression)* ')')?;

literal_expression
    : CHAR
    | FLOAT
    | INT
    | STRING
    | 'auto'
    | 'type'
    | type_definition;

primary_expression
    : literal_expression
    | ID
    | '(' expression ')';

expression 
    : assignment_expression;

assignment_expression
    : logical_or_expression (('=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<='| '>>=' | '&=' | '^=' | '|=') assignment_expression)*;

logical_or_expression
    : logical_and_expression ('||' logical_and_expression)*;

logical_and_expression
    : inclusive_or_expression ('&&' inclusive_or_expression)*;

inclusive_or_expression
    : exclusive_or_expression ('|' exclusive_or_expression)*;

exclusive_or_expression
    : and_expression ('^' and_expression)*;

and_expression
    : equality_expression ('&' equality_expression)*;

equality_expression
    : relational_expression (('=='|'!=') relational_expression)*;

relational_expression
    : shift_expression (('<'|'>'|'<='|'>=') shift_expression)*;

shift_expression
    : additive_expression (('<<'|'>>') additive_expression)*;

additive_expression
    : multiplicative_expression (('+' multiplicative_expression) | ('-' multiplicative_expression))*;

multiplicative_expression
    : unary_expression (('*' | '/' | '%') unary_expression)*;

unary_expression
    : '++' primary_expression
    | '--' primary_expression
    | ('&' | '*' | '+' | '-' | '~' | '!') primary_expression
    | 'sizeof' primary_expression
    | postfix_expression;

postfix_expression
    : primary_expression
    | '[' expression ']'
    | '(' expression* ')'
    | '.' ID
    | '->' ID
    | '++' 
    | '--';

initializer_statement
    : expression ';'
    | variable_definition ';';

return_statement
    : 'return' expression ';';

try_statement
    : 'try' compound_statement catch_statement;

catch_statement
    : 'catch' '(' ID ')' compound_statement catch_statement?
    | 'catch' '(' '...' ')' compound_statement;

for_statement
    : 'for' '(' initializer_statement expression? ';' expression? ')' compound_statement;

while_statement
    : 'while' '(' initializer_statement ')' compound_statement;

do_while_statement
    : 'do' compound_statement 'while' '(' expression ')';

switch_statement
    : 'switch' '(' expression ')' '{' case_statement '}';

case_statement
    : 'case:' (statement)* case_statement?
    | 'default:' (statement)*;

if_statement
    : 'if' '(' initializer_statement ')' compound_statement;

statement
    : compound_statement
    | return_statement
    | try_statement
    | initializer_statement
    | for_statement
    | while_statement
    | do_while_statement
    | switch_statement
    | if_statement;

compound_statement
    : '{' (statement)* '}';

В частности, у меня проблемы со следующими правилами: 

namespace_scope_definitions
    : (namespace_definition | type_definition | function_definition | variable_definition)+;

type_scope_definitions
    : (type_definition | function_definition | variable_definition)*;

ANTLR говорит, что альтернативы 2 и 4, то есть type_definition и variable_definition, являются рекурсивными. Вот variable_definition: 

variable_definition
: 'static'? expression? ID ':=' expression 
| 'static'? expression ID ('(' (expression)* ')')?;

и вот type_definition: 

type_definition 
: 'type' ID? (':' expression (',' expression)+ )? '{' type_scope_definitions '}';

'type' сам по себе, и type_definition, является допустимым выражением в моем синтаксисе выражения. Тем не менее, удаление этого не устраняет двусмысленность, поэтому это не происходит там. И у меня есть множество других двусмысленностей , которые мне нужно устранить - детализировать все предупреждения и ошибки было бы слишком много, поэтому мне бы очень хотелось увидеть больше подробностей о том, как они рекурсивны из самой ANTLR.

Ответы [ 2 ]

1 голос
/ 20 июля 2011

Мое предложение состоит в том, чтобы на данный момент удалить большинство правил приоритета операторов: 

expression 
    : multiplicative_expression
      (
        ('+' multiplicative_expression)
      | ('-' multiplicative_expression)
      )*;

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

0 голосов
/ 21 июля 2011

Я нашел несколько неясностей в грамматике, исправил их и получил гораздо меньше предупреждений. Тем не менее, я думаю, что, вероятно, LL просто не правильный алгоритм для меня. Я пишу пользовательский парсер и лексер. Было бы неплохо, если бы ANTLR показал мне, как он обнаружил проблемы, чтобы я мог вмешаться и исправить их.

...