antlr4:语法歧义，左递归，都是吗? [英] antlr4: Grammar ambiguity, left-recursion, both?

问题描述

我的语法如下所示，无法编译.返回的错误(来自antlr4 maven插件)是:

My grammar, shown below, does not compile. The returned error (from the antlr4 maven plugin) is:

[INFO] --- antlr4-maven-plugin:4.3:antlr4 (default-cli) @ beebell ---
[INFO] ANTLR 4: Processing source directory /Users/kodecharlie/workspace/beebell/src/main/antlr4
[INFO] Processing grammar: DateRange.g4
org\antlr\v4\parse\GrammarTreeVisitor.g: node from line 13:87 mismatched tree node: startTime expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from after line 13:87 mismatched tree node: RULE expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from line 13:87 mismatched tree node: startTime expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from after line 13:87 mismatched tree node: RULE expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from line 13:87 mismatched tree node: startTime expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from after line 13:87 mismatched tree node: RULE expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from line 13:87 mismatched tree node: startTime expecting <UP>
org\antlr\v4\parse\GrammarTreeVisitor.g: node from after line 13:87 mismatched tree node: RULE expecting <UP>
[ERROR] error(20):  internal error: Rule HOUR undefined 
[ERROR] error(20):  internal error: Rule MINUTE undefined 
[ERROR] error(20):  internal error: Rule SECOND undefined 
[ERROR] error(20):  internal error: Rule HOUR undefined 
[ERROR] error(20):  internal error: Rule MINUTE undefined 

我可以看到语法可能是如何混淆的-例如，2位数字是MINUTE，SECOND还是HOUR(或者可能是一年的开始).但是一些文章建议此错误是由左递归导致的.

I can see how the grammar might be confused -- Eg, whether 2 digits is a MINUTE, SECOND, or HOUR (or maybe the start of a year). But a few articles suggest this error results from left-recursion.

你能告诉我发生了什么吗?

Can you tell what's going on?

谢谢.这是语法:

grammar DateRange;

range     : startDate (THRU endDate)? | 'Every' LONG_DAY 'from' startDate THRU endDate ;

startDate : dateTime ;
endDate   : dateTime ;
dateTime  : GMTOFF | SHRT_MDY | YYYYMMDD | (WEEK_DAY)? LONG_MDY ;

// Dates.
GMTOFF    : YYYYMMDD 'T' HOUR ':' MINUTE ':' SECOND ('-'|'+') HOUR ':' MINUTE ;
YYYYMMDD  : YEAR '-' MOY '-' DOM ;
SHRT_MDY  : MOY ('/' | '-') DOM ('/' | '-') YEAR ;
LONG_MDY  : (SHRT_MNTH '.'? | LONG_MNTH) WS DOM ','? (WS YEAR (','? WS TIMESPAN)? | WS startTime)? ;

YEAR      : DIGIT DIGIT DIGIT DIGIT ;   // year
MOY       : (DIGIT | DIGIT DIGIT) ;     // month of year.
DOM       : (DIGIT | DIGIT DIGIT) ;     // day of month.
TIMESPAN  : startTime (WS THRU WS endTime)? ;

// Time-of-day.
startTime : TOD ;
endTime   : TOD ;
TOD       : NOON | HOUR2 (':' MINUTE)? WS? MERIDIAN ;
NOON      : 'noon' ;
HOUR2     : (DIGIT | DIGIT DIGIT) ;
MERIDIAN  : 'AM' | 'am' | 'PM' | 'pm' ;

// 24-hour clock.  Sanity-check range in listener.
HOUR      : DIGIT DIGIT ;
MINUTE    : DIGIT DIGIT ;
SECOND    : DIGIT DIGIT ;

// Range verb.
THRU      : WS ('-'|'to') WS -> skip ;

// Weekdays.
WEEK_DAY  : (SHRT_DAY | LONG_DAY) ','? WS ;
SHRT_DAY  : 'Sun' | 'Mon' | 'Tue' | 'Wed' | 'Thu' | 'Fri' | 'Sat' -> skip ;
LONG_DAY  : 'Sunday' | 'Monday' | 'Tuesday' | 'Wednesday' | 'Thursday' | 'Friday' | 'Saturday' -> skip ;

// Months.
SHRT_MNTH : 'Jan' | 'Feb' | 'Mar' | 'Apr' | 'May' | 'Jun' | 'Jul' | 'Aug' | 'Sep' | 'Oct' | 'Nov' | 'Dec' ;
LONG_MNTH : 'January' | 'February' | 'March' | 'April' | 'May' | 'June' | 'July' | 'August' | 'September' | 'October' | 'November' | 'December' ;

DIGIT     : [0-9] ;
WS        : [ \t\r\n]+ -> skip ;

推荐答案

我通过为每个数字序列(长度为1、2、3或4)设置唯一的生产规则来解决了此问题.同样，我简化了几个规则-实际上，是试图使生产规则的替代方案更直接.无论如何，这是编译的最终结果:

I resolved this issue by setting up a unique production rule for each sequence of digits (of length 1, 2, 3, or 4). As well, I simplified several rules -- in effect, trying to make the production rule alternatives more straightforward. Anyway, here is the final result, which does compile:

grammar DateRange;

range     : 'Every' WS longDay WS 'from' WS startDate THRU endDate
          | startDate THRU endDate
          | startDate
          ;

startDate : dateTime ; endDate   : dateTime ; dateTime  : utc
          | shrtMdy
          | yyyymmdd
          | longMdy
          | weekDay ','? WS longMdy
          ;

// Dates.
utc       : yyyymmdd 'T' hour ':' minute ':' second ('-'|'+') hour ':' minute ;
yyyymmdd  : year '-' moy '-' dom ;
shrtMdy : moy ('/' | '-') dom ('/' | '-') year ;
longMdy   : longMonth WS dom ','? optYearAndOrTime?
          | shrtMonth '.'? WS dom ','? optYearAndOrTime?
          ;

optYearAndOrTime : WS year ','? WS timespan
                 | WS year
                 | WS timespan
                 ;

fragment DIGIT : [0-9] ;
ONE_DIGIT    : DIGIT ;
TWO_DIGITS   : DIGIT ONE_DIGIT ;
THREE_DIGITS : DIGIT TWO_DIGITS ;
FOUR_DIGITS  : DIGIT THREE_DIGITS ;

year      : FOUR_DIGITS ;                   // year
moy       : ONE_DIGIT | TWO_DIGITS ;        // month of year.
dom       : ONE_DIGIT | TWO_DIGITS ;        // day of month.
timespan  : (tod THRU tod) | tod ;

// Time-of-day.
tod       : noon | (hour2 (':' minute)? WS? meridian?) ;
noon      : 'noon' ; hour2     : ONE_DIGIT | TWO_DIGITS ;
meridian  : ('AM' | 'am' | 'PM' | 'pm' | 'a.m.' | 'p.m.') ;

// 24-hour clock.  Sanity-check range in listener.
hour      : TWO_DIGITS ;
minute    : TWO_DIGITS ;
second    : TWO_DIGITS ;   // we do not use seconds.

// Range verb.
THRU      : WS? ('-'|'–'|'to') WS? ;

// Weekdays.
weekDay   : shrtDay | longDay ; shrtDay   : 'Sun' | 'Mon' | 'Tue' | 'Wed' | 'Thu' | 'Fri' | 'Sat' ; longDay   : 'Sunday' | 'Monday' | 'Tuesday' | 'Wednesday' | 'Thursday' | 'Friday' | 'Saturday' ;

// Months.
shrtMonth : 'Jan' | 'Feb' | 'Mar' | 'Apr' | 'May' | 'Jun' | 'Jul' | 'Aug' | 'Sep' | 'Oct' | 'Nov' | 'Dec' ;
longMonth : 'January' | 'February' | 'March' | 'April' | 'May' | 'June' | 'July' | 'August' | 'September' | 'October' | 'November' | 'December' ;

WS        : ~[a-zA-Z0-9,.:]+ ;

这篇关于antlr4:语法歧义，左递归，都是吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！