Grammar Parse Baum? - Parsing, Baum, Grammatik, Parse-Baum

Diese Frage bezieht sich auf meine Hausaufgaben, und ich habe keine Ahnung, wie ich das machen soll.

Betrachten Sie die Grammatik

S ← ( L )
S ← a
L ← L , S
L ← S

Zeichnen Sie einen Analysebaum für den Satz ( a , ( a , a ) )

Ich habe versucht, der Struktur zu folgen, und ich ende damit (L,(L,L)) Das scheint jedoch nicht richtig zu sein. Könnte mich jemand in die richtige Richtung bringen?

Antworten:

Hier ist ein Teil von dem, was Sie danach suchen:

Jetzt können Sie den Rest der Arbeit erledigen :)

Schau dir den Satz an (a, (a, a)). Auf welche der rechten Seiten (RHS) kann es passen? Nur die erste, S ← ( L ). Die Wurzel Ihres Baumes wird also eine sein S-Knoten mit drei Kindern: a (-Node, eine L-Knoten und a )-Knoten.

Jetzt müssen Sie herausfinden, was die Kinder von der L-Knoten sind und müssen mit der verbleibenden Eingabe übereinstimmen: a,(a,a). Schauen Sie sich also die Regeln an L auf der LHS. Von diesen Regeln hat man eine RHS, die passen kann a,(a,a)?

Der Analysebaum für (a,(a,a)) ist erhältlich aus einer ganz linken Ableitung von (a,(a,a)):

S => (L)        [S -> (L)]
=> (L,S)      [L -> L,S]
=> (S,S)      [L -> S  ]
=> (a,S)      [S -> a  ]
=> (a,(L))    [S -> (L)]
=> (a,(L,S))  [L -> L,S]
=> (a,(S,S))  [L -> S  ]
=> (a,(a,S))  [S -> a  ]
=> (a,(a,a))  [S -> a  ]

Die Wurzel Ihres Analysebaums ist S. Für jede Umschreibung eines Nichtterminalsymbols imAbleitung, zeichnen Sie den entsprechenden Knoten in den Parser-Baum. Außerdem ist Ihre Grammatik nicht optimal und enthält unter anderem Kettenregeln. Wenn Sie sie entfernen, müssen Sie sie nicht ableiten S von L um abzuleiten a.