infix [1+2*3]
postfix [1 2 3 mult add]
Алгоритм генерации асд из постфиксно-подобной записи
Добрый день, интересуют алгоритм создания дерева из постфиксно-подобной записи, не простой-типа
А из более сложной записи, например дана след. ebnf грамматика.
и такой входящий текст-парсеру
Как многие уже скорее всего догадались, парсер при удачном выполнении правила или чего-либо выводит то что написано в квадратных скобках, на выходе мы получим след.
Вот тут я и застопорился, как с этой постфиксно-подобной записи сконструировать абстрактное синтаксическое дерево?
По идее дерево должно быть такимhttp://i073.radikal.ru/1006/2f/c4be6c8dee4a.jpg
з.ы. парсер самописный, динамический.
Заранее спасибо.
Код:
Код:
translation_unit = program[program];
program = stmt+;
stmt = expr_stmt[expr_stmt] |
if_stmt[if_stmt] |
for_stmt[for_stmt] |
while_stmt[while_stmt] |
('continue' ';')[continue] |
('break' ';')[break] |
('return' return_expr? ';')[return]
;
return_expr = expr[return_expr];
if_stmt = 'if' ('(' expr ')')[if_cond_expr]
block[if_body]
else_stmt[else_body]?
;
else_stmt = 'else'
block
;
for_stmt = 'for'
'('
expr[for_decl_expr]? ';'
expr[for_cond_expr]? ';'
expr[for_act_expr]?
')'
block[for_body]
;
while_stmt = 'while' ('(' expr ')')[while_cond_expr]
block[while_body]
;
block = '{' stmt* '}';
expr_stmt = expr ';';
expr = assign_expr (',' assign_expr)[comma_expr]*;
assign_expr = cond_expr ('=' cond_expr)[assign_expr]*;
cond_expr = logical_or_expr ternary_expr[ternary_expr]?;
ternary_expr = ('?' expr[if_true] ':' cond_expr[if_false]);
const_expr = cond_expr;
logical_or_expr = logical_and_expr ('||' logical_and_expr)[logical_or]*;
logical_and_expr = bitwise_or_expr ('&&' bitwise_or_expr)[logical_and]*;
bitwise_or_expr = bitwise_xor_expr ('|' bitwise_xor_expr)[bitwise_or]*;
bitwise_xor_expr = bitwise_and_expr ('^' bitwise_and_expr)[bitwise_xor]*;
bitwise_and_expr = equality_expr ('&' equality_expr)[bitwise_and]*;
equality_expr = relational_expr (
('==' relational_expr)[equal] |
('!=' relational_expr)[not_equal]
)*
;
relational_expr = shift_expr (
('<' shift_expr)[less] |
('>' shift_expr)[greater] |
('<=' shift_expr)[less_equal] |
('>=' shift_expr)[greater_equal]
)*
;
shift_expr = additive_expr (
('<<' additive_expr)[bitwise_left_shift] |
('>>' additive_expr)[bitwise_right_shift]
)*
;
additive_expr = multiplicative_expr (
('+' multiplicative_expr)[addition] |
('-' multiplicative_expr)[subtraction]
)*
;
multiplicative_expr = unary_expr (
('*' unary_expr)[multiplication] |
('/' unary_expr)[division] |
('%' unary_expr)[modulus]
)*
;
unary_expr = (
'++'[pre_increment] |
'--'[pre_decrement]
)*
(
(
('+' unary_expr)[positive] |
('-' unary_expr)[negative] |
('!' unary_expr)[not]
) |
postfix_expr
)
;
postfix_expr = (
NAME[name] |
NUM[const_number] |
STR[const_string] |
'(' expr ')'
)
(
('[' const_expr? ']')[array_subscript_expr] |
func_call_expr[func_call_expr] |
('.' postfix_expr)[member_expr] |
'++'[post_increment] |
'--'[post_decrement]
)*
;
func_call_expr = '(' (arg_expr (',' arg_expr)*)? ')';
arg_expr = assign_expr[arg_expr];
program = stmt+;
stmt = expr_stmt[expr_stmt] |
if_stmt[if_stmt] |
for_stmt[for_stmt] |
while_stmt[while_stmt] |
('continue' ';')[continue] |
('break' ';')[break] |
('return' return_expr? ';')[return]
;
return_expr = expr[return_expr];
if_stmt = 'if' ('(' expr ')')[if_cond_expr]
block[if_body]
else_stmt[else_body]?
;
else_stmt = 'else'
block
;
for_stmt = 'for'
'('
expr[for_decl_expr]? ';'
expr[for_cond_expr]? ';'
expr[for_act_expr]?
')'
block[for_body]
;
while_stmt = 'while' ('(' expr ')')[while_cond_expr]
block[while_body]
;
block = '{' stmt* '}';
expr_stmt = expr ';';
expr = assign_expr (',' assign_expr)[comma_expr]*;
assign_expr = cond_expr ('=' cond_expr)[assign_expr]*;
cond_expr = logical_or_expr ternary_expr[ternary_expr]?;
ternary_expr = ('?' expr[if_true] ':' cond_expr[if_false]);
const_expr = cond_expr;
logical_or_expr = logical_and_expr ('||' logical_and_expr)[logical_or]*;
logical_and_expr = bitwise_or_expr ('&&' bitwise_or_expr)[logical_and]*;
bitwise_or_expr = bitwise_xor_expr ('|' bitwise_xor_expr)[bitwise_or]*;
bitwise_xor_expr = bitwise_and_expr ('^' bitwise_and_expr)[bitwise_xor]*;
bitwise_and_expr = equality_expr ('&' equality_expr)[bitwise_and]*;
equality_expr = relational_expr (
('==' relational_expr)[equal] |
('!=' relational_expr)[not_equal]
)*
;
relational_expr = shift_expr (
('<' shift_expr)[less] |
('>' shift_expr)[greater] |
('<=' shift_expr)[less_equal] |
('>=' shift_expr)[greater_equal]
)*
;
shift_expr = additive_expr (
('<<' additive_expr)[bitwise_left_shift] |
('>>' additive_expr)[bitwise_right_shift]
)*
;
additive_expr = multiplicative_expr (
('+' multiplicative_expr)[addition] |
('-' multiplicative_expr)[subtraction]
)*
;
multiplicative_expr = unary_expr (
('*' unary_expr)[multiplication] |
('/' unary_expr)[division] |
('%' unary_expr)[modulus]
)*
;
unary_expr = (
'++'[pre_increment] |
'--'[pre_decrement]
)*
(
(
('+' unary_expr)[positive] |
('-' unary_expr)[negative] |
('!' unary_expr)[not]
) |
postfix_expr
)
;
postfix_expr = (
NAME[name] |
NUM[const_number] |
STR[const_string] |
'(' expr ')'
)
(
('[' const_expr? ']')[array_subscript_expr] |
func_call_expr[func_call_expr] |
('.' postfix_expr)[member_expr] |
'++'[post_increment] |
'--'[post_decrement]
)*
;
func_call_expr = '(' (arg_expr (',' arg_expr)*)? ')';
arg_expr = assign_expr[arg_expr];
Код:
hello = 'Hello World!';
for (i = 0; i < hello.length(); ++i) {
print(hello);
}
for (i = 0; i < hello.length(); ++i) {
print(hello);
}
Код:
program
for_stmt
for_body
expr_stmt
func_call_expr
arg_expr
array_subscript_expr
name
i
name
hello
name
print
for_act_expr
name
i
pre_increment
for_cond_expr
less
member_expr
func_call_expr
name
length
name
hello
name
i
for_decl_expr
assign_expr
const_number
0
name
i
expr_stmt
assign_expr
const_string
Hello World!
name
hello
for_stmt
for_body
expr_stmt
func_call_expr
arg_expr
array_subscript_expr
name
i
name
hello
name
for_act_expr
name
i
pre_increment
for_cond_expr
less
member_expr
func_call_expr
name
length
name
hello
name
i
for_decl_expr
assign_expr
const_number
0
name
i
expr_stmt
assign_expr
const_string
Hello World!
name
hello
Вот тут я и застопорился, как с этой постфиксно-подобной записи сконструировать абстрактное синтаксическое дерево?
По идее дерево должно быть такимhttp://i073.radikal.ru/1006/2f/c4be6c8dee4a.jpg
з.ы. парсер самописный, динамический.
Заранее спасибо.
вобще-то парсер мог бы сразу строить АСД, и это было бы проще т.к.алгоритм разбора грамматики -- это по сути алгоритм обхода дерева.
зачем нужна промежуточная стадия?
зачем нужна промежуточная стадия?
Цитата: LM(AL/M)
вобще-то парсер мог бы сразу строить АСД, и это было бы проще т.к.алгоритм разбора грамматики -- это по сути алгоритм обхода дерева.
зачем нужна промежуточная стадия?
зачем нужна промежуточная стадия?
Сразу скорее всего не получится, т.к. парсер выдает коды не сверху вниз как написано у меня, а снизу вверх, т.е. не так
Код:
expr_stmt
assign_expr
const_string
Hello World!
name
hello
assign_expr
const_string
Hello World!
name
hello
Код:
hello
name
Hello World!
const_string
assign_expr
expr_stmt
name
Hello World!
const_string
assign_expr
expr_stmt
Или-же я чего-то недопонимаю?
ага, так и знал что у вас что-то не так написано
так вот если хотите использовать постфиксную запись то тогда парсер должен для каждого элемента возвращать ещё и кол-во потомков, тогда преобразование в АСД-- элементарный рекрсивный алгоритм
ну а если не использовать постфикс то при разборе очередного узла грамматического дерева можно было бы на лету строить соотв. узел результирующего АСД, ничего сложного нет
вообще при правильном подходе алгоритм обхода дерева должен быть отделён от алгоритма обработки узлов (см. паттерн проектирования Visitor) -- в этом случае можно было бы по желанию получать на выходе и постфиксную запись и АСД и любую другую структуру
так вот если хотите использовать постфиксную запись то тогда парсер должен для каждого элемента возвращать ещё и кол-во потомков, тогда преобразование в АСД-- элементарный рекрсивный алгоритм
ну а если не использовать постфикс то при разборе очередного узла грамматического дерева можно было бы на лету строить соотв. узел результирующего АСД, ничего сложного нет
вообще при правильном подходе алгоритм обхода дерева должен быть отделён от алгоритма обработки узлов (см. паттерн проектирования Visitor) -- в этом случае можно было бы по желанию получать на выходе и постфиксную запись и АСД и любую другую структуру
2LM(AL/M)
Спасибо, кажется начинаю понимать и если я правильно понял-то у меня все-же можно реализовать одновременно построение дерева и поиск совпадений.
Например для грамматики
у меня получится вот такое дерево
которое затем скармливается парсеру, а он в свою очередь рекурсивно проходит по дереву в поисках совпадения.
me пошел экспериментировать =]
Спасибо, кажется начинаю понимать и если я правильно понял-то у меня все-же можно реализовать одновременно построение дерева и поиск совпадений.
Например для грамматики
Код:
expr = multiplicative_expr (
('+' multiplicative_expr)[addition] |
('-' multiplicative_expr)[subtraction]
)*
;
multiplicative_expr = postfix_expr (
('*' postfix_expr)[multiplication] |
('/' postfix_expr)[division]
)*
;
postfix_expr = (
NAME[identifier] |
NUM[number] |
STR[string] |
'(' expr ')'
)
;
('+' multiplicative_expr)[addition] |
('-' multiplicative_expr)[subtraction]
)*
;
multiplicative_expr = postfix_expr (
('*' postfix_expr)[multiplication] |
('/' postfix_expr)[division]
)*
;
postfix_expr = (
NAME[identifier] |
NUM[number] |
STR[string] |
'(' expr ')'
)
;
Код:
(expr)
(Node)-|
|-(Once)-|
| |-multiplicative_expr-(Identifier)
|
|-(Zero or more)-|
| |-(Node)-|
| | |-(Once)-|
| | | |-(Or)-|
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[addition]-|
| | | | | | | |-(Once)-|
| | | | | | | | |-+-(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-multiplicative_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[subtraction]-|
| | | | | | | |-(Once)-|
| | | | | | | | |---(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-multiplicative_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | |
| | |
| |
|
(multiplicative_expr)
(Node)-|
|-(Once)-|
| |-postfix_expr-(Identifier)
|
|-(Zero or more)-|
| |-(Node)-|
| | |-(Once)-|
| | | |-(Or)-|
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[multiplication]-|
| | | | | | | |-(Once)-|
| | | | | | | | |-*-(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-postfix_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[division]-|
| | | | | | | |-(Once)-|
| | | | | | | | |-/-(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-postfix_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | |
| | |
| |
|
(postfix_expr)
(Node)-|
|-(Once)-|
| |-(Node)-|
| | |-(Once)-|
| | | |-(Or)-|
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-NAME-(Identifier)-[identifier]
| | | | | |
| | | | |
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Or)-|
| | | | | | | |-(Node)-|
| | | | | | | | |-(Once)-|
| | | | | | | | | |-(Or)-|
| | | | | | | | | | |-(Node)-|
| | | | | | | | | | | |-(Once)-|
| | | | | | | | | | | | |-NUM-(Identifier)-[number]
| | | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |-(Node)-|
| | | | | | | | | | | |-(Once)-|
| | | | | | | | | | | | |-STR-(Identifier)-[string]
| | | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | |
| | | | | | | | |
| | | | | | | |
| | | | | | | |-(Node)-|
| | | | | | | | |-(Once)-|
| | | | | | | | | |-(-(Terminal)
| | | | | | | | |
| | | | | | | | |-(Once)-|
| | | | | | | | | |-expr-(Identifier)
| | | | | | | | |
| | | | | | | | |-(Once)-|
| | | | | | | | | |-)-(Terminal)
| | | | | | | | |
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | |
| | |
| |
|
(Node)-|
|-(Once)-|
| |-multiplicative_expr-(Identifier)
|
|-(Zero or more)-|
| |-(Node)-|
| | |-(Once)-|
| | | |-(Or)-|
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[addition]-|
| | | | | | | |-(Once)-|
| | | | | | | | |-+-(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-multiplicative_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[subtraction]-|
| | | | | | | |-(Once)-|
| | | | | | | | |---(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-multiplicative_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | |
| | |
| |
|
(multiplicative_expr)
(Node)-|
|-(Once)-|
| |-postfix_expr-(Identifier)
|
|-(Zero or more)-|
| |-(Node)-|
| | |-(Once)-|
| | | |-(Or)-|
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[multiplication]-|
| | | | | | | |-(Once)-|
| | | | | | | | |-*-(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-postfix_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Node)-[division]-|
| | | | | | | |-(Once)-|
| | | | | | | | |-/-(Terminal)
| | | | | | | |
| | | | | | | |-(Once)-|
| | | | | | | | |-postfix_expr-(Identifier)
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | |
| | |
| |
|
(postfix_expr)
(Node)-|
|-(Once)-|
| |-(Node)-|
| | |-(Once)-|
| | | |-(Or)-|
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-NAME-(Identifier)-[identifier]
| | | | | |
| | | | |
| | | | |-(Node)-|
| | | | | |-(Once)-|
| | | | | | |-(Or)-|
| | | | | | | |-(Node)-|
| | | | | | | | |-(Once)-|
| | | | | | | | | |-(Or)-|
| | | | | | | | | | |-(Node)-|
| | | | | | | | | | | |-(Once)-|
| | | | | | | | | | | | |-NUM-(Identifier)-[number]
| | | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | | |-(Node)-|
| | | | | | | | | | | |-(Once)-|
| | | | | | | | | | | | |-STR-(Identifier)-[string]
| | | | | | | | | | | |
| | | | | | | | | | |
| | | | | | | | | |
| | | | | | | | |
| | | | | | | |
| | | | | | | |-(Node)-|
| | | | | | | | |-(Once)-|
| | | | | | | | | |-(-(Terminal)
| | | | | | | | |
| | | | | | | | |-(Once)-|
| | | | | | | | | |-expr-(Identifier)
| | | | | | | | |
| | | | | | | | |-(Once)-|
| | | | | | | | | |-)-(Terminal)
| | | | | | | | |
| | | | | | | |
| | | | | | |
| | | | | |
| | | | |
| | | |
| | |
| |
|
me пошел экспериментировать =]
расскажешь об успехах ))