Antlr左递归问题 [英] Antlr left recursive problem
本文介绍了Antlr左递归问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我在Antlr语法中有一个左递归问题.虽然我认为我理解为什么存在问题，但我无法想到解决方案.问题出在我的数据类型规则的最后一行.我已经包括了整个语法供您查看:
grammar Test;
options {output=AST;ASTLabelType=CommonTree;}
tokens {FUNCTION; ATTRIBUTES; CHILDREN; COMPOSITE;}
program : function ;
function : ID (OPEN_BRACKET (attribute (COMMA? attribute)*)? CLOSE_BRACKET)? (OPEN_BRACE function* CLOSE_BRACE)? SEMICOLON? -> ^(FUNCTION ID ^(ATTRIBUTES attribute*) ^(CHILDREN function*)) ;
attribute : ID (COLON | EQUALS) datatype -> ^(ID datatype);
datatype : ID -> ^(STRING["id"] ID)
| NUMBER -> ^(STRING["number"] NUMBER)
| STRING -> ^(STRING["string"] STRING)
| BOOLEAN -> ^(STRING["boolean"] BOOLEAN)
| array -> ^(STRING["array"] array)
| lookup -> ^(STRING["lookup"] lookup)
| datatype PLUS datatype -> ^(COMPOSITE datatype datatype) ;
array : OPEN_BOX (datatype (COMMA datatype)*)? CLOSE_BOX -> datatype* ;
lookup : OPEN_BRACE (ID (PERIOD ID)*) CLOSE_BRACE -> ID* ;
NUMBER
: ('+' | '-')? (INTEGER | FLOAT)
;
STRING
: '"' ( ESC_SEQ | ~('\\'|'"') )* '"'
;
BOOLEAN
: 'true' | 'TRUE' | 'false' | 'FALSE'
;
ID : (LETTER|'_') (LETTER | INTEGER |'_')*
;
COMMENT
: '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
WHITESPACE : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;
COLON : ':' ;
SEMICOLON : ';' ;
COMMA : ',' ;
PERIOD : '.' ;
PLUS : '+' ;
EQUALS : '=' ;
OPEN_BRACKET : '(' ;
CLOSE_BRACKET : ')' ;
OPEN_BRACE : '{' ;
CLOSE_BRACE : '}' ;
OPEN_BOX : '[' ;
CLOSE_BOX : ']' ;
fragment
LETTER
: 'a'..'z' | 'A'..'Z'
;
fragment
INTEGER
: '0'..'9'+
;
fragment
FLOAT
: INTEGER+ '.' INTEGER*
;
fragment
ESC_SEQ
: '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
;
我正在使用Antlr works开发，该产品提供了解决此问题的功能-但不幸的是，它似乎不起作用:s
任何帮助都会很棒.
谢谢.
这是我尝试实现/解析的语言的示例
<FunctionName> <OptionalAttributes> <OptionalChildFunctions>
例如:
ForEach(in:[1,2,3,4,5] as:"i") {
Switch(value:{i}) {
Case(value:3) {
Print(message:"This is the number 3")
}
Default {
Print(message:"This isn't the number 3")
}
}
}
解决方案
好的，这可以解决问题:
grammar Test;
/************************************** PARSER **************************************/
program
: function EOF
;
function
: ID (OPEN_PAREN (attribute (COMMA attribute)*)? CLOSE_PAREN)?
(OPEN_BRACE function* CLOSE_BRACE)?
SEMICOLON?
;
attribute
: ID (COLON | EQUALS)? expression
;
expression
: atom (PLUS atom)*
;
atom
: ID
| STRING
| BOOLEAN
| NUMBER
| array
| lookup
;
array
: OPEN_BOX (expression (COMMA expression)*)? CLOSE_BOX
;
lookup
: OPEN_BRACE (ID (PERIOD ID)*) CLOSE_BRACE
;
/************************************** LEXER **************************************/
NUMBER : ('+' | '-')? (INTEGER | FLOAT)
;
STRING : '"' ( ESC_SEQ | ~('\\'|'"') )* '"'
;
BOOLEAN : 'true' | 'TRUE' | 'false' | 'FALSE'
;
ID : (LETTER|'_') (LETTER | INTEGER |'_')*
;
COMMENT : '//' ~('\n'|'\r')* ('\r'? '\n'| EOF) {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
WHITESPACE : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;
COLON : ':' ;
SEMICOLON : ';' ;
COMMA : ',' ;
PERIOD : '.' ;
PLUS : '+' ;
EQUALS : '=' ;
OPEN_PAREN : '(' ;
CLOSE_PAREN : ')' ;
OPEN_BRACE : '{' ;
CLOSE_BRACE : '}' ;
OPEN_BOX : '[' ;
CLOSE_BOX : ']' ;
fragment
LETTER : 'a'..'z' | 'A'..'Z' ;
fragment
INTEGER : '0'..'9'+ ;
fragment
FLOAT : INTEGER+ '.' INTEGER* ;
fragment
ESC_SEQ : '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\') ;
请注意，我已将OPEN_BRACKET和CLOSE_BRACKET的名称更改为OPEN_PAREN和CLOSE_PAREN.圆括号(和)是圆括号，方括号[和]被称为方括号(您称为框的框，但将其称为框不会损害IMO).
I have a left recursive issue in my Antlr grammar. While I think I understand why there is a problem I am unable to think of a solution. The issue is with the last line for my datatype rule. I have included the entire grammar for you to see:
grammar Test;
options {output=AST;ASTLabelType=CommonTree;}
tokens {FUNCTION; ATTRIBUTES; CHILDREN; COMPOSITE;}
program : function ;
function : ID (OPEN_BRACKET (attribute (COMMA? attribute)*)? CLOSE_BRACKET)? (OPEN_BRACE function* CLOSE_BRACE)? SEMICOLON? -> ^(FUNCTION ID ^(ATTRIBUTES attribute*) ^(CHILDREN function*)) ;
attribute : ID (COLON | EQUALS) datatype -> ^(ID datatype);
datatype : ID -> ^(STRING["id"] ID)
| NUMBER -> ^(STRING["number"] NUMBER)
| STRING -> ^(STRING["string"] STRING)
| BOOLEAN -> ^(STRING["boolean"] BOOLEAN)
| array -> ^(STRING["array"] array)
| lookup -> ^(STRING["lookup"] lookup)
| datatype PLUS datatype -> ^(COMPOSITE datatype datatype) ;
array : OPEN_BOX (datatype (COMMA datatype)*)? CLOSE_BOX -> datatype* ;
lookup : OPEN_BRACE (ID (PERIOD ID)*) CLOSE_BRACE -> ID* ;
NUMBER
: ('+' | '-')? (INTEGER | FLOAT)
;
STRING
: '"' ( ESC_SEQ | ~('\\'|'"') )* '"'
;
BOOLEAN
: 'true' | 'TRUE' | 'false' | 'FALSE'
;
ID : (LETTER|'_') (LETTER | INTEGER |'_')*
;
COMMENT
: '//' ~('\n'|'\r')* '\r'? '\n' {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
WHITESPACE : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;
COLON : ':' ;
SEMICOLON : ';' ;
COMMA : ',' ;
PERIOD : '.' ;
PLUS : '+' ;
EQUALS : '=' ;
OPEN_BRACKET : '(' ;
CLOSE_BRACKET : ')' ;
OPEN_BRACE : '{' ;
CLOSE_BRACE : '}' ;
OPEN_BOX : '[' ;
CLOSE_BOX : ']' ;
fragment
LETTER
: 'a'..'z' | 'A'..'Z'
;
fragment
INTEGER
: '0'..'9'+
;
fragment
FLOAT
: INTEGER+ '.' INTEGER*
;
fragment
ESC_SEQ
: '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
;
I am developing using Antlr works which provides a function to resolve this issue - but unfortunately it does not seem to work :s
Any help would be great.
Thanks.
EDIT:
Here is an example of the language I'm trying to implement / parse
<FunctionName> <OptionalAttributes> <OptionalChildFunctions>
So for example:
ForEach(in:[1,2,3,4,5] as:"i") {
Switch(value:{i}) {
Case(value:3) {
Print(message:"This is the number 3")
}
Default {
Print(message:"This isn't the number 3")
}
}
}
解决方案
Okay, this should do the trick:
grammar Test;
/************************************** PARSER **************************************/
program
: function EOF
;
function
: ID (OPEN_PAREN (attribute (COMMA attribute)*)? CLOSE_PAREN)?
(OPEN_BRACE function* CLOSE_BRACE)?
SEMICOLON?
;
attribute
: ID (COLON | EQUALS)? expression
;
expression
: atom (PLUS atom)*
;
atom
: ID
| STRING
| BOOLEAN
| NUMBER
| array
| lookup
;
array
: OPEN_BOX (expression (COMMA expression)*)? CLOSE_BOX
;
lookup
: OPEN_BRACE (ID (PERIOD ID)*) CLOSE_BRACE
;
/************************************** LEXER **************************************/
NUMBER : ('+' | '-')? (INTEGER | FLOAT)
;
STRING : '"' ( ESC_SEQ | ~('\\'|'"') )* '"'
;
BOOLEAN : 'true' | 'TRUE' | 'false' | 'FALSE'
;
ID : (LETTER|'_') (LETTER | INTEGER |'_')*
;
COMMENT : '//' ~('\n'|'\r')* ('\r'? '\n'| EOF) {$channel=HIDDEN;}
| '/*' ( options {greedy=false;} : . )* '*/' {$channel=HIDDEN;}
;
WHITESPACE : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;} ;
COLON : ':' ;
SEMICOLON : ';' ;
COMMA : ',' ;
PERIOD : '.' ;
PLUS : '+' ;
EQUALS : '=' ;
OPEN_PAREN : '(' ;
CLOSE_PAREN : ')' ;
OPEN_BRACE : '{' ;
CLOSE_BRACE : '}' ;
OPEN_BOX : '[' ;
CLOSE_BOX : ']' ;
fragment
LETTER : 'a'..'z' | 'A'..'Z' ;
fragment
INTEGER : '0'..'9'+ ;
fragment
FLOAT : INTEGER+ '.' INTEGER* ;
fragment
ESC_SEQ : '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\') ;
Note that I've changed the name of OPEN_BRACKET and CLOSE_BRACKET into OPEN_PAREN and CLOSE_PAREN. The round ones, ( and ), are parenthesis, the square ones, [ and ], are called brackets (the ones you called boxes, but calling them boxes doesn't hurt IMO).
这篇关于Antlr左递归问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
