Parsing Programm with C

-

 Programming language class에서 제작한 문법에 따른 parser이다. Robert W. sebesta의 Concepts of Programming Languages 교재에 나온 코드를 참고하였다.

간단한 arithmetic 연산을 수행하고, IDENT와 CONST, OP를 구분하여 lexeme으로 받아들이고, 선언된 변수에 대해 symbol table을 만들어 값을 저장하는 코드이다.

연산의 경우, stmt를 IDENT = expr으로 나누고, expr-term-factor- lex 순으로 함수가 호출되며 연산을 진행한다. 연산자 우선순위가 높은 것이 나중에 파싱 되어야 하므로 expr가 Add/Sub, term이 Mult/Div를 연산하고, factor는 left parenthesis에 대해 expr을 다시 호출하거나 IDENT, CONST 값을 lex를 호출하여 얻는다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
#include <string.h>

int charClass;
char lexeme[100]; // token_string
char nextChar;
int lexLen;
int token;
int nextToken; //token_type
FILE* in_fp, * fopen(); //txt file input

/* Function declarations */
void addChar();
void getChar();
void getNonBlank();
int lookup(char ch);
int lex();

void stmt();
void expr();
void term();
void factor();
void error();

/* Character classes */
#define LETTER 0 // IDENT
#define DIGIT 1 // CONST
#define UNKNOWN 99

/* Token codes */
#define INT_LIT 10 // CONST
#define IDENT 11 // IDENT
#define ASSIGN_OP 20 // :=
#define ADD_OP 21 // +
#define SUB_OP 22 // -
#define MULT_OP 23 // *
#define DIV_OP 24 // /
#define LEFT_PAREN 25 // (
#define RIGHT_PAREN 26 // )
#define NEW_LINE 27 // ;

/****************************************************************/

int operatortop = 0; //top pointer for operator stack
int operandtop = 0; // top pointer for operand stack
int CONSTcount = 0; // number of CONST
int IDENTcount = 0; // number of IDENT
int OPcount = 0; // number of OP

char operatorStack[20]; // OP stack : + - * /
int constStack[20]; // CONST stack
char* operandStack[20]; // IDENT stack

typedef struct IDENTIFIER { // IDENT value and name store.
    int value; // IDENT value
    char* name; // IDENT name
}IDENTIFIER;

IDENTIFIER* IDstore[20]; // Symbol table for IDENT
int IDtop = 0; // top pointer for symbol table IDstore
int buff = 0; // buffer for operation values
int parseResult = 0; // switch index for result

/****************************************************************/
//main function

int main(int argc, char*argv[]) {
    /* Open the input data file and process its contents */
    FILE* fp = fopen(argv[1], "r"); // execute by command >>program.exe input.txt
    in_fp = fp;
    if (in_fp == NULL)
        printf("ERROR - cannot open file \n");
    else {
        getChar();
        do {
            stmt();
        } while (!feof(in_fp));
    }
    printf("Result ==> ");
    for(int i=0;i<IDtop;i++){
        printf("%s: %d; ",IDstore[i]->name, IDstore[i]->value);
    } //print out the result of parseing.
    printf("\n");
    for(int i=0;i<IDtop;i++){
        free(IDstore[i]); // Free each allocated struct
    }
    for (int i = 0; i < operandtop; i++) {
        free(operandStack[i]); // Free each allocated string
    }
    printf("Parsing complete. Press Enter to continue...\n");
    getchar();  // Wait for Enter key

    return 0;
}

/****************************************************************/
//stmt() function : parse the input program into <stmt> -> <ident><Assign_op><expr>

void stmt() {
    //printf("Enter <stmt>\n");
    parseResult = 0; // switch value for parse result

    IDENTcount = 0; CONSTcount = 0; OPcount = 0; buff = 0;operandtop = 0; operatortop = 0; // initialize the count & top values when new line started.
    do {
        lex();
    } while (nextToken!=ASSIGN_OP);

    IDENTIFIER* ID = (IDENTIFIER*)malloc(sizeof(IDENTIFIER)); // new IDENT
    ID->name = operandStack[operandtop-1];
    expr();
    ID->value = atoi(operandStack[--operandtop]);
    if (IDtop < 20) IDstore[IDtop++] = ID; // add it to symbol table
    printf("ID: %d; CONST: %d; OP: %d;\n", IDENTcount, CONSTcount, OPcount);

    switch (parseResult) {
    case 0:
        printf("OK\n");
        break;
    case 1:
        printf("WARNING\n");
        break;
    case 2:
        printf("ERROR\n");
        break;
    }
    //printf("Exit <stmt>\n\n");
}

/****************************************************************/
//expr() function : parses strings with add/sub operation : <expr> -> <term>{ (+| -) < term > }

void expr() {
    //printf("Enter <expr>\n");
    /* Parse the first term */
    term();
    /* As long as the next token is + or -, get
    the next token and parse the next term */
    while (nextToken == ADD_OP || nextToken == SUB_OP) {
        lex();
        term();
        if (operatortop > 0 && operatorStack[operatortop-1] == '+') {
            if (!((operandStack[operandtop - 2][0] >= 48 )&& (operandStack[operandtop - 2][0] <= 57))) { // check the operand is IDENT or CONST
                int i = 0;
                for (i = 0; i < IDtop; i++) { // if it's IDENT, find it's value in Symbol table
                    if (strcmp(IDstore[i]->name, operandStack[operandtop - 2]) == 0) {
                        sprintf(operandStack[operandtop - 2], "%d", IDstore[i]->value); // if the IDENT found in symbol table, get it's value as string.
                        break;
                    }
                }
            }
            if (!(operandStack[operandtop-1][0] >= 48 && operandStack[operandtop-1][0] <= 57)) {
                int i = 0;
                for (i = 0; i < IDtop; i++) {
                    if (strcmp(IDstore[i]->name, operandStack[operandtop - 1]) == 0) {
                        sprintf(operandStack[operandtop - 1], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            int midbuff = 0;
            midbuff = atoi(operandStack[operandtop - 2]) + atoi(operandStack[operandtop - 1]);
            operandtop -= 2;
            operatortop -= 1;
            sprintf(operandStack[operandtop++], "%d", midbuff);
        }
        if (operatortop > 0 && operatorStack[operatortop-1] == '-') {
            if (!(operandStack[operandtop - 2][0] >= 48 && operandStack[operandtop - 2][0] <= 57)) {
                int i = 0;
                for (i = 0; i < IDtop; i++) {
                    if (strcmp(IDstore[i]->name, operandStack[operandtop - 2]) == 0) {
                        sprintf(operandStack[operandtop - 2], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            if (!(operandStack[operandtop-1][0] >= 48 && operandStack[operandtop-1][0] <= 57)) {
                int i = 0;
                for (i = 0; i < IDtop; i++) {
                    if (strcmp(IDstore[i]->name, operandStack[operandtop-1]) == 0) {
                        sprintf(operandStack[operandtop-1], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            int midbuff = 0;
            midbuff = atoi(operandStack[operandtop - 2]) - atoi(operandStack[operandtop - 1]);
            operandtop -= 2;
            operatortop -= 1;
            sprintf(operandStack[operandtop++], "%d", midbuff);
        }
        //printf("%d\n", buff);
        //term();
    }
    //printf("Exit <expr>\n");
} /* End of function expr */

/****************************************************************/
//term() function : parse string with mult/div operation : <term> -> <factor> {(* | /) <factor>)

void term() {
    //printf("Enter <term>\n");
    /* Parse the first factor */
    factor();
    /* As long as the next token is * or /, get the
    next token and parse the next factor */
    while (nextToken == MULT_OP || nextToken == DIV_OP) {
        lex();
        //factor();
        if (operatortop > 0 && operatorStack[operatortop-1] == '*') {
            if (!(operandStack[operandtop - 2][0] >= 48 && operandStack[operandtop -2][0] <= 57)) { // check the operand is IDENT or CONST
                for (int i = 0; i < IDtop; i++) { // if it's IDENT, find it's value in Symbol table
                    if (strcmp(IDstore[i]->name, operandStack[operandtop - 2]) == 0) {
                        sprintf(operandStack[operandtop - 2], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            if (!(operandStack[operandtop-1][0] >= 48 && operandStack[operandtop-1][0] <= 57)) {
                for (int i = 0; i < IDtop; i++) {
                    if (strcmp(IDstore[i]->name, operandStack[operandtop-1]) == 0) {
                        sprintf(operandStack[operandtop-1], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            int midbuff = 0;
            midbuff = atoi(operandStack[operandtop - 2]) * atoi(operandStack[operandtop-1]);
            operandtop -= 2;
            operatortop -= 1;
            sprintf(operandStack[operandtop++], "%d", midbuff);
        }
        if (operatortop > 0 && operatorStack[operatortop-1] == '/') {
            if (!(operandStack[operandtop - 2][0] >= 48 && operandStack[operandtop - 2][0] <= 57)) {
                for (int i = 0; i < IDtop; i++) {
                    if (strcmp(IDstore[i]->name, operandStack[operandtop - 2]) == 0) {
                        sprintf(operandStack[operandtop - 2], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            if (!(operandStack[operandtop-1][0] >= 48 && operandStack[operandtop-1][0] <= 57)) {
                for (int i = 0; i < IDtop; i++) {
                    if (strcmp(IDstore[i]->name, operandStack[operandtop-1]) == 0) {
                        sprintf(operandStack[operandtop-1], "%d", IDstore[i]->value);
                        break;
                    }
                }
            }
            int midbuff = 0;
            midbuff = atoi(operandStack[operandtop - 2]) / atoi(operandStack[operandtop-1]);
            operandtop -= 2;
            operatortop -= 1;
            sprintf(operandStack[operandtop++], "%d", midbuff);
        }
        //printf("%d\n", buff);
        factor();
    }
    //printf("Exit <term>\n");
} /* End of function term */

/****************************************************************/
//factor() function : Parse string with parenthesis or IDENT or CONST : <factor> -> ID | CONST | ( <expr> )

void factor() {
    //printf("Enter <factor>\n");
    /* Determine which RHS */
    if (nextToken == LEFT_PAREN) { // if parenthesis comes after an operator, have to detect forward
        //printf("Enter <left parenthesis>\n");
        lex();
        expr();
        if (nextToken == RIGHT_PAREN) {
            //printf("Enter <right parenthesis>\n"); // lex() is done in outside of parenthesis
        }
        else
            error();
    }

    lex();
    if (nextToken == IDENT || nextToken == INT_LIT)
        /* Get the next token */
        lex();
    /* If the RHS is ( <expr>), call lex to pass over the left parenthesis, call expr, and check for the right parenthesis */

    else {
        if (nextToken == LEFT_PAREN) {
            //printf("Enter <left parenthesis>\n");
            lex();
            expr();
            if (nextToken == RIGHT_PAREN) {
                //printf("Enter <right parenthesis>\n");
                lex();
            }
            else
                error();
        }
        else if (nextToken == RIGHT_PAREN) {
            //printf("Exit <factor>\n");
            return;
        }
        else if (nextToken == NEW_LINE) {
            //printf("Exit <factor>\n");
            return;
        }
        else if (nextToken == MULT_OP || nextToken == DIV_OP) {
            //printf("Exit <factor>\n");
            return;
        }
        else if (nextToken == ADD_OP || nextToken == SUB_OP) {
            //printf("Exit <factor>\n");
            return;
        }
        else error();
    }
    //printf("Exit <factor>\n");
} /* End of function factor */

/*****************************************************/
//lex() function : Lexical analyzer, read the character from input file, and put it into lexeme array

int lex() {
    //printf("Enter <lex>\n");
    lexLen = 0;
    getNonBlank();
    switch (charClass) {
    case LETTER: // parse IDENT
        addChar();
        getChar();
        while (charClass == LETTER || charClass == DIGIT) {
            addChar();
            getChar();
        }
        nextToken = IDENT;
        operandStack[operandtop++] = _strdup(lexeme);
        IDENTcount++;
        break;

    case DIGIT: // parse CONST
        addChar();
        getChar();
        while (charClass == DIGIT) {
            addChar();
            getChar();
        }
        nextToken = INT_LIT;
        operandStack[operandtop++] = _strdup(lexeme);
        CONSTcount++;
        break;

    case UNKNOWN: // parse OP & parenthesis
        lookup(nextChar);
        getChar();
        break;

    case EOF: // if reached EOF. shouldn't be reached normally.
        nextToken = EOF;
        lexeme[0] = 'E';
        lexeme[1] = 'O';
        lexeme[2] = 'F';
        lexeme[3] = 0;
        error();
        break;
    }

    //prinf("Exit <lex>, next token is %s\n", lexeme);
    printf("%s ", lexeme);
    if (nextToken == NEW_LINE) printf("\n");
    return nextToken;
} /* End of function lex */

/*****************************************************/
//lookup() function : lookup operators and parentheses and return the token

int lookup(char ch) {
    switch (ch) {
    case '(':
        addChar();
        nextToken = LEFT_PAREN;
        break;
    case ')':
        addChar();
        nextToken = RIGHT_PAREN;
        break;
    case '+':
        addChar();
        nextToken = ADD_OP;
        operatorStack[operatortop++] = '+';
        OPcount++;
        break;
    case '-':
        addChar();
        nextToken = SUB_OP;
        operatorStack[operatortop++] = '-';
        OPcount++;
        break;
    case '*':
        addChar();
        nextToken = MULT_OP;
        operatorStack[operatortop++] = '*';
        OPcount++;
        break;
    case '/':
        addChar();
        nextToken = DIV_OP;
        operatorStack[operatortop++] = '/';
        OPcount++;
        break;
    case ':':
        addChar();
        nextChar = getc(in_fp); // Assign_Op -> :=
        addChar();
        nextToken = ASSIGN_OP;
        break;
    case ';':
        addChar();
        nextToken = NEW_LINE;
        break;
    default:
        addChar();
        nextToken = EOF;
        break;
    }
    return nextToken;
}

/*****************************************************/
/* addChar - a function to add nextChar to lexeme */

void addChar() {
    if (lexLen <= 98) {
        lexeme[lexLen++] = nextChar;
        lexeme[lexLen] = 0;
    }
    else
        printf("Error - lexeme is too long \n");
}

/*****************************************************/
/* getChar - a function to get the next character of
input and determine its character class */

void getChar() {
    if ((nextChar = getc(in_fp)) != EOF) {
        if (isalpha(nextChar))
            charClass = LETTER;
        else if (isdigit(nextChar))
            charClass = DIGIT;
        else charClass = UNKNOWN;
    }
    else
        charClass = EOF;
}

/*****************************************************/
/* getNonBlank - a function to call getChar until it returns a non-whitespace character */

void getNonBlank() {
    while (isspace(nextChar))
        getChar();
}

/*****************************************************/
// error() function : gives error message and pause the programm.

void error() {
    printf("Wrong input detected!\n");
    printf("Press Enter to continue...\n");
    getchar();  // Wait for Enter key
    return;
}

댓글

댓글 쓰기

이 블로그의 인기 게시물

IIKH Class from Timothy Budd's introduction to OOP

-
 Timothy Budd의 An Introduction to OOP 3ed. IIIKH(Intelligent Interactive Kitchen Helper) 앞서 객체 지향 프로그래밍의 가장 큰 특징은 Separation of implementation and interface라고 하였다. 즉, 사용자는 해당 오브젝트의 기능들이 어떻게 실현되었는지 알 필요 없이 해당 오브젝트가 제공하는 기능들 만 사용할 수 있는 것이다. 그래서 책의 예제에 제공되는 6개의 클래스가 어떤 기능을 가져야 하는지 public / private 에 대해서 attribute와 method를 생성하였다. #pragma once class Greeter { //greeter component that starts at the very beginning of IIKH. It provides several menu for user to choose. private:     void show_menu(); // main display window when IIKH is started and offer several choices. public:     void call_RecipeDatabase(); // if user selects browse, add, edit recipe.     void call_PlanManager(); // if user selects review or create meal plan. }; class RecipeDatabase { // RecipeDatabase component that store recipes and manage them. private:     Recipe recipeList[100]; //store list of recipe components(objects) and can return, edit, add whenever nee...
자세한 내용 보기

Compiler 9 - Efficient Code generation

-
 이전의 코드 생성은 모두 가정(무한한 레지스터 등)에 의해 리소스를 낭비하였다. 따라서 이를 개선하는 방법이 필요하다. 따라서 memory access의 횟수를 줄여 실행속도를 증가시키고, 쓸모 없는 register의 사용을 줄여 리소스의 낭비 또한 방지한다. 이는 각 레지스터에 가능한 많은 변수를 가지고 있게 하는 방식으로 구현할 수 있다. 이를 위해서 서로 겹치지 않는 live variable을 하나의 레지스터가 공유하여 저장하도록 하면 된다. (덮어씌워도 더이상 사용되지 않는 변수라면 필요 없으므로) 이를 위해서 앞서 진행했던 live variable analysis를 global scope에서 모두 실행한다. 그리고 각 variable을 노드로 가지고, 동시에 존재하는 live variable 사이에 edge가 존재하도록 graph를 그린다. (Register Interference Graph - edge가 존재하는 노드 끼리는 서로 같은 레지스터를 공유하면 안된다) 이 RIG를 통해 연결되지 않은 노드는 같은 레지스터에 할당되어도 문제가 없다는 것을 알 수 있다. 따라서 전체 노드 수보다 적은 레지스터에 모든 변수를 저장할 수 있다. 그리고 TAC로 표현된 각 노드 변수에 서로 연결되지 않았다면 같은 레지스터를 할당하여 어셈브릴 코드를 완성할 수 있다. - k colorable (transform into graph coloring problem) 서로 연결되지 않은 노드에 같은 색을 할당하여 색칠할 때 k개의 색이 필요하다면, k개의 레지스터에 모든 variable을 저장할 수 있다. 따라서 이를 그래프 색칠 문제로 확장하여 이해할 수 있다. 그러나 해당 문제는 NP-hard problem이므로 답은 존재하지만, 효율적으로 풀 수 있는 방법이 없다. (가장 간단한 것이 O(n*2^n)) 따라서 이를 직접적으로 해결하기보다는 heuristic을 사용해야 한다. - Heuristics for graph coloring (not optimal, ...
자세한 내용 보기

Software Engineering 10 - V&V, SOLID principle

-
 Verification & Validation(V&V) - Verification : inspection 과 review를 통해 우리가 올바르게 제품을 만들고 있는지 각 스텝을 검사하는 것 inspection(static) : system의 실행이 필요하지 않고 코드나 requirement, design 등등 representation에 대해서 검사 가능. 소프트웨어의 퀄리티를 올리기 위한 가장 좋은 방법(Best Known Method) -Validation : 만들어낸 artifact가 requirement를 만족하는가? 주로 testing을 통해서 올바른 제품을 만들고 있는지 확인하는 것. testing(dynamic) : 현재 존재하는 에러를 입증 (에러가 없다는 것을 보장해주지 않음) 가장 cost가 많이 필요한 단계. inspection과 testing은 서로 상호보완적인 관계. inspection은 고객의 requirement를 만족하는지 실제로 확인하기 어려움. development testing - release testing - user testing의 stage로 구성된다. - Development testing = unit testing + component testing + system testing 각 unit의 functionality를 먼저 테스트하고, 이들을 합친 component의 interface를 확인한 다음 전체를 합쳐 integration된 시스템이 잘 작동하는지 확인하게 된다. Black box & White Box 내부 작동원리를 모르고 주어진 시스템에 대한 input/output만 구현하는 것이 black box, 내부 작동 원리와 유닛들 사이 interaction, 코드 등을 알고 수행하는 테스트가 white box이다. 주로 development 과정에서 개발자들에 의해 시행되는 테스트는 white box test가 되고, 제 3자가 테스트하는 경우(user / release tes...
자세한 내용 보기