Синтаксис направленное определение для грамматики для печати строки синтаксического анализа - PullRequest
Новая
       33

Синтаксис направленное определение для грамматики для печати строки синтаксического анализа

0 голосов
/ 31 марта 2012

---> Рассмотрим грамматику ниже: 

  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.

Это решение в порядке?У меня такое чувство, что оно может быть неточным.

Вот аннотированное дерево разбора. enter image description here

1 Ответ

1 голос
/ 31 марта 2012

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

...