相互左递归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 支持直接左递归，但显然它没有以某种方式.在输出中，它一直告诉我我的方法 [表达式] 是相互递归的，显然这是不允许的......?我的问题:

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 将生成一个 VarIntContext，而不是生成一个普通的 ExpressionContext 对象.这使您可以在自动生成的听众和访问者中区分规则中的不同备选方案.

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屋！