Grammar Parse tree?

Question

This question is on my CS homework and I have no idea how to do it.

Consider the grammar

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

Нарисуйте дерево разбора для предложения ( a , ( a , a ) )

Я попытался следовать структуре, и я в конечном итоге (L,(L,L)) Это не кажется правильным, хотя. Кто-нибудь может подтолкнуть меня в правильном направлении?

Answer 1

Вот часть того, что вы ищете:

Теперь вы можете сделать остальную часть работы:)

Answer 2

Посмотрите на предложение (a, (a, a)), С какой из правых сторон (RHS) это может соответствовать? Только первое, S ← ( L ), Таким образом, корень вашего дерева будет S-узел с тремя детьми: (узел L-узел и )-узел.

Теперь вам нужно выяснить, что дети из L-узлы, и они должны соответствовать оставшимся входным данным: a,(a,a), Итак, посмотрите на правила, которые имеют L на LHS. Из тех правил, у которых есть RHS, который может соответствовать a,(a,a)?

Answer 3

Дерево разбора для (a,(a,a)) можно получить из самого левого вывода (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  ]

Корень вашего дерева разбора S, Для каждой перезаписи нетерминального символа в деривации нарисуйте соответствующий узел в дереве разбора. Кроме того, ваша грамматика не является оптимальной и, среди прочего, содержит правила цепочки. Удаление их предотвратит необходимость извлечения S от L чтобы вывести a,