解决 XText 中的左递归 SQL-语法定义表和连接

Question

为了练习，我目前正在为简单的 SELECT 语句定义语法，例如

SELECT * FROM table1 as t1 JOIN table 2 AS t2 ON (t1.field1=t2.field2);

为此，我使用 XText。这是语法的摘录，在 FROM 部分定义表：

table: 
    name=ID (('AS')? alias=ID)?
    | 
    join
;

join:
    left_table=table (type=join_type)? 'JOIN' right_table=table 'ON' condition=predicate
;

显然，规则 "table" 是递归的。我已经阅读了所有描述如何解决 XText（或分别为 ANTLR）中的左递归的指南。但我不明白，或者至少，我无法将解释映射到我的特定代码...

我的定义有什么问题，如何解决左递归问题？

Answer 1

这对你的语法来说是个大手术。

为什么是左递归的？

table：加入； // 所以 join 是 table
加入：table'JOIN'table'ON'条件； // 所以 table 是 join
相互递归和 join 的两种用法，table 最左边使得两个规则都是左递归的

如何解决这个问题？

您可以将 JOIN 规则重写为列表：join: ('JOIN' table)*
以及您需要对其余语法进行更改以使此更改保持语法不变。
请注意，更改会影响树模型的形状

解决 XText 中的左递归 SQL-语法定义表和连接

Resolve left-recursion in XText SQL-grammar defining tables and joins

antlr

xtext