parsing - 读取右递归

Question

我明白在左递归中

A -> Aα | β

所以 A 可以是 β 并且停止或继续并且有 Aα 无限次，因为它在其自身中被解释。所以如果我要解析βαα：

      A 
     / \
    A   α 
   / \
  Α   α
 /
β 

我发现右递归中的相同语法如下：

A-> βA'

A'-> αA'|ε

我可以再次为 βαα 做解析树，但我无法像左递归那样读取产生式规则。有人能解释一下在这个右递归语法中阅读产生式规则的步骤吗？

标签： parsingrecursion

Answer 1

生产规则按以下顺序应用：

A -> 
  -> βA'   (apply A -> βA')
  -> βαA'  (apply A' -> αA')
  -> βααA' (apply A' -> αA')
  -> βαα   (apply A' -> ε)

解析树如下所示：

  A 
 / \
β   A' 
   / \
  α   A'
     / \
    α   A'
        |
        ε

---

删除直接左递归

每个具有直接左递归的规则：

A -> Aa | Ab | Ac | ... | x | y | z

替换为：

A  -> xA' | yA' | zA' | ...
A' -> aA' | bA' | cA' | ε

其中a, b, c, ..., x, y,z是不以 开头的序列A。

重复这个过程，直到没有直接左递归。