Bab*_*bak 4 compiler-construction grammar parsing left-recursion
我正在尝试为C编写一个编译器(虽然简单的语法).
有些事情我已经坚持了一段时间.如果我没有正确理解,所有二进制操作都是关联的.因此,如果我们有"x + y + z",则首先出现x + y,然后出现加号z.
但是,不执行左关联会导致无限左递归吗？
到目前为止,我检查过的所有解决方案都是左关联的,或者没有左递归,但不是两者都有.是否可以使用具有这两种属性的语法.它甚至可能吗？
例:
左联想:
Expr = Term | Expr + Term
Term = Element | Term ? Element
Element = x|y|z|(Expr)
左递归消除:
Expr = Term ExprTail
ExprTail = epsilon | + Term ExprTail
Term = Element TermTail
TermTail = epsilon | * Element TermTail
Element = x|y|z|(Expr)
有任何想法吗？
如果运算符是左关联的,则相应的生成将保持递归.
如果您使用LR解析器生成器,那么没有问题.LR算法在处理左递归方面没有问题(尽管可能需要更多的堆栈空间,但任何其他类型的递归都没有问题).
您还可以使用其他自下而上的技术,例如经典运算符优先算法(即shunting yard),但LR解析严格更具表现力,解析器生成器使实现相对简单.
如果你坚持递归下降解析,那是可能的,因为你可以使用循环解析重复的模式(理论上是正确的递归),但是从左到右组合元素.在某种理论意义上,这是AST的树重写,但我怀疑很多程序员编写了这些代码而没有注意到树的修复.