0

Есть небольшой формальный С-подобный язык.

Пример кода:

int x = 10;
int i = 0;

while (i < x) {
    i = i + 1;
}

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

1
  • 1
    книгу дракона или что то в этом стиле читали? Если да, то до конца?
    – KoVadim
    5 окт 2013 в 10:28

2 ответа 2

5

Проще всего воспользоваться генератором парсеров, например, парой lex/yacc (flex/bison).

Дерево разбора получится автоматически:

program:
    statements { $$ = new Program($1); }

statements:
    /* empty */ { $$ = new StatementList(); }
  | statements statement { $1->push_back($2); $$ = $1; }

inner_statement:
    compound_statement
  | assignment
  | loop

statement:
    inner_statement
  | vardef

compound_statement:
    '{' statements '}' { $$ = new CompoundStatement($2); }

assignment:
    IDENT '=' expression ';' { $$ = new AssignmentStatement($1, $3); }

loop:
    while_loop
  | for_loop

vardef:
    TYPE IDENT maybe_initializer ';' { $$ = new VarDefinition($1, $2, $3); }

maybe_initializer:
    /* empty */ { $$ = null; }
  | '=' expression { $$ = $2; }

while_loop:
    WHILE '(' expression ')' inner_statement { $$ = new WhileLoop($3, $5); }

и так далее.

Видите, как рекурсивно строится дерево?

1
  • Спасибо. Попробую разобратся.
    – nullptr
    5 окт 2013 в 17:55
3

Для простого языка можно не заморачиваться с генераторами парсеров и разбирать вручную, как например описано в здесь и здесь, только вместо непосредственных вычислений процедуры разбора должны выдавать части дерева разбора. В качестве примера посмотрите также JSON парсер.

5
  • Спасибо. Это мне тоже пригодится )
    – nullptr
    5 окт 2013 в 18:07
  • Вручную несложно пишутся LL-парсеры (recursive descent). Если же язык леворекурсивный, писать LR-парсер вручную не так уж и просто. Например, стандартная грамматика для разбора арифметического выражения, ЕМНИП, не LL. --- И даже для LL-языков я бы писал не вручную, а на каком-нибудь ANTLR.
    – VladD
    6 окт 2013 в 11:11
  • Грамматика арифметических выражений - LL(1): http://en.wikipedia.org/wiki/Recursive_descent_parser
    – rfq
    6 окт 2013 в 12:10
  • @rfq: Хм, и правда. Однако всё же написать правильную LL(1)-грамматику для арифметических выражений не подсматривая не так уж просто. Вот пример (секция «Creating an LL(1) Grammar»).
    – VladD
    6 окт 2013 в 12:29
  • 1
    а зачем ее (грамматику) писать, если по ссылке приведен уже готовый ручной парсер для маленького языка, включающий разбор арифметических выражений.
    – rfq
    6 окт 2013 в 12:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.