标准方法很容易将非 LL(1) 的上下文无关文法转换为等效的文法。是否有可用的工具可以自动执行此过程?
在下面的示例中,我对非终结符使用大写字母,对终结符使用小写字母。
以下左递归非终结符:
A -> A a | b
可以转化为右递归形式:
A -> b A'
A' -> NIL | a A'
请注意,左递归产生式规则确保表达式关联到左侧,右递归产生式也类似;因此语法修改也会改变表达式的关联性。
另一个问题是间接左递归,例如:
A -> B a
B -> A b
左因式分解也用于确保解析器只需要一个前瞻标记。以下产生式必须通过两个标记向前看:
A -> a b | a c
这也可以重构;到:
A -> a (b | c)
是否有任何软件工具可以自动进行这些语法转换?从而生成适用于 LL(1) 解析器的等效语法?
最佳答案
Haskell 语法组合器库 here允许将语法转换为非左递归形式。输入语法必须是 parsing expression grammar .
关于parsing - 左因式分解的自动语法转换;和左递归移除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17265798/