Удалить левую рекурсию в грамматике

Question

У меня есть эта грамматика:

agent
 = nil 
 | @ 
 | id 
 | act . agent
 | agent + agent
 | agent "|" agent
 | agent \ restriction
 |  agent [relabeling]
 | agent where agent_frame end
 | automation
 | (agent)

где приоритеты:

"where" < "+" < "|" < "\" < "." < "[" < "nil", "@"

Мне нужно удалить левую рекурсию с учетом приоритетов (и написать все на JavaCC).

Можете ли вы помочь мне удалить рекурсию?

Answer 1

Динеш, спасибо за ответ, ваше решение вызывает конфликт в JavaCC с (agent-postfix) *. Я решил таким образом:

agent=agent2 agent'
agent'= "where" agent_frame "end" agent' | epsilon

agent2= agent3 agent2'
agent2'= "+" agent3 agent2' | epsilon

agent3= agent4 agent3'
agent3'= "|" agent4 agent3' | epsilon

agent4 = agent5 agent4'
agent4'= "\" restriction agent4' | epsilon

agent5: act "." agent | agent6

agent6 = agent7 agent6'
agent6'= "[" relabeling "]" agent6' | epsilon

agent7= id | automaton | "(" agent ")" | "nil" | "@"

но я не знаю, правильно ли это решение.

Большое спасибо.

С уважением Доменико

Answer 2

Я не эксперт по JavaCC, но вот как вы можете начать избавляться от своей левой рекурсии:

agent-primary
 = nil
 | @
 | id
 | act . agent
 | automation
 | (agent)

agent-postfix
 = + agent
 | "|" agent
 | \ restriction
 | [relabeling]
 | where agent_frame end

agent
 = agent-primary (agent-postfix)* 

Вы можете столкнуться с некоторыми конфликтами с правом agent вызывает также в "бинарных" выражениях, таких как agent + agent,

В любом случае ваша грамматика очень похожа на арифметические выражения, поэтому я советую вам посмотреть, как они обычно обрабатываются в JavaCC.