定义算术运算的典型BNF:
E :- E + T
| T
T :- T * F
| F
F :- ( E )
| number
有没有什么方法可以重写这个语法,这样它就可以用LR(0)语法分析器实现,同时仍然保留运算符的优先级和左结合性?我认为引入某种非歧义终端应该是可能的,但我不知道如何做到
谢谢!
一种语言只有在无前缀的情况下才能有LR(0)语法,这意味着该语言中没有字符串是另一种语言的前缀。在这种情况下,您所描述的语言不是无前缀的。例如,字符串number + number
是number + number + number
的前缀。
解决这个问题的一个常见解决方法是通过要求生成的所有字符串以一个特殊的"完成"字符结尾来"结束标记"您的语言。例如,您可以要求生成的所有字符串都以分号结尾。如果您这样做,您可以为具有以下语法的语言构建LR(0)解析器:
S→E
E→E+T|T
T→T*F|F
F&rar;数字|(E)