Gramatika Parse tree? - parsovanie, strom, gramatika, parse-strom

Táto otázka sa týka mojej domácej práce a nemám tušenie, ako to urobiť.

Zvážte gramatiku

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

Nakreslite strom pre analýzu ( a , ( a , a ) )

Snažil som sa sledovať štruktúru a skončila som (L,(L,L)) To však nie je správne, môže mi niekto tlačiť správnym smerom?

odpovede:

Tu je časť toho, čo ste po:

Teraz si môžete urobiť zvyšok práce :)

Pozrite sa na vetu (a, (a, a)), Ktorá z pravých strán (RHS) sa môže zhodovať? Len prvý, S ← ( L ), Takže koreň vášho stromu bude S-node s tromi deťmi: a (-node, an L-node a a )-node.

Teraz musíte zistiť, čo deti z L-node a musia zodpovedať zostávajúcemu vstupu: a,(a,a), Pozrite sa na pravidlá, ktoré majú L na LHS. Z týchto pravidiel, ktoré majú RHS, ktoré sa môžu zhodovať a,(a,a)?

Analyzátor pre (a,(a,a)) je možné získať z ľavej odvodenosti (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  ]

Koreň vášho parseru je S, Pre každé prepísanie neterminálneho symbolu vodvodenie, nakreslite príslušný uzol v parse stromu. Tiež vaša gramatika nie je optimálna a okrem iného obsahuje reťazové pravidlá. Odstránením by sa zabránilo tomu, že by ste museli odvodiť S z L aby sme odvodili a.