Синтаксис Направленного Определения для грамматики, чтобы напечатать строку синтаксического анализа

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 только один раз, поэтому печать происходит только один раз, вытягивая окончательный val с верхнего уровня 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 распознается и уменьшается, заставляя все его терминалы печататься. Вы можете признать, что это близко аналогично обходу дерева.