인터프리터 만들기 : AST 디자인하기

Question

그래서 저는 파이썬과 비슷한 언어를 만들기 위해 통역을하고 있습니다. 지금 나는 이것이 작은 일이 아니라는 것을 잘 알고 있으며, 그것이 잘 작동하거나 많이 할 것을 기대하지는 않는다.하지만 몇 가지 기본적인 기능 (변수, 함수, 루프, if 문 등)을 갖고 싶다.

그래서 현재 나는 통역사가 파일을 받아서 토큰 목록으로 나눠서이 토큰을 AST로 변환 할 준비가되었습니다. 필자는 이해할 수 있다고 생각하는 재귀 파생 파서를 사용하여이 작업을 수행하려고하지만 여기에는 문제가 있습니다. 의 너무

2 * 3 = 6 

은 다음 또한 내가 아는

1 + 6 = 7 

후에 완료됩니다 첫번째 수행 BIDMAS에게 곱셈을 사용하기 때문에 나는 다음과 같은 입력이 것

1 + 2 * 3 

출력 7 있다고 가정 해 봅시다 간단한 문법으로이 순서를 얻는 방법은 없지만 이것을 AST로 저장하는 방법을 모르겠습니다. 답변에 대한 일을 단순화하기 위해, 이것은 당신이받을 것이며, 문법 그래서 기본적으로

program = add 
add = mul {"+" mul} 
mul = NUM {"*" NUM} 

할 수있는 유일한 입력 가정 할 수 있습니다, 당신은 어떻게 데이터 구조 (들)은 AST를 저장해야합니까?

P. 나는 C.

Answer 1

면책 조항 :이 표현은 주관적이다 그리고 조명하기위한 것입니다.

기본적으로 AST는 각 AST 노드가 "왼쪽"및 "오른쪽"포인터를 모두 보유하는 "C"구조 인 이진 트리처럼 구성됩니다. AST의 다른 요소는 일반적으로 상황에 따라 다릅니다. 예를 들어 변수 정의와 함수 정의 또는 함수의 표현식. 당신이 인용 예를 들어, 거친 나무는이 거울 것 : 그래서

+ 
/ \ 
1  * 
     /\ 
    2 3 

1 + (2 * 3) AST 구조가 유사하다와 위의 노드를 대체하여 :

    ----------------- 
       | type: ADDOP | 
       | left: struct* | 
       | right: struct*| 
       ----------------- 
      /     \ 
      /     \ 
(ADDOP left points to)   (ADDOP right points to) 
------------------------  -------------------------- 
| type: NUMLITERAL  |  | type: MULTOP   | 
| value: 1    |  | left: struct*   | 
| left: struct* (null) |  | right: struct*   | 
| right: struct*(null) |  -------------------------- 
------------------------   /    \ 
            /    \ 

        (MULTOP left points to)   (MULTOP right points to) 
        ------------------------  -------------------------- 
        | type: NUMLITERAL  |  | type: NUMLITERAL  | 
        | value: 2    |  | value: 3    | 
        | left: struct* (null) |  | left: struct* (null) | 
        | right: struct*(null) |  | right: struct* (null) | 
        ------------------------  -------------------------- 

I "C"에 대해 충분히 알고 있고 malloc 노드를 사용하고 왼쪽/오른쪽 포인터를 할당한다고 가정합니다.

나머지 활동은 표현식을 평가하고 결과를 생성하거나 컴파일 된 결과에 정렬되는 적절한 중간 코드/기계어 코드를 방출하기 위해 트리 순회를 수행하는 것입니다. 어느 쪽이든 엄청난 양의 사고와 계획을 당신에게 가져다줍니다.

BTW : AST 노드는 일반적으로 표현하고자하는 추상화 수준에 따라 특성을 갖게됩니다. 또한 일반적인 컴파일러는 다른 이유 때문에 여러 AST를 활용할 수 있습니다. 그래, 더 읽기/공부하기.

참고 : 참고 :이 코드는 AST의 데이터 구조를 보여 주지만 @mikeb 응답은 "1 + 2 * 3"문자열을 이러한 구조의 노드로 가져 오는 방법에 견고합니다.

Answer 2

나는 "입환 마당"알고리즘을 사용하는 것이를하고있는 중이 야 - 너무 거기에 psudocode 있습니다>https://en.wikipedia.org/wiki/Shunting-yard_algorithm

.

FTA : 컴퓨터 과학에서

는 차량 기지 알고리즘은 중위 표기법으로 지정 수학적 표현을 구문 분석하는 방법이다. RPN (Reverse Polish Notation) 또는 AST (Abstract Syntax Tree)라고도하는 접미사 표기법 문자열을 생성하는 데 사용할 수 있습니다. 이 알고리즘은 Edsger Dijkstra에 의해 발명되었으며 "shunting yard"알고리즘으로 명명되었습니다. 그 작업은 철도 셔틀 마당과 비슷하기 때문입니다. Dijkstra는 처음으로 Mathematisch Centrum 보고서 MR 34/61에서 Shunting Yard Algorithm에 대해 설명했습니다.

RPN의 평가와 마찬가지로, shunting yard 알고리즘은 스택 기반입니다. 중위어 표현은 대부분의 사람들이 익숙했던 수학 표기법의 형식입니다 (예 : "3 + 4"또는 "3 + 4 * (2-1)"). 변환에는 두 개의 텍스트 변수 (문자열), 입력 및 출력이 있습니다. 출력 대기열에 아직 추가되지 않은 연산자를 보유하는 스택도 있습니다. 변환을 위해 프로그램은 각 기호를 순서대로 읽고 해당 기호를 기반으로 작업을 수행합니다. 위 예제의 결과는 "3 4 +"또는 "3 4 2 1 - * +"입니다.

shunting-yard 알고리즘은 나중에 운영자 우선 구문 분석으로 일반화되었습니다.

코드, 그것은이 그것을 저장하는 방법 (그리고 C를 좋아하지 않는 경우 - http://rosettacode.org/wiki/Parsing/Shunting-yard_algorithm을 선택할 수) 아니라고 지적 이후 :

#include <sys/types.h> 
#include <regex.h> 
#include <stdio.h> 

typedef struct { 
    const char *s; 
    int len, prec, assoc; 
} str_tok_t; 

typedef struct { 
    const char * str; 
    int assoc, prec; 
    regex_t re; 
} pat_t; 

enum assoc { A_NONE, A_L, A_R }; 
pat_t pat_eos = {"", A_NONE, 0}; 

pat_t pat_ops[] = { 
    {"^\\)", A_NONE, -1}, 
    {"^\\*\\*", A_R, 3}, 
    {"^\\^", A_R, 3}, 
    {"^\\*", A_L, 2}, 
    {"^/",  A_L, 2}, 
    {"^\\+", A_L, 1}, 
    {"^-",  A_L, 1}, 
    {0} 
}; 

pat_t pat_arg[] = { 
    {"^[-+]?[0-9]*\\.?[0-9]+([eE][-+]?[0-9]+)?"}, 
    {"^[a-zA-Z_][a-zA-Z_0-9]*"}, 
    {"^\\(", A_L, -1}, 
    {0} 
}; 

str_tok_t stack[256]; /* assume these are big enough */ 
str_tok_t queue[256]; 
int l_queue, l_stack; 
#define qpush(x) queue[l_queue++] = x 
#define spush(x) stack[l_stack++] = x 
#define spop() stack[--l_stack] 

void display(const char *s) 
{ 
    int i; 
    printf("\033[1;1H\033[JText | %s", s); 
    printf("\nStack| "); 
    for (i = 0; i < l_stack; i++) 
     printf("%.*s ", stack[i].len, stack[i].s); // uses C99 format strings 
    printf("\nQueue| "); 
    for (i = 0; i < l_queue; i++) 
     printf("%.*s ", queue[i].len, queue[i].s); 
    puts("\n\n<press enter>"); 
    getchar(); 
} 

int prec_booster; 

#define fail(s1, s2) {fprintf(stderr, "[Error %s] %s\n", s1, s2); return 0;} 

int init(void) 
{ 
    int i; 
    pat_t *p; 

    for (i = 0, p = pat_ops; p[i].str; i++) 
     if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED)) 
      fail("comp", p[i].str); 

    for (i = 0, p = pat_arg; p[i].str; i++) 
     if (regcomp(&(p[i].re), p[i].str, REG_NEWLINE|REG_EXTENDED)) 
      fail("comp", p[i].str); 

    return 1; 
} 

pat_t* match(const char *s, pat_t *p, str_tok_t * t, const char **e) 
{ 
    int i; 
    regmatch_t m; 

    while (*s == ' ') s++; 
    *e = s; 

    if (!*s) return &pat_eos; 

    for (i = 0; p[i].str; i++) { 
     if (regexec(&(p[i].re), s, 1, &m, REG_NOTEOL)) 
      continue; 
     t->s = s; 
     *e = s + (t->len = m.rm_eo - m.rm_so); 
     return p + i; 
    } 
    return 0; 
} 

int parse(const char *s) { 
    pat_t *p; 
    str_tok_t *t, tok; 

    prec_booster = l_queue = 0; 
    display(s); 
    while (*s) { 
     p = match(s, pat_arg, &tok, &s); 
     if (!p || p == &pat_eos) fail("parse arg", s); 

     /* Odd logic here. Don't actually stack the parens: don't need to. */ 
     if (p->prec == -1) { 
      prec_booster += 100; 
      continue; 
     } 
     qpush(tok); 
     display(s); 

re_op:  p = match(s, pat_ops, &tok, &s); 
     if (!p) fail("parse op", s); 

     tok.assoc = p->assoc; 
     tok.prec = p->prec; 

     if (p->prec > 0) 
      tok.prec = p->prec + prec_booster; 
     else if (p->prec == -1) { 
      if (prec_booster < 100) 
       fail("unmatched)", s); 
      tok.prec = prec_booster; 
     } 

     while (l_stack) { 
      t = stack + l_stack - 1; 
      if (!(t->prec == tok.prec && t->assoc == A_L) 
        && t->prec <= tok.prec) 
       break; 
      qpush(spop()); 
      display(s); 
     } 

     if (p->prec == -1) { 
      prec_booster -= 100; 
      goto re_op; 
     } 

     if (!p->prec) { 
      display(s); 
      if (prec_booster) 
       fail("unmatched (", s); 
      return 1; 
     } 

     spush(tok); 
     display(s); 
    } 

    return 1; 
} 

int main() 
{ 
    int i; 
    const char *tests[] = { 
     "3 + 4 * 2/(1 - 5)^2^3", /* RC mandated: OK */ 
     "123",     /* OK */ 
     "3+4 * 2/(1 - 5)^2^3.14", /* OK */ 
     "(((((((1+2+3**(4 + 5))))))",  /* bad parens */ 
     "a^(b + c/d * .1e5)!",   /* unknown op */ 
     "(1**2)**3",    /* OK */ 
     0 
    }; 

    if (!init()) return 1; 
    for (i = 0; tests[i]; i++) { 
     printf("Testing string `%s' <enter>\n", tests[i]); 
     getchar(); 

     printf("string `%s': %s\n\n", tests[i], 
      parse(tests[i]) ? "Ok" : "Error"); 
    } 

    return 0; 
}