VPF::Генерация асд из постфиксной записи.

rudvil

Дата 19.5.2010, 21:09 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

Интересуют способы создания дерева из постфиксной записи, не простой-типа

Код


infix [1+2*3]
postfix [1 2 3 mult add]

, тут всё понятно-если на входе цифра кидаем её в стек, если оператор берем 2 посл елемента из стека и создаем дерево с корнем-оператором и 2-умя потомками(которые мы до этого взяли из стека), пихаем дерево в стек и так далее...
А как обойтись с более сложными записями, например дана след. ebnf грамматика

Код


translation_unit = ((func_def)[func_def] | (decl)[declaration])+;

func_def = 'def' NAME[name] (param_list)[params_expr] (block)[func_body];

param_list = '(' ((const_expr)[param_expr] (',' const_expr)[param_expr]*)? ')';

arg_list = '(' ((const_expr)[arg_expr] (',' const_expr)[arg_expr]*)? ')';

decl = unary_expr ('=' expr)[assign_expr]? ';';

stmt = (expr_stmt)[expr_stmt] |
       (if_stmt)[if_stmt] |
       (while_stmt)[while_stmt] |
       ('continue' ';')[continue] |
       ('break' ';')[break] |
       ('return' (expr)[return_expr]? ';')[return]
       ;

if_stmt = 'if' ('(' expr ')')[if_cond_expr]
            (block)[if_body]
          else_stmt?
          ;

else_stmt = 'else'
             (block)[else_body]
            ;

while_stmt = 'while' ('(' expr ')')[while_cond_expr]
              (block)[while_body]
             ;

block = '{' decl* stmt* '}';

expr_stmt = expr ';';

expr = assign_expr (',' assign_expr)[comma_expr]*;

assign_expr = logical_or_expr ('=' logical_or_expr)[assign_expr]*;

const_expr = logical_or_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] |
                (arg_list)[func_call_expr] |
                ('.' postfix_expr)[member] |
                ('++')[post_increment] |
                ('--')[post_decrement]
               )*
               ;

и такой текст-парсеру

Код

def main(argc, argv[]) {
  print('Hello World!');
  return 0;
}

, мы получим след.

Код

func_def
func_body
return
return_expr
const_number
0
func_call_expr
arg_expr
const_string
Hello World!
name
print
params_expr
param_expr
array_subscript_expr
name
argv
param_expr
name
argc
name
main

как с этим справляться?
Сгенерированное дерево из этой записи(см. выше) должно быть таким

Т.е. нужен универсальный способ(алгоритм?), что-бы при изменении грамматики-не пришлось бы переписывать что-либо в коде, для корректного генерирования абстрактного синтаксического дерева, спасибо.

Это сообщение отредактировал(а) rudvil - 19.5.2010, 21:11

--------------------

xor

ИванМ

Дата 19.5.2010, 21:38 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1260
Регистрация: 19.6.2006
Где: СПб

Репутация: 1
Всего: 23

Вообще деревьями лучше не пользоваться. Постфиксная запись самодостаточная.
Также существуют стандартные библиотеки для работы с грамматиками. Например, boost::Spirit. Правда, с помощью него ошибки не проверить. Должен быть код изначально правильный.

rudvil

Дата 19.5.2010, 21:46 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

Цитата(ИванМ @ 19.5.2010, 20:38)

Т.е. выполнять код "на лету" из постфиксной записи быстрее, чем прогонять аналогичное дерево?
На данный момент у меня готов лексер+парсер, т.е. проверить что эффективней пока-что не могу...

з.ы. spirit'ом не пользуюсь - не понравился, слишком навороченный да и компилирует жуть как долго, поэтому использую самописный парсер.

--------------------

xor

ИванМ

Дата 19.5.2010, 21:55 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1260
Регистрация: 19.6.2006
Где: СПб

Репутация: 1
Всего: 23

rudvil, быстрее и с точки зрения выполнения, а особенно сточки зрения трансляции исходного кода. Для постфиксной записи достаточно одного прохода, а в случае с деревом - больше одного. К тому же в случае постфиксной записи памяти меньше расходуется и она динамически освобождается, что для дерева ни так.

GoldFinch

Дата 19.5.2010, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26

а что лучше, постфиксная запись, или префиксная запись? и вообще, в чем у них принципиальная разница?

ИванМ

Дата 19.5.2010, 22:06 (ссылка)

(голосов:2)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1260
Регистрация: 19.6.2006
Где: СПб

Репутация: 1
Всего: 23

Цитата(GoldFinch @ 19.5.2010, 22:01

)

а что лучше, постфиксная запись, или префиксная запись? и вообще, в чем у них принципиальная разница?

С постфиксной удобнее работать.
Например, выражение 1 + 2

в постфиксной записи:
1 2 +
выполнение:
1->стек
2->cтек
+: стек->x, стек->y, (x+y)->стек
На выходе в стеке 3, как и положено

в префиксной записи:
+ 1 2
такое быстро реализовать с помощью стека проблематично

rudvil

Дата 19.5.2010, 22:47 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

Цитата(ИванМ @ 19.5.2010, 20:55)

Спасибо за совет, а то я как зациклился над этим "деревом"... так всё и приостановилось - пока не нашел бы решения.
Теперь смело продолжу разработку своего я.п.
Ещё раз спасибо!

--------------------

xor

rudvil

Дата 20.5.2010, 09:32 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

Рано я обрадовался, а как тогда все-же обойтись без дерева, если даны 3 простых выражения основанные на этой грамматики

Код

translation_unit = (expr ';')[program]*;

expr = multiplicative_expr (
                            ('+' multiplicative_expr)[addition] |
                            ('-' multiplicative_expr)[subtraction]
                           )*
                           ;

multiplicative_expr = postfix_expr (
                                    ('*' postfix_expr)[multiplication] |
                                    ('/' postfix_expr)[division] |
                                    ('%' postfix_expr)[modulus]
                                   )*
                                   ;

postfix_expr = NUM[const_number] | '(' expr ')';

и скормить парсеру

Код

1+2*3;
4-5/6;
7*8+9;

то мы, получим вот-что

Код

program
addition
const_number
9
multiplication
const_number
8
const_number
7
program
subtraction
division
const_number
6
const_number
5
const_number
4
program
addition
multiplication
const_number
3
const_number
2
const_number
1

запись так-сказать получается "снизу вверх", тогда как нужно выполнение выражений "сверху вниз" и это наблюдается везде, не только в выражениях, но и в конструкциях типа иф-елсе и.т.д.
Одним проходом "на лету" никак не получится.
Другое дело, дерево - там все было-бы разложено по местам и все становится понятным.
Поэтому наверное вернусь к асд, пусть не так быстро , зато понятно что - к чему.

все ещё акутально

Цитата

Это сообщение отредактировал(а) rudvil - 20.5.2010, 09:33

--------------------

xor

xvr

Дата 20.5.2010, 12:00 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата

универсальный способ

называется 'генератор парсеров'. Это может быть уже упоминавшийся тут boost::spirit, или bison/yacc или antlr или еще какой нибудь

PS. 1+2*3 - это не 'постфиксная запись', а инфиксная.

Это сообщение отредактировал(а) xvr - 20.5.2010, 12:02

rudvil

Дата 20.5.2010, 12:33 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

Цитата(xvr)

называется 'генератор парсеров'. Это может быть уже упоминавшийся тут boost::spirit, или bison/yacc или antlr или еще какой нибудь

генераторы.. уйй как не хочется их использовать smile

Цитата(xvr)

PS. 1+2*3 - это не 'постфиксная запись', а инфиксная.

это я знаю, спасибо.

Гугл облазил, есть только примеры бинарных деревьев для простых выражений...
а если потомков может быть не 2, а 4 или 9 или...

Есть идея пройтись разок по грамматики и создать список всех правил и какие подправила могут быть у текущего правила...
т.е. если посмотреть на грамматику в первом посте, то для первых 2-ух правил можно создать след таблицу:

std::map<std::string/*название правила*/, std::list<std::string>/*может содержать...*/ > table;

1-ое правило "translation_unit" может содержать в себе "func_def" и "declaration"
2-ое правило "func_def" содержит "name", "params_expr" и "func_body"

т.е. то что в квадратных скобках...

вот... и благодаря этой таблице создать из этого

Код

func_def
func_body
return
return_expr
const_number
0
func_call_expr
arg_expr
const_string
Hello World!
name
print
params_expr
param_expr
array_subscript_expr
name
argv
param_expr
name
argc
name
main

синтаксическое дерево как тут

т.е. первое что мы видим это - "func_def" далее идет "func_body", если "func_body" может находиться в "func_def" то создаем дерево с корнем "func_def" и потомком "func_body" ну и далее обрабатываем похожим образом все оставшееся...

конечно этот способ не идеален... но т.к. пока других вариантов не вижу - остановлюсь на нем.

--------------------

xor

ИванМ

Дата 20.5.2010, 13:35 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1260
Регистрация: 19.6.2006
Где: СПб

Репутация: 1
Всего: 23

rudvil, тот пример, что вы привели, также можно реализовать с помощью постфиксной записи. И без деревьев. Просто нужно создать еще один дополнительный стек. Если надо, могу выслать один свой проект. Там с помощью постфиксной записи реализованы очень сложные вычисления: приоритет операций, условные операторы и проч..

rudvil

Дата 30.5.2010, 23:40 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

После изучения примера mini_c в boost::spirit который "на лету" производит все операции и работает по такому же принципу как мне хотелось изначально, я пришел к выводу что мне это все-же не подходит.
Во первых, насколько я теперь понимаю - без дерева будет крайне неудобно проводить семантический анализ, а он уж точно мне будет нужен.
Во вторых, я почитал как устроен питон и мне кажется что имеет смысл продвигаться в том же направлении, т.е. транслировать в упрощенный код и уже этот упрощенный код выполнять "на лету" smile

--------------------

xor

xvr

Дата 31.5.2010, 00:31 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Если нужен какой то нетривиальный анализ (и возможно какие то оптимизации, или просто преобразования), то без дерева (или DAG) обойтись не получится (даже в теории)

rudvil

Дата 15.6.2010, 13:48 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 20.11.2009
Где: Latvia/Riga

Репутация: 2
Всего: 3

Дабы не создавать новую тему спрошу тут, какие преимущества у меня будут если я буду использовать при динамическом парсинге, NFA/DFA вместо дерева.
Поясню насчет дерева, вот EBNF грамматика

Код

expr = multiplicative_expr (
                            ('+' multiplicative_expr) |
                            ('-' multiplicative_expr)
                           )*
                           ;

multiplicative_expr = postfix_expr (
                                    ('*' postfix_expr) |
                                    ('/' postfix_expr)
                                   )*
                                   ;

postfix_expr = (
                NAME |
                NUM |
                STR |
                '(' expr ')'
               )
               ;

после её анализа у меня на выходе получается след. дерево

Код

(expr)
(Node)-|
       |-(Once)-|
       |        |-multiplicative_expr-(Identifier)
       |
       |-(Zero or more)-|
       |                |-(Node)-|
       |                |        |-(Once)-|
       |                |        |        |-(Or)-|
       |                |        |        |      |-(Node)-|
       |                |        |        |      |        |-(Once)-|
       |                |        |        |      |        |        |-(Node)-|
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-+-(Terminal)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-multiplicative_expr-(Identifier)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |
       |                |        |        |      |        |
       |                |        |        |      |
       |                |        |        |      |-(Node)-|
       |                |        |        |      |        |-(Once)-|
       |                |        |        |      |        |        |-(Node)-|
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |---(Terminal)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-multiplicative_expr-(Identifier)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |
       |                |        |        |      |        |
       |                |        |        |      |
       |                |        |        |
       |                |        |
       |                |
       |
 

(multiplicative_expr)
(Node)-|
       |-(Once)-|
       |        |-postfix_expr-(Identifier)
       |
       |-(Zero or more)-|
       |                |-(Node)-|
       |                |        |-(Once)-|
       |                |        |        |-(Or)-|
       |                |        |        |      |-(Node)-|
       |                |        |        |      |        |-(Once)-|
       |                |        |        |      |        |        |-(Node)-|
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-*-(Terminal)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-postfix_expr-(Identifier)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |
       |                |        |        |      |        |
       |                |        |        |      |
       |                |        |        |      |-(Node)-|
       |                |        |        |      |        |-(Once)-|
       |                |        |        |      |        |        |-(Node)-|
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-/-(Terminal)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |        |-(Once)-|
       |                |        |        |      |        |        |        |        |-postfix_expr-(Identifier)
       |                |        |        |      |        |        |        |
       |                |        |        |      |        |        |
       |                |        |        |      |        |
       |                |        |        |      |
       |                |        |        |
       |                |        |
       |                |
       |
 

(postfix_expr)
(Node)-|
       |-(Once)-|
       |        |-(Node)-|
       |        |        |-(Once)-|
       |        |        |        |-(Or)-|
       |        |        |        |      |-(Node)-|
       |        |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |-NAME-(Identifier)
       |        |        |        |      |        |
       |        |        |        |      |
       |        |        |        |      |-(Node)-|
       |        |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |-(Or)-|
       |        |        |        |      |        |        |      |-(Node)-|
       |        |        |        |      |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |      |        |        |-(Or)-|
       |        |        |        |      |        |        |      |        |        |      |-(Node)-|
       |        |        |        |      |        |        |      |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |      |        |        |      |        |        |-NUM-(Identifier)
       |        |        |        |      |        |        |      |        |        |      |        |
       |        |        |        |      |        |        |      |        |        |      |
       |        |        |        |      |        |        |      |        |        |      |-(Node)-|
       |        |        |        |      |        |        |      |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |      |        |        |      |        |        |-STR-(Identifier)
       |        |        |        |      |        |        |      |        |        |      |        |
       |        |        |        |      |        |        |      |        |        |      |
       |        |        |        |      |        |        |      |        |        |
       |        |        |        |      |        |        |      |        |
       |        |        |        |      |        |        |      |
       |        |        |        |      |        |        |      |-(Node)-|
       |        |        |        |      |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |      |        |        |-(-(Terminal)
       |        |        |        |      |        |        |      |        |
       |        |        |        |      |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |      |        |        |-expr-(Identifier)
       |        |        |        |      |        |        |      |        |
       |        |        |        |      |        |        |      |        |-(Once)-|
       |        |        |        |      |        |        |      |        |        |-)-(Terminal)
       |        |        |        |      |        |        |      |        |
       |        |        |        |      |        |        |      |
       |        |        |        |      |        |        |
       |        |        |        |      |        |
       |        |        |        |      |
       |        |        |        |
       |        |        |
       |        |
       |

Порывшись в исходниках того-же питона, стало ясно что он для парсинга использует NFA/DFA, есть ли смысл перейти на использование NFA/DFA вместо выше описанного мною дерева?
Понятно что у питона парсер статический т.е. сгенерированный.
Но т.к. я хочу использовать динамический парсинг, хотелось бы узнать - что будет эффективней?
Динамически генерируемое дерево или динамически генерируемые NFA/DFA?, и естественно последующий парсинг...

Это сообщение отредактировал(а) rudvil - 15.6.2010, 13:50

--------------------

xor

xvr

Дата 15.6.2010, 19:15 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

NFA/DFA не заменят стекового парсера (LL1/LR1/LALR1/etc) - это разный класс граматик.
Например ваша грамматика в NFA/DFA не ляжет. NFA/DFA описывают класс грамматик, соотвествующий регулярным выражениям.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »