구문 감독 정의

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과 같은 내장 된 규칙 :

터미널을 인식하는 모든 규칙에서 터미널이 인식되는 즉시 인쇄하십시오. 그래서 여기에서 우리는 S1의 감소로 인해 모든 터미널이 인쇄되도록합니다 (문법 전체에서 비슷한 규칙에 의해). 그런 다음 a을 인식하여 인쇄하면 S2가 인식되고 축소되어 모든 터미널이 인쇄됩니다. 이것은 inorder traversal과 매우 흡사하다는 것을 알 수 있습니다.