Создать синтаксическое дерево из заданных регулярных выражений (для RE в DFA)

Question

Я изучаю теорию автоматов и сталкиваюсь с некоторыми трудностями при конвертации RE непосредственно в DFA. Этот метод требует создания синтаксического дерева из RE. Но я не могу генерировать.
Мне дают регулярное выражение, например a*b*(a|b)abc

Теперь я хочу создать синтаксическое дерево из этого. Я не хочу программы для этого, но я хочу сделать это вручную. Может кто-нибудь мне помочь?

Answer 1

Вам необходимо выяснить, какие операции представлены этим выражением, в каком порядке они применяются и каковы их операнды.

Например a* означает: "применить * оператор для a Msgstr " В дереве выражений вы получите узел для оператора" звезда "и a узел для символа, на который действует оператор.

Точно так же | обозначает чередование, так что это будет узел в дереве, а дочерние узлы будут подвыражениями чередования.

Операция верхнего уровня - это просто конкатенация, которая будет вашим корневым узлом.

Вот полный AST, полученный из этих правил:

a*b*(a|b)abc

--+ CONCAT
  |
  +-+ STAR
  | |
  | +-- a
  |
  +-+ STAR
  | |
  | +-- b
  |
  +-+ OR
  | |
  | +-- a
  | |
  | +-- b
  |
  +-- a
  |
  +-- b
  |
  +-- c

РЕДАКТИРОВАТЬ: Вы попросили двоичное дерево, преобразование должно быть простым. Я оставлю оба дерева, чтобы вы могли понять это:

              .
             / \
            .   c
           / \
          .   b
         / \
        .   a
       / \
      /   \
     /     \
    .       |
   / \     / \
  *   *   a   b
 /     \
a       b

Обратите внимание, что в приведенном выше дереве используется оператор левой ассоциативной конкатенации.