如何解析带括号的层次结构根? [英] How to parse a parenthesized hierarchy root?

问题描述

我正在尝试使用ANTLR解析值.这是我语法的相关部分:

I'm trying to parse values with ANTLR. Here's the relevant part of my grammar:

root : IDENTIFIER | SELF | literal | constructor | call | indexer;

hierarchy : root (SUB^ (IDENTIFIER | call | indexer))*;

factor  : hierarchy ((MULT^ | DIV^ | MODULO^) hierarchy)*;

sum : factor ((PLUS^ | MINUS^) factor)*;

comparison  : sum (comparison_operator^ sum)*;

value   : comparison | '(' value ')';

我不会描述每个标记或规则，因为它们的名称足以说明它们的作用.该语法运作良好并且可以编译，允许我使用value解析以下内容:

I won't describe each token or rule since their name is quite explanatory of their role. This grammar works well and compiles, allowing me to parse, using value, things such as:

a.b[c(5).d[3] * e()] < e("f")

唯一需要进行值识别的是能够具有带括号的层次结构根.例如:

The only thing left for value recognition is to be able to have parenthesized hierarchy roots. For instance:

(a.b).c
(3 < d()).e
...

天真的，没有太大的期望，我尝试为我的root规则添加以下替代方法:

Naively, and without much expectations, I tried adding the following alternative to my root rule:

root : ... | '(' value ')';

但是由于非LL(*)行为，这违反了value规则:

This however breaks the value rule due to non-LL(*)ism:

rule value has non-LL(*) decision due to recursive rule invocations reachable
from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using 
backtrack=true option.

即使阅读了《 权威性ANTLR参考》 的大部分内容，我仍然不理解这些错误.但是，我的理解是，在看到括号打开时，ANTLR无法知道它是在看括号值的开头还是在括号根的开头.

Even after reading most of The Definitive ANTLR Reference, I still don't understand these errors. However, what I do understand is that, upon seeing a parenthesis opening, ANTLR cannot know if it's looking at the beginning of a parenthesized value, or at the beginning of a parenthesized root.

如何明确定义带括号的层次结构根的行为?

How can I clearly define the behavior of parenthesized hierarchy root?

编辑:根据要求，附加规则:

Edit: As requested, the additional rules:

parameter : type IDENTIFIER -> ^(PARAMETER ^(type IDENTIFIER));

constructor : NEW type PAREN_OPEN (arguments+=value (SEPARATOR arguments+=value)*)? PAREN_CLOSE -> ^(CONSTRUCTOR type ^(ARGUMENTS $arguments*)?);

call : IDENTIFIER PAREN_OPEN (values+=value (SEPARATOR values+=value)*)? PAREN_CLOSE -> ^(CALL IDENTIFIER ^(ARGUMENTS $values*)?);

indexer : IDENTIFIER INDEX_START (values+=value (SEPARATOR values+=value)*)? INDEX_END -> ^(INDEXER IDENTIFIER ^(ARGUMENTS $values*));

推荐答案

从value删除'(' value ')'并将其放置在root中:

Remove '(' value ')' from value and place it in root:

root : IDENTIFIER | SELF | literal | constructor | call | indexer | '(' value ')';

...

value : comparison;

现在(a.b).c将导致以下分析:

和(3 < d()).e在:

当然，您可能希望省略AST中的括号:

Of course, you'll probably want to omit the parenthesis from the AST:

root : IDENTIFIER | SELF | literal | constructor | call | indexer | '('! value ')'!;

此外，您无需在解析器规则中使用+=在List中附加令牌.以下:

Also, you don't need to append tokens in a List using += in your parser rules. The following:

call 
 : IDENTIFIER PAREN_OPEN (values+=value (SEPARATOR values+=value)*)? PAREN_CLOSE 
   -> ^(CALL IDENTIFIER ^(ARGUMENTS $values*)?)
 ;

可以重写为:

call 
 : IDENTIFIER PAREN_OPEN (value (SEPARATOR value)*)? PAREN_CLOSE 
   -> ^(CALL IDENTIFIER ^(ARGUMENTS value*)?)
 ;

编辑

您的主要问题是某些输入可以用两种(或更多种！)方式进行解析的事实.例如，输入(a)可以通过value规则的替代项1和2进行解析:

EDIT

Your main problem is the fact that certain input can be parsed in two (or more!) ways. For example, the input (a) could be parsed by alternative 1 and 2 of your value rule:

value 
 : comparison    // alternative 1
 | '(' value ')' // alternative 2
 ;

运行您的解析器规则:comparison(替代项1)可以匹配(a)，因为它匹配root规则，而该规则又匹配了'(' value ')'.但这也是替代2匹配的东西！这样就可以了:解析器看到"一个输入，两个不同 解析并报告这种歧义.

Run through your parser rules: a comparison (alternative 1) can match (a) because it matches the root rule, which in its turn matches '(' value ')'. But that is also what alternative 2 matches! And there you have it: the parser "sees" for one input, two different parses and reports about this ambiguity.

这篇关于如何解析带括号的层次结构根?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！