Разрешить левую рекурсию в 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
;

Очевидно, что правило "таблица" остается рекурсивным. Я прочитал все руководства, описывающие, как разрешить левую рекурсию в XText (или ANTLR соответственно). Но я не понимаю этого или, по крайней мере, я не могу сопоставить объяснения с моим конкретным кодом...

В чем проблема с моим определением и как я могу решить левую рекурсию?

Answer 1

Это будет большая операция над вашей грамматикой.

Почему это левый рекурсив?

• стол: соединение; // так что соединение является крайним левым нетерминалом таблицы
• join: таблица 'JOIN' таблица 'ON' условие; // поэтому таблица является крайним левым нетерминалом для объединения
• взаимная рекурсия и два крайних использования соединения и таблицы делают оба правила леворекурсивными

Как это исправить?

• Вы можете переписать правило JOIN в виде списка: join: ('JOIN' table)*
• и все, что вам нужно изменить в остальной части грамматики, чтобы сохранить это изменение с сохранением синтаксиса.
• обратите внимание, что изменение повлияет на форму вашей модели дерева