Грамматика разбора деревьев?

Question

Этот вопрос находится на моей домашней работе по CS, и я не знаю, как это сделать.

Рассмотрим грамматику

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.