compiler study 5 - crowbar whole workflow

compile

---

I debugged the crowbar program, just have a rough idea how the crowbar works.

test case 1

preparation

• write a crowbar program :

    print("hoge\tpiyo\n\\n");

save it as a file, test.crb.

• debug the program

    lldb --source test/br_aliases crowbar test/test.crb

• contents of br_aliases

command alias bfl breakpoint set -f %1 -l %2
bfl main.c 21
bfl create.c 121
bfl create.c 152
bfl create.c 207
bfl execute.c 298
bfl eval.c 746
bfl eval.c 683
bfl eval.c 656
bfl eval.c 587

begin to debug :

compile process

why in this print case, crb_create_funciton_call_expression got triggered.
go back to crowbar.y, you would see this :

primary_expression
        : IDENTIFIER LP argument_list RP
        {
            $$ = crb_create_function_call_expression($1, $3);
        }
        | IDENTIFIER LP RP
        {
            $$ = crb_create_function_call_expression($1, NULL);
        }

print("hello"); exactly match the pattern.
here is the call graph from doxygen

intepret process

here is the interpret process from doxygen

dispose interpreter

test cases 2

preparation

print("3 + 5.." + (3 + 5) + "\n"); #this is a comment

test2.crb

debug

lex tokenize process

I used pvtrace and graphviz dynamically analyze the code, here is the pic :

1. create identifier

   * thread #1: tid = 0x23a0a2, 0x000000010000960c          crowbar`crb_create_identifier(str=0x0000000101002200) + 12 at string.c:58, queue = 'com.apple.main-thread', stop reason = breakpoint 4.1
   frame #0: 0x000000010000960c crowbar`crb_create_identifier(str=0x0000000101002200) + 12 at string.c:58
   55   {
   56       char *new_str;
   57
   -> 58       new_str = crb_malloc(strlen(str) + 1);
   59
   60       strcpy(new_str, str);
   61

2. the above code shows the str is print, why?

   (lldb) p str
   (char *) $1 = 0x0000000101002200 "print"

   see crowbar.l,

   <INITIAL>[A-Za-z_][A-Za-z_0-9]* {
   yylval.identifier = crb_create_identifier(yytext);
   return IDENTIFIER;
   }

3. lexer woudl ignore the LP and RP, just go ahead and see ", then decide to open_string_literal

   * thread #1: tid = 0x23a0a2, 0x00000001000094c4 crowbar`crb_open_string_literal + 4 at string.c:15, queue = 'com.apple.main-thread', stop reason = breakpoint 2.1
   frame #0: 0x00000001000094c4 crowbar`crb_open_string_literal + 4 at string.c:15
   12   void
   13   crb_open_string_literal(void)
   14   {
   -> 15       st_string_literal_buffer_size = 0;
   16   }
   17
   18   void

4. then lexer see another ", decide to close string

       * thread #1: tid = 0x23a0a2, 0x00000001000095ec crowbar`crb_close_string_literal + 76 at string.c:50, queue = 'com.apple.main-thread', stop reason = step over
   frame #0: 0x00000001000095ec crowbar`crb_close_string_literal + 76 at string.c:50
   47       memcpy(new_str, st_string_literal_buffer, st_string_literal_buffer_size);
   48       new_str[st_string_literal_buffer_size] = '\0';
   49
   -> 50       return new_str;
   51   }
   52
   53   char *
   (lldb) p new_str
   (char *) $4 = 0x0000000101000158 "3 + 5.."

compile process

the pattern is like this :

* thread #1: tid = 0x1e945a, 0x00000001000043b2 crowbar`yyparse + 2818 at crowbar.y:148, queue = 'com.apple.main-thread', stop reason = step over
    frame #0: 0x00000001000043b2 crowbar`yyparse + 2818 at crowbar.y:148
   145          : multiplicative_expression
   146          | additive_expression ADD multiplicative_expression
   147          {
-> 148              $$ = crb_create_binary_expression(ADD_EXPRESSION, $1, $3);
   149          }
   150          | additive_expression SUB multiplicative_expression
   151          {

then it would start create a binary expression

ESSION, left=0x0000000100803360, right=0x0000000100803378) + 22 at create.c:152, queue = 'com.apple.main-thread', stop reason = breakpoint 3.1
    frame #0: 0x0000000100005a66 crowbar`crb_create_binary_expression(operator=ADD_EXPRESSION, left=0x0000000100803360, right=0x0000000100803378) + 22 at create.c:152
   149  crb_create_binary_expression(ExpressionType operator,
   150                               Expression *left, Expression *right)
   151  {
-> 152      if ((left->type == INT_EXPRESSION
   153           || left->type == DOUBLE_EXPRESSION)
   154          && (right->type == INT_EXPRESSION
   155              || right->type == DOUBLE_EXPRESSION)) {
(lldb) bt
* thread #1: tid = 0x1e945a, 0x0000000100005a66 crowbar`crb_create_binary_expression(operator=ADD_EXPRESSION, left=0x0000000100803360, right=0x0000000100803378) + 22 at create.c:152, queue = 'com.apple.main-thread', stop reason = breakpoint 3.1
  * frame #0: 0x0000000100005a66 crowbar`crb_create_binary_expression(operator=ADD_EXPRESSION, left=0x0000000100803360, right=0x0000000100803378) + 22 at create.c:152
    frame #1: 0x00000001000043b2 crowbar`yyparse + 2818 at crowbar.y:148
    frame #2: 0x000000010000550c crowbar`CRB_compile(interpreter=0x0000000100803240, fp=0x00007fff7d8cf070) + 44 at interface.c:47
    frame #3: 0x0000000100005358 crowbar`main(argc=2, argv=0x00007fff5fbff798) + 184 at main.c:22
    frame #4: 0x00007fff9b5655c9 libdyld.dylib`start + 1
    frame #5: 0x00007fff9b5655c9 libdyld.dylib`start + 1

it would first evalue (3+5), the tree looks like this :

(lldb) p left->type
(ExpressionType) $1 = INT_EXPRESSION
(lldb) p right->type
(ExpressionType) $2 = INT_EXPRESSION

then it would

   frame #0: 0x0000000100005a66 crowbar`crb_create_binary_expression(operator=ADD_EXPRESSION, left=0x0000000101000140, right=0x0000000101000160) + 22 at create.c:152
   149  crb_create_binary_expression(ExpressionType operator,
   150                               Expression *left, Expression *right)
   151  {
-> 152      if ((left->type == INT_EXPRESSION
   153           || left->type == DOUBLE_EXPRESSION)
   154          && (right->type == INT_EXPRESSION
   155              || right->type == DOUBLE_EXPRESSION)) {
(lldb) p left->type
(ExpressionType) $9 = STRING_EXPRESSION
(lldb) p right->u.int_value
(int) $10 = 8
(lldb) p left->u.string_value
(char *) $11 = 0x0000000101000158 "3 + 5.."

test case 3

if (true) {
    print("true\n");
}

dynamic code analysis

1. crb_create_boolean_expression, firstly see 'true', then at crowbar.y it create boolean expression

   197             | TRUE_T
   198          {
   -> 199              $$ = crb_create_boolean_expression(CRB_TRUE);
   200          }
   201          | FALSE_T

2. crb_create_identifier, then see 'print', create identifier at crowbar.l

   55      <INITIAL>[A-Za-z_][A-Za-z_0-9]* {
   -> 56       yylval.identifier = crb_create_identifier(yytext);
   57       return IDENTIFIER;
   58   }

3. crb_open_string_literal, then see ", at crowbar.l

   <INITIAL>\" {
   72       crb_open_string_literal();
   -> 73       BEGIN STRING_LITERAL_STATE;
   74   }

4. crb_close_string_literal, same as above

       <STRING_LITERAL_STATE>\"        {
   98       Expression *expression = crb_alloc_expression(STRING_EXPRESSION);
   -> 99       expression->u.string_value = crb_close_string_literal();
   100      yylval.expression = expression;
   101      BEGIN INITIAL;
   102      return STRING_LITERAL;

5. crb_create_argument_list, then see "true\n" as argument, at crowbar.y

   argument_list
   74           : expression
   75           {
   -> 76               $$ = crb_create_argument_list($1);
   77           }
   78           | argument_list COMMA expression

6. crb_create_function_call_expression, after get argument_list, then see 'funciton call' at crowbar.y

   177     primary_expression
   178          : IDENTIFIER LP argument_list RP
   179          {
   -> 180              $$ = crb_create_function_call_expression($1, $3);
   181          }
   182          | IDENTIFIER LP RP

7. crb_create_statement_list, then print("true\n"); as a statement, because the statement pattern is expression SEMICOLON

   83   statement_list
   84           : statement
   85           {
   -> 86               $$ = crb_create_statement_list($1);
   87           }

8. crb_create_block

   308  block
   309          : LC statement_list RC
   310          {
   -> 311              $$ = crb_create_block($2);
   312          }
   313          | LC RC

9. crb_create_if_statement

   239     if_statement
   240          : IF LP expression RP block
   241          {
   -> 242              $$ = crb_create_if_statement($3, $5, NULL, NULL);
   243          }
   244          | IF LP expression RP block ELSE block

10. crb_chain_statement_list

      frame #0: 0x00000001000040f5 crowbar`yyparse + 2117 at crowbar.y:50
    47               CRB_Interpreter *inter = crb_get_current_interpreter();
    48
    49               inter->statement_list
    -> 50                   = crb_chain_statement_list(inter->statement_list, $1);

test case 4

dynamic code analysis ![call graph 2]

if (false) {
    print("bad\n");
} else {
    print("good\n");
}

1. crb_create_boolean_expression

    frame #0: 0x000000010000451b crowbar`yyparse + 3179 at crowbar.y:203
   200          }
   201          | FALSE_T
   202          {
   -> 203              $$ = crb_create_boolean_expression(CRB_FALSE);
   204          }
   205          | NULL_T
   206          {

2. crb_create_identifier, print

    frame #0: 0x00000001000019db crowbar`yylex + 1435 at crowbar.l:56
   53   <INITIAL>"/"            return DIV;
   54   <INITIAL>"%"            return MOD;
   55   <INITIAL>[A-Za-z_][A-Za-z_0-9]* {
   -> 56       yylval.identifier = crb_create_identifier(yytext);
   57       return IDENTIFIER;
   58   }
   59   <INITIAL>([1-9][0-9]*)|"0" {

3. crb_close_string_literal

   * thread #1: tid = 0x43fb0, 0x00000001000095ec crowbar`crb_close_string_literal + 76 at string.c:50, queue = 'com.apple.main-thread', stop reason = step over
   frame #0: 0x00000001000095ec crowbar`crb_close_string_literal + 76 at string.c:50
   47       memcpy(new_str, st_string_literal_buffer, st_string_literal_buffer_size);
   48       new_str[st_string_literal_buffer_size] = '\0';
   49
   -> 50       return new_str;
   51   }
   52
   53   char *
   (lldb) p new_str
   (char *) $5 = 0x0000000101000170 "bad\n"

    frame #0: 0x0000000100001bb1 crowbar`yylex + 1905 at crowbar.l:99
   96   <COMMENT>.      ;
   97   <STRING_LITERAL_STATE>\"        {
   98       Expression *expression = crb_alloc_expression(STRING_EXPRESSION);
   -> 99       expression->u.string_value = crb_close_string_literal();
   100      yylval.expression = expression;
   101      BEGIN INITIAL;
   102      return STRING_LITERAL;

4. crb_create_argument_list

    frame #0: 0x00000001000041a2 crowbar`yyparse + 2290 at crowbar.y:76
   73   argument_list
   74           : expression
   75           {
   -> 76               $$ = crb_create_argument_list($1);
   77           }
   78           | argument_list COMMA expression
   79           {

5. crb_create_function_call

   frame #0: 0x00000001000044a0 crowbar`yyparse + 3056 at crowbar.y:180
   177  primary_expression
   178          : IDENTIFIER LP argument_list RP
   179          {
   -> 180              $$ = crb_create_function_call_expression($1, $3);
   181          }
   182          | IDENTIFIER LP RP
   183          {

6. *crb_create_statement_list

7. crb_create_block

   frame #0: 0x0000000100004790 crowbar`yyparse + 3808 at crowbar.y:311
   308  block
   309          : LC statement_list RC
   310          {
   -> 311              $$ = crb_create_block($2);
   312          }
   313          | LC RC

8. crb_create_identifier, print again

9. crb_close_string_literal, "good\n"
10. crb_create_argument_list, ("good\n")
11. crb_create_funcion_call

12. crb_create_statement_list

    (lldb) p statement->u.expression_s->u.function_call_expression
    (FunctionCallExpression) $27 = {
    identifier = 0x00000001010001e0 "print"
    argument = 0x0000000101000208
    }

13. crb_create_block

    (lldb) p then_block->statement_list->statement->u.expression_s->type
    (ExpressionType) $35 = FUNCTION_CALL_EXPRESSION

14. crb_create_if_statement

    (lldb) p then_block->statement_list->statement->u.expression_s->u.function_call_expression.argument->expression->u.string_value
    (char *) $46 = 0x0000000101000170 "bad\n"

15. crb_chain_statement_list

    frame #0: 0x000000010000594e crowbar`crb_chain_statement_list(list=0x0000000000000000, statement=0x0000000101000270) + 30 at create.c:95
    92       StatementList *pos;
    93
    94       if (list == NULL)
    -> 95           return crb_create_statement_list(statement);
    96
    97       for (pos = list; pos->next; pos = pos->next)
    98           ;
    (lldb) p statement
    (Statement *) $47 = 0x0000000101000270
    (lldb) p statement->type
    (StatementType) $48 = IF_STATEMENT

test case 5

test code :

i = 0;
for (;;) {
    print(" i.." + i);
    if (i > 5) {
        break;
    }
    i = i + 1;
}
print("\n");

dynamic code analysis :

1. create identifier

   frame #0: 0x000000010000960c crowbar`crb_create_identifier(str=0x0000000101800000) + 12 at string.c:58
   55   {
   56       char *new_str;
   57
   -> 58       new_str = crb_malloc(strlen(str) + 1);
   59
   60       strcpy(new_str, str);
   61
   (lldb) p str
   (char *) $1 = 0x0000000101800000 "i"

2. create assign expression

   frame #0: 0x0000000100005a15 crowbar`crb_create_assign_expression(variable=0x0000000101000138, operand=0x0000000101000140) + 21 at create.c:121
   118  {
   119      Expression *exp;
   120
   -> 121      exp = crb_alloc_expression(ASSIGN_EXPRESSION);
   122      exp->u.assign_expression.variable = variable;
   123      exp->u.assign_expression.operand = operand;
   124
   (lldb) p operand
   (Expression *) $3 = 0x0000000101000140
   (lldb) p operand->type
   (ExpressionType) $4 = INT_EXPRESSION
   (lldb) p operand->u.int_value
   (int) $5 = 0

3. crb_chain_statement_list

   frame #0: 0x0000000100005940 crowbar`crb_chain_statement_list(list=0x0000000000000000, statement=0x0000000101000170) + 16 at create.c:94
   91   {
   92       StatementList *pos;
   93
   -> 94       if (list == NULL)
   95           return crb_create_statement_list(statement);
   96
   97       for (pos = list; pos->next; pos = pos->next)

   (lldb) p statement->u.expression_s->type
   (ExpressionType) $10 = ASSIGN_EXPRESSION

4. crb_create_identifier

   frame #0: 0x000000010000960c crowbar`crb_create_identifier(str=0x0000000101800016) + 12 at string.c:58
   55   {
   56       char *new_str;
   57
   -> 58       new_str = crb_malloc(strlen(str) + 1);
   59
   60       strcpy(new_str, str);
   61
   (lldb) p str
   (char *) $17 = 0x0000000101800016 "print"

5. crb_open_string_literal

6. crb_close_string_literal

7. crb_create_binary_expression, create binary expr for "i.." + i

   frame #0: 0x0000000100005a66 crowbar`crb_create_binary_expression(operator=ADD_EXPRESSION, left=0x00000001010001b0, right=0x00000001010001d8) + 22 at create.c:152
   149  crb_create_binary_expression(ExpressionType operator,
   150                               Expression *left, Expression *right)
   151  {
   -> 152      if ((left->type == INT_EXPRESSION
   153           || left->type == DOUBLE_EXPRESSION)
   154          && (right->type == INT_EXPRESSION
   155              || right->type == DOUBLE_EXPRESSION)) {
   (lldb) p left->type
   (ExpressionType) $19 = STRING_EXPRESSION
   (lldb) p left->u.string_value
   (char *) $20 = 0x00000001010001c8 " i.."
   (lldb) p right->u.string_value
   (char *) $21 = 0x00000001010001d0 "i"

8. crb_create_argument_list

   frame #0: 0x0000000100005863 crowbar`crb_create_argument_list(expression=0x00000001010001f0) + 19 at create.c:58
   55   {
   56       ArgumentList *al;
   57
   -> 58       al = crb_malloc(sizeof(ArgumentList));
   59       al->expression = expression;
   60       al->next = NULL;
   61
   (lldb) p expression->type
   (ExpressionType) $23 = ADD_EXPRESSION

9. crb_create_function_call_expression

10. crb_create_statement_list

     frame #0: 0x0000000100005903 crowbar`crb_create_statement_list(statement=0x0000000101000230) + 19 at create.c:82
    79   {
    80       StatementList *sl;
    81
    -> 82       sl = crb_malloc(sizeof(StatementList));
    83       sl->statement = statement;
    84       sl->next = NULL;
    85
    (lldb) p statement->type
    (StatementType) $26 = EXPRESSION_STATEMENT
    (lldb) p statement->u.expression_s->type
    (ExpressionType) $27 = FUNCTION_CALL_EXPRESSION
    (lldb) p statement->u.expression_s->u.string_value
    (char *) $28 = 0x00000001010001a8 "print"

11. crb_create_identifier, "i"

    frame #0: 0x000000010000960c crowbar`crb_create_identifier(str=0x0000000101800031) + 12 at string.c:58
    55   {
    56       char *new_str;
    57
    -> 58       new_str = crb_malloc(strlen(str) + 1);
    59
    60       strcpy(new_str, str);
    61
    (lldb) p str
    (char *) $30 = 0x0000000101800031 "i"

12. crb_create_binary_expression

     frame #0: 0x0000000100005a66 crowbar`crb_create_binary_expression(operator=GT_EXPRESSION, left=0x0000000101000270, right=0x0000000101000288) + 22 at create.c:152
    149  crb_create_binary_expression(ExpressionType operator,
    150                               Expression *left, Expression *right)
    151  {
    -> 152      if ((left->type == INT_EXPRESSION
    153           || left->type == DOUBLE_EXPRESSION)
    154          && (right->type == INT_EXPRESSION
    155              || right->type == DOUBLE_EXPRESSION)) {
    (lldb) p left->type
    (ExpressionType) $32 = IDENTIFIER_EXPRESSION
    (lldb) p right->type
    (ExpressionType) $33 = INT_EXPRESSION
    (lldb) p left->u.string_value
    (char *) $34 = 0x0000000101000268 "i"
    (lldb) p left->u.int_value
    (int) $35 = 16777832
    (lldb) p right->u.int_value
    (int) $36 = 5

13. crb_create_break_statement

     frame #0: 0x0000000100004763 crowbar`yyparse + 3763 at crowbar.y:299
    296  break_statement
    297          : BREAK SEMICOLON
    298          {
    -> 299              $$ = crb_create_break_statement();
    300          }
    301          ;
    302  continue_statement

14. crb_create_statement_list

    frame #0: 0x00000001000041e3 crowbar`yyparse + 2355 at crowbar.y:86
    83   statement_list
    84           : statement
    85           {
    -> 86               $$ = crb_create_statement_list($1);
    87           }
    88           | statement_list statement

15. crb_create_block

    frame #0: 0x0000000100006113 crowbar`crb_create_block(statement_list=0x00000001010002e0) + 19 at create.c:355
    352  {
    353      Block *block;
    354
    -> 355      block = crb_malloc(sizeof(Block));
    356      block->statement_list = statement_list;
    357
    358      return block;

16. crb_create_identifier

    frame #0: 0x000000010000962e crowbar`crb_create_identifier(str=0x000000010180004c) + 46 at string.c:60
    57
    58       new_str = crb_malloc(strlen(str) + 1);
    59
    -> 60       strcpy(new_str, str);
    61
    62       return new_str;
    63   }
    (lldb) p str
    (char *) $52 = 0x000000010180004c "i"

17. crb_create_if_statement

     frame #0: 0x0000000100005f4d crowbar`crb_create_if_statement(condition=0x00000001010002a0, then_block=0x00000001010002f0, elsif_list=0x0000000000000000, else_block=0x0000000000000000) + 29 at create.c:289
    286  {
    287      Statement *st;
    288
    -> 289      st = alloc_statement(IF_STATEMENT);
    290      st->u.if_s.condition = condition;
    291      st->u.if_s.then_block = then_block;
    292      st->u.if_s.elsif_list = elsif_list;

      frame #0: 0x00000001000045d2 crowbar`yyparse + 3362 at crowbar.y:242
    239  if_statement
    240          : IF LP expression RP block
    241          {
    -> 242              $$ = crb_create_if_statement($3, $5, NULL, NULL);
    243          }
    244          | IF LP expression RP block ELSE block

18. create_chain_statement_list,

    frame #0: 0x0000000100005940 crowbar`crb_chain_statement_list(list=0x0000000101000258, statement=0x0000000101000300) + 16 at create.c:94
    91   {
    92       StatementList *pos;
    93
    -> 94       if (list == NULL)
    95           return crb_create_statement_list(statement);
    96
    97       for (pos = list; pos->next; pos = pos->next)
    (lldb) p statement->type

    (lldb) p statement->u.expression_s->type
    (ExpressionType) $61 = GT_EXPRESSION

19. crb_chain_statement_list

    frame #0: 0x0000000100005940 crowbar`crb_chain_statement_list(list=0x0000000101000258, statement=0x00000001010003a0) + 16 at create.c:94
    91   {
    92       StatementList *pos;
    93
    -> 94       if (list == NULL)
    95           return crb_create_statement_list(statement);
    96
    97       for (pos = list; pos->next; pos = pos->next)
    (lldb) p statement->type
    (StatementType) $79 = EXPRESSION_STATEMENT
    (lldb) p statement->u.expression_s
    (Expression *) $80 = 0x0000000101000388
    (lldb) p statement->u.expression_s->type
    (ExpressionType) $81 = ASSIGN_EXPRESSION
    (lldb) p statement->u.expression_s->u.string_value
    (char *) $82 = 0x00000001010002f8 "i"

20. crb_create_block

    frame #0: 0x0000000100006113 crowbar`crb_create_block(statement_list=0x0000000101000258) + 19 at create.c:355
    352  {
    353      Block *block;
    354
    -> 355      block = crb_malloc(sizeof(Block));
    356      block->statement_list = statement_list;
    357
    358      return block;

21. crb_create_block

    frame #0: 0x000000010000612a crowbar`crb_create_block(statement_list=0x0000000101000258) + 42 at create.c:358
    355      block = crb_malloc(sizeof(Block));
    356      block->statement_list = statement_list;
    357
    -> 358      return block;
    359  }
    360
    361  Statement *
    (lldb) p statement_list->statement->u.expression_s->type
    (ExpressionType) $94 = FUNCTION_CALL_EXPRESSION
    (lldb) p statement_list->statement->u.expression_s->u.string_value
    (char *) $95 = 0x00000001010001a8 "print"

22. crb_create_for_statement

    frame #0: 0x00000001000060ad crowbar`crb_create_for_statement(init=0x0000000000000000, cond=0x0000000000000000, post=0x0000000000000000, block=0x00000001010003d8) + 29 at create.c:341
    338  {
    339      Statement *st;
    340
    -> 341      st = alloc_statement(FOR_STATEMENT);
    342      st->u.for_s.init = init;
    343      st->u.for_s.condition = cond;
    344      st->u.for_s.post = post;

23. crb_chain_statement_list

24. 
    ignore the later call....

test case 6