Я изучаю теорию автоматов и сталкиваюсь с некоторыми трудностями при преобразовании RE непосредственно в DFA. Этот метод требует создания синтаксического дерева из RE. Но я не могу сгенерировать.
Мне дают регулярное выражение, например, a*b*(a|b)abc
Теперь я хочу создать из этого синтаксическое дерево. Мне не нужна программа для этого, но я хочу сделать это вручную. Может кто-нибудь мне помочь?
Вам нужно выяснить, какие операции представлены этим выражением, в каком порядке они применяются и каковы их операнды.
Например, a* означает: "применить оператор * к a". В дереве выражений вы получите узел для оператора звезды и узел 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
Обратите внимание, что в приведенном выше дереве используется левоассоциативный оператор конкатенации.
