相互左递归ANTLR 4 [英] Mutual Left Recursion ANTLR 4

问题描述

很抱歉在相互左递归问题上再问一个问题，我觉得我的情况对我来说很独特，或者至少我想不出足以将其与其他所有人的语法联系起来的地方.我对comp sci世界有点陌生(我是用Java自学的，这是我的目标语言，现在是ANTLR4)，因此，请尽可能以通俗的方式而不是CS的主要术语来描述事物.

I'm sorry to ask yet another question on mutual left recursion, I feel like mine is unique to my situation, or at least I can't figure out enough to relate it to everyone else's grammars. I'm a bit new to the comp sci world (I'm self taught in java, which is my target language, and now ANTLR4) so if possible please describe things in layperson terms, not CS major terms.

我正在编写一个程序，该程序需要代数和符号导数，当然还要求对事物进行解析，并对树进行运算，但是我什至不必担心这一点，因为我认为ANTLR4支持直接左键递归，但显然并没有.在输出中，它一直告诉我我的方法[expression]是相互左递归的，显然这是不允许的...? 我的问题:

I'm writing a program that requires algebra and symbolic derivatives, and of course that requires that things be parsed, and trees be operated upon but I'm not even going to worry about that yet because I thought ANTLR4 supported direct left recursion, but apparently it doesn't somehow. On the output, it keeps telling me that my method [expression] is mutually left recursive and apparently that's not allowed...? MY QUESTIONS:

1)有人可以解释左递归/如果存在左递归，则相互之间和直接左递归之间的区别?

1) Can someone explain left recursion/the difference between mutual and direct left recursion if there is one?

2)说明我的语法是什么导致这种递归的烦恼，以及如何解决它? 而且我不确定这是否是主题:

2) Explain what in my grammar is causing this recursive annoyance, and how to fix it? And I'm not sure if this is on topic:

3)人们说关于替代品和标签替代品的事情(我认为它们的意思是#label符号).那是做什么用的?

3) People say things about alternatives and labeling alternatives (I think they mean the #label notation). What is that for?

grammar MathProcessor;
@header {package utils;}
END: ';';
EQUALS: '=';
SIN: 'sin(';
COS: 'cos(';
TAN: 'tan(';
SEC: 'sec(';
CSC: 'csc(';
COT: 'cot(';
LN: 'ln(';
EPOW: 'pow(';
RPAREN: '(';
LPAREN: ')';
EXP: '^';
MULT: '*';
DIV: '/';
ADD: '+';
SUBT: '-';
VAR: ('a'..'z'|'A'..'Z');
INT: ('0'..'9')+;
mathobj: ((equation|expression) END) EOF;
equation: (expression '=' expression);

expression: 
((RPAREN|SIN|COS|TAN|SEC|CSC|COT|LN|EPOW) expression (RPAREN)) #parenOps
| (expression EXP expression) #exponent
| (expression (MULT|DIV) expression) #multiplyDivide 
| (expression (ADD|SUBT) expression) #addSubtract
| (VAR|INT) #varInt
;

推荐答案

如果仅删除语法中不必要的括号的几种情况，您的语法就可以在ANTLR 4中使用.左递归消除算法仅适用于直接左递归，如下例所示:

Your grammar would actually work with ANTLR 4 if you simply removed several cases of unnecessary parentheses in your grammar. The left recursion elimination algorithm only works with direct left recursion, which appears in the following example:

a
  : B
  | a B  // the reference to 'a' here is direct left recursion
  ;

另一种主要的递归类型是间接左递归，通常使用两个单独的规则进行演示.

The primary other type of recursion is indirect left recursion, which is typically demonstrated using two separate rules.

a
  : B
  | c
  ;

c
  : a B // the reference back to 'a' is indirect left recursion
  ;

就您的语法而言，ANTLR将(...)视为匿名子规则，因此将类似以下的代码确定为间接左递归.如果从示例中删除括号，则其行为类似于第一种情况.

In the case of your grammar, ANTLR is treating (...) as an anonymous sub-rule, so code like the following is determined to be indirect left recursion. If you remove the parentheses from the example, it behaves like the first case.

a
  : B
  | (a B)
  ;

为回答您的最后一个问题，#label语法更改了该替代方法的生成的分析树类.例如，表达式3不会生成普通的ExpressionContext对象，而是会生成VarIntContext.这样，您就可以在自动生成的侦听器和访问者的规则中区分不同的选择.

To answer your last question, the #label syntax changes the generated parse tree class for that alternative. For example, rather than generate a plain ExpressionContext object, the expression 3 will generate a VarIntContext. This allows you to distinguish between different alternatives in a rule in automatically generated listeners and visitors.

这篇关于相互左递归ANTLR 4的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！