删除语法中的左递归

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

Dinesh谢谢你的回答，你的解决方案给我一个冲突在JavaCC与(代理-后缀)*。我是这样解决的:

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中通常是如何处理这些语法的。