Как сгенерировать синтаксическое дерево для конкретного предложения типа a+b*c, где id->a|b|c?

Question

Как сгенерировать синтаксическое дерево для конкретного предложения типа a+b*c, где id->a|b|c?

Рассмотрим грамматику: E-> E+E|EE|E*E|E/E|(E)|id

Я пытался по крайней мере 5 часов, чтобы решить эту проблему, но не смог. Пожалуйста, скажите мне,

в чем идея решить эту проблему?
Как это реализовать?

0

compiler-construction compiler-optimization automata-theory

Источник

user6714430 27 окт '17 в 01:57

1 ответ

Решение

Другие вопросы по тегам compiler-construction compiler-optimization automata-theory

user6034255 27 окт '17 в 08:13 2017-10-27 08:13 · Accepted Answer · 2017-10-27 08:13

Синтаксическое дерево строится путем синтаксического анализа, который в некотором смысле применяет грамматику в обратном порядке. Итак, вы видите, что a, b и c могут исходить только от id, который, в свою очередь, может исходить только от E. Теперь вы находитесь в E+E*E. Вы можете сначала уменьшить E + E или E*E, а затем другой. В результате E является корнем дерева. Это одно из двух возможных синтаксических деревьев (первое сокращающее E*E)

  E
 /| \
E +   E
|    /|\
id  E * E
|   |   |
a   id  id
    |   |
    b   c

Что касается реализации, вам нужно будет указать, где и с какой целью вы хотите реализовать это.