0

---> 考虑下面的语法：

  S->SaS|bB
  B->AcB| ε
  A->dAd| ε

对于上面给出的语法，编写打印正在解析的字符串的语法指导定义，并为字符串“bddcab”构造一个带注释的解析树。

解决方案：

现在重写上面的语法我们有：

    S->S1aS2
    S->bB
    B->AcB1
    B-> ε
    A->dA1d
    A-> ε
   ( The numbers 1 and 2 following the non-terminal actually denote subscripts. And the subscripts in above grammar denote instances of the non-terminal.)

上述语法以及语义规则。

    Productions        Semantic Rules

    S->S1aS2        S.val=S1.val+a.lexval + S2.val { print S.val }
    S->bB           S.val=b.lexval + B.val { Print S.val}
    B->AcB1         B.val=A.val+c.lexval + B1.val
    B-> ε
    A->dA1d         A.val=d.lexval  + A1.val + d.lexval
    A-> ε

      ** The '+' operator is merely for concatenation.

这个解决方案好吗？我有一种感觉，它可能不准确。

这是带注释的解析树。在此处输入图像描述

4

1 回答 1

1

我认为 S 规则中的那些打印操作会适得其反，因为 S 可以多次发生。

S 可以生成 SaS。但是这些 S 中的每一个也可以生成 SaS。

基本上，如果您将打印表示构建为语义属性，则只能在完全评估语法后在语法之外进行打印，以确保它只发生一次。

这可以通过引入伪开始符号 X 来显示。 S 仅简化为 X 一次，因此打印只发生一次，val从顶层拉出 final S。

X -> S { print S.val }  // print the top-level S's val, just once.

另一种方法是进行真正的语法指导打印，其中打印的副作用随着解析减少的发生而发生。例如，右手符号中的类似 Yacc 的嵌入规则：

S -> S1 a { print a.lexeme } S2 { /* other semantic rules go here */ }

在识别终端的每条规则中，一旦识别终端就打印终端。所以在这里，我们知道 S1 的减少导致它的所有终端都被打印（通过整个语法的类似规则）。然后我们识别a并打印它，然后识别并减少S2，使其所有终端都被打印。您可能会认识到这与树的中序遍历非常相似。

于 2012-03-31T07:07:08.027 回答