相互递归-ANTLR:固定左递归和相互左递归

Question

这是我正在研究的语法的一部分，目的是开发一个解析器工具，这对我的研究很重要。它在eclipse中的ANTLR IDE下给了我一个错误，说paraction, action, cspaction是相互左递归的。

我已经在网上搜索了一个解决方案，但不知道该怎么做。由于这种语言是研究领域的标准，我没有改变语言语义细节的能力。

paraction : action | decl 'circspot' paraction;
action : schemaexp | command | INDEX | cspaction | action '['INDEX+ ':=' exp+']';
cspaction   : 'Skip'|'Stop'|'Chaos'|comm 'circthen' action | pred '&' action
        |action ';' action | action 'extchoice' action | action 'intchoice' action
        |action 'lpar' nsexp | csexp | nsexp 'rpar' action
        |action 'lpar' nsexp | nsexp 'rpar' action
        |action '\' csexp | paraction '('exp+')' | 'circmu' INDEX 'circspot' action
        | ';' decl 'circspot' action | 'extchoice' decl 'circspot' action 
        | 'intchoice' decl 'circspot' action
        | 'lpar' csexp 'rpar' decl 'circspot' 'lpar' nsexp 'rpar' 'circspot' action 
        | 'interleave' decl 'circspot' 'lpar' nsexp 'rpar' action;

事实上，我正在尝试为"Circus"创建一个语法文件，这是一种状态丰富的形式建模语言，它是一种称为Z的规范语言和一种名为CSP（通信顺序过程）的过程建模语言的组合，所以是的，这是现有的语言。它在学术界使用至今，语言处于发展之中。我有一个语言的EBNF，我正在尝试用ANTLR将EBNF翻译成语法。我已设法使以下两条规则发挥作用。但是cspaction似乎是一个困难的问题。

paraction : (decl 'circspot' (paraction)+ | action)  ;
action  : ((schemaexp | command | N | cspaction)('[' IDENT+ ':=' exp+']')?)* ;

反斜杠是latex的一部分，现在可以省略，因为它们被用作字符串。下面请找到Circus的完整EBNF。它来自已发表的论文《马戏团的指称语义》。

电路的完整EBNFhttp://www.use.com/b1ad2df0609961615fff

Answer 1

我建议您使用ANTLR v4。以前版本的ANTLR v3不支持左递归（既不支持间接递归也不支持直接递归）。，但是ANTLR v4确实支持直接左递归。因此，在删除了间接左递归规则，并删除了生成ParAction（即(Decl '•')* Action）之后，我得到了以下语法：

grammar Circus;
// parser rules
program
 : circus_par* EOF
 ;
circus_par
 : par
 | CHANNEL cdecl
 | CHANSET n '==' csexp
 | proc_decl
 ;
cdecl
 : simple_cdecl (';' simple_cdecl)*
 ;
simple_cdecl
 : n+ ':' exp
 | n+
 | '[' n+ ']' n+ ':' exp
 | schema_exp
 ;
proc_decl
 : PROCESS n '[' n+ ']' '^=' proc_def
 | PROCESS n '^=' proc_def
 ;
proc_def
 : decl '•' proc_def
 | decl '⊙' proc_def
 | proc
 ;
proc
 : BEGIN ppar* STATE schema_exp ppar* '•' action END
 | proc ';' proc
 | proc '□' proc
 | proc '⊓' proc
 | proc '|[' csexp ']|' proc
 | proc '|||' proc
 | proc '\' proc
 | '(' decl '•' proc_def ')' '(' exp+ ')'
 | n '(' exp+ ')'
 | '(' decl '⊙' proc_def ')' '⌊' exp+ '⌋'
 | n '⌊' exp+ '⌋'
 | proc '[' n+ ':=' n+ ']'
 | n '[' exp+ ']'
 | ';' decl '•' proc
 | '□' decl '•' proc
 | '⊓' decl '•' proc 
 ;
ppar
 : par
 | n '^=' (decl '•')* action
 | NAMESET n '==' nsexp
 ;     
action
 : schema_exp
 | command
 | n
 | action '[' n+ ':=' exp+ ']'
 | SKIP
 | STOP
 | CHAOS
 | comm '→' action
 | pred '&' action
 | action ';' action
 | action '□' action
 | action '⊓' action
 | action '[|' nsexp
 | csexp
 | nsexp ']|' action
 | action '||[' nsexp
 | nsexp ']||' action
 | action '\' csexp
 | (decl '•')+ action '(' exp+ ')'  
 | action '(' exp+ ')'  
 | 'μ' n '•' action
 | ';' decl '•' action
 | '□' decl '•' action
 | '⊓' decl '•' 
 | '|[' csexp ']|' decl '•' '|[' nsexp ']|' '•' action
 | '|||' decl '•' '|[' nsexp ']|' action
 ;
comm
 : n '[' exp+ ']' cparameter*
 | n cparameter*
 ;
cparameter
 : '?' n ':' pred
 | '?' n
 | '!' exp
 | '.' exp
 ;
command
 : n+ ':=' exp+
 | IF gactions FI
 | n+ ':' '[' pred ',' pred ']'
 | '[' pred ']'
 | '{' pred '}'
 | VAR decl '•' action
 | VAL decl '•' action
 | RES decl '•' action
 | VRES decl '•' action
 ;
gactions
 : pred '→' action '□' gactions
 | pred '→' action
 ;
n
 : ZID
 ;
par : 'TODO';
decl : 'TODO';
nsexp : 'TODO';
exp : 'TODO';
csexp : 'TODO';
schema_exp : 'TODO';
pred : 'TODO';
// lexer rules
CHANNEL : 'channel';
CHANSET : 'chanset';
PROCESS : 'process';
BEGIN : 'begin';
END : 'end';
STATE : 'state';
NAMESET : 'nameset';
SKIP : 'Skip';
STOP : 'Stop';
CHAOS : 'Chaos';
IF : 'if';
FI : 'fi';
VAL : 'val';
VAR : 'var';
RES : 'res';    
VRES : 'vres';
ZID : [a-zA-Z]+;

这与你发布的链接非常相似。

生成这样的lexer和解析器：

java-cp antlr-4.0-complete.jar org.antlr.v4.Tool Circus.g4

注意，如果你想匹配一个字面反斜杠，你需要对其进行转义：

CIRCSPOT : '\circspot';