输入 0.110 上的以下 SDT 应该是什么结果?

Question

请考虑以下具有相应合成属性的语法：

F -> .L  {    F.val = L.val    }
L -> LB  {    L.length = L.length`+ 1}{L.val = L.val + 2^ (-L.length) * B.val}
L -> B   {    L.length = 1, L.val = B.val/2}
B -> 0   {    B.val = 0}
B -> 1   {    B.val = 1}

如果 "F.val" 给出上述语法中 F 生成的二进制分数的值，那么输入时 F.val 的值 {0.110} 是 ____________。(小数点后3位(

解决方案解决方案说答案是 0.875。我想知道他们是如何计算L值的，因为 我们可以看到，当 L.val = 0.75 ，它实际上应该是 1，因为：

L.value = L.value + 2^(- L.length) * B.val
= 0.5 + 2^(-1)*1
= 0.5 + 0.5
= 1

Answer 1

L.length = L.length + 1

像这样写下规则有点模棱两可，因为L用于指代父节点和子节点。在这种情况下，很明显，第一个 L 引用父节点，第二个引用子节点(否则L.length = L.length ...将是无限递归的(，但这在符号中没有明确说明。为了解决这种歧义，我们通常会向子节点添加索引，如下所示：

L ->L1B  { L.length = L1.length + 1}

现在明确表示L引用父节点，L1引用子节点。

记住该符号后，让我们看一下与计算相关的规则：

L.val = L.val + 2 ^ (-L.length) * B.val

很明显，等号后面的L.val必须引用L1.val，否则它将再次无限递归。但L.length实际上可以指任何一个。也就是说，上述内容可以解释为：

L ->L1B  { L.length = L1.length + 1} { L.val = L1.val + 2 ^ (-L1.length) * B.val }

或作为：

L ->L1B  { L.length = L1.length + 1} { L.val = L1.val + 2 ^ (-L.length) * B.val }

使用前一种解释，L1.length是 1，计算结果确实为0.5 + 0.5 = 1。但是，使用后一种解释，我们得到：

L.val = L1.val + 2 ^ (-L.length) * B.val
= 0.5 + 2^-2 * 1
= 0.5 + 0.25
= 0.75

所以后者一定是预期的解释。