用于语法语法定向定义打印解析串

Question

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

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. 

此解决方案是否正常？我有一种感觉可能不准确。

这是注释的分析树。

Answer 1

我认为S规则中的那些打印动作会适得其反，因为S可能会出现多次。

S可以产生SaS。但是每个S都可以生成SaS。

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

这可以通过引入一个伪起始符号X来显示.S只是简化为X一次，所以打印只发生一次，从*S拉最后的val。

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，导致其所有终端都被打印。你可能会认识到，这与树的中序遍历非常相似。