python으로 recursive descent parser 구현

20200252_김주현.zip

0.86MB

Internal Document.docx

0.49MB

main.py

0.01MB

과제설명.pdf

0.98MB

External Document.docx

1.15MB

 

import sys
# 단순 산술식에 대한 어휘 분석기 시스템
# 어휘 분석기의 소스 코드는 정수 변수 next_token, 문자열 변수 token_string, 함수 lexical()을 포함해야 한다.

char_class = 0
lexeme = []
next_char = ''
lex_len = 0
next_token = 0
token_string = ''

ID_cnt = 0  # ID 개수
CONST_cnt = 0  # CONST 개수
OP_cnt = 0  # OP 개수

# 문자 유형들(charClass)
letter_type = {'LETTER': 0, 'DIGIT': 1, 'UNKNOWN': 99, 'EOF': -1}

# 토큰 코드들
token_code = {'CONST': 10,
              'IDENT': 11,
              'ASSIGNMENT_OP': 20,
              'ADD_OP': 21,
              'SUB_OP': 22,
              'MULT_OP': 23,
              'DIV_OP': 24,
              'LEFT_PAREN': 25,
              'RIGHT_PAREN': 26,
              'SEMI_COLON': 59}

#변수(IDENT) 값 저장을 위한 dictionary
ident_result = {}

#오류 복구된 결과 저장을 위한 list
read_line = []
is_ok = True    #오류가 있으면 False
error_string = []   #에러 문장들 저장 list


def lookup(ch):
    global next_token, OP_cnt, is_ok
    if ch == '(':
        addchar()  # nextChar을 lexeme에 추가
        next_token = token_code['LEFT_PAREN']

    elif ch == ')':
        addchar()  # nextChar을 lexeme에 추가
        next_token = token_code['RIGHT_PAREN']

    elif ch == '+':
        addchar()
        next_token = token_code['ADD_OP']
        OP_cnt += 1

    elif ch == '-':
        addchar()
        next_token = token_code['SUB_OP']
        OP_cnt += 1

    elif ch == '*':
        addchar()
        next_token = token_code['MULT_OP']
        OP_cnt += 1

    elif ch == '/':
        addchar()
        next_token = token_code['DIV_OP']
        OP_cnt += 1

    elif ch == ';':
        addchar()
        next_token = token_code['SEMI_COLON']
        read_line.append(';')

    elif next_char == ':':
        addchar()
        getchar()
        if next_char == '=':
            addchar()
            next_token = token_code['ASSIGNMENT_OP']
            read_line.append(':=')

    else:
        addchar()
        next_token = letter_type['EOF']

    return next_token


# nextChar을 lexeme에 추가


def addchar():
    global lex_len  # 전역번수 lex_len을 사용하겠다
    if lex_len <= 98:
        lexeme.append(next_char)
        lex_len += 1
    else:
        error_string.append('Error - lexeme is too long')
        is_ok = False


def getchar():
    global f
    global next_char, char_class
    next_char = f.read(1)

    if next_char != '':
        if next_char.isalpha():
            char_class = letter_type['LETTER']

        elif next_char.isdigit():
            char_class = letter_type['DIGIT']

        else:
            char_class = letter_type['UNKNOWN']
    else:
        char_class = letter_type['EOF']
    #print('charclass : ', char_class)


# 비 공백 문자를 반환할 때까지 getchar를 호출하는 함수
def get_non_blank():
    while next_char.isspace():
        getchar()


# lexical() : 산술식을 위한 단순 어휘 분석기
# 입력 스트림을 분석하여 하나의 lexeme을 찾아낸 뒤, 그것의 token type을 next_token에 저장하고,
# lexeme 문자열을 token_string에 저장하는 함수

def lexical():
    global next_token, lex_len, char_class, ID_cnt, CONST_cnt, OP_cnt, lexeme, token_string, is_ok
    lexeme.clear()
    lex_len = 0
    get_non_blank()

    # 식별자를 파싱한다.
    if char_class == letter_type['LETTER']:
        addchar()
        getchar()
        while char_class == letter_type['LETTER'] or char_class == letter_type['DIGIT']:
            addchar()
            getchar()
        next_token = token_code['IDENT']
        ID_cnt += 1  # ID 개수 1 증가
        token_string = ''.join(s for s in lexeme)
        read_line.append(token_string)

    # 정수 리터럴을 파싱한다.
    elif char_class == letter_type['DIGIT']:
        addchar()
        getchar()
        while char_class == letter_type['DIGIT']:
            addchar()
            getchar()
        next_token = token_code['CONST']
        CONST_cnt += 1
        token_string = ''.join(s for s in lexeme)
        read_line.append(token_string)

    elif char_class == letter_type['UNKNOWN']:
        lookup(next_char)
        getchar()

    elif char_class == letter_type['EOF']:
        next_token = letter_type['EOF']
        #lexeme.append('EOF')

    token_string = ''.join(s for s in lexeme)

    #print('Next token is ', next_token, ', Next lexeme is ', token_string)

    if next_char == '\n' or next_char == '':
        if read_line:
            read_line_string = ''.join(read_line)
            print(read_line_string)
            print('ID:', ID_cnt, '; CONST: ', CONST_cnt, '; OP: ', OP_cnt,';')
            if is_ok:
                print('(OK)')
            else:
                for error in error_string:
                    print(error)
                error_string.clear()
            print()
            ID_cnt = 0
            CONST_cnt = 0
            OP_cnt = 0
            is_ok = True
            read_line.clear()



#Recursive Descent Parsing
# <program> -> <statements>
def program():
    statements()

# <statements> -> <statement>|<statement><semi_colon><statements>


def statements():
    global is_ok
    statement()
    while next_token == token_code['SEMI_COLON']:
        lexical()
        statements()


# <statement> → <ident><assignment_op><expression>
def statement():
    global error_string
    if next_token == token_code['IDENT']:
        ident_result[token_string] = 'Unknown'  #<ident>를 dictionary의 key값으로 추가
        temp_ident_string = token_string    #<ident>에 <expression> 결과를 저장하기 위해 변수 이름을 임시 저장
        lexical()

        if next_token == token_code['ASSIGNMENT_OP']:
            lexical()
            e = expression()
            ident_result[temp_ident_string] = e   #expression에서 계산된 결과를 IDENT에 대입
        else:
            pass
    else:
        pass

#<expression> → <term><term_tail>


def expression():
    t = 0    # term()의 반환값을 받을 변수
    expr_result = 0

    t = term()
    if t != 'Unknown':
        # term_tail의 연산(+/-)을 수행한 결과
        expr_result = term_tail(t)
    else:   #정의되지 않은 변수에 대한 연산
        expr_result = 'Unknown'
        term_tail(t)

    return expr_result


#<term_tail> → <add_op><term><term_tail> | ε
# t: <expr> 내 <term>의 반환값을 전달받는다.


def term_tail(t):
    term_result = t
    global is_ok, error_string, OP_cnt
    t1 = 0  #term()의 반환값을 받을 변수

    if next_token == token_code['ADD_OP']:
        read_line.append(token_string)
        lexical()

        # 중복 연산자(*) 오류 검사
        if next_token == token_code['ADD_OP']:
            error_string.append('(Warning)\"중복 연산자(+) 제거\"')
            OP_cnt -= 1
            is_ok = False
            lexical()

        t1 = term()
        term_tail(t1)

        if t1 != 'Unknown' and t != 'Unknown':
            term_result = t + t1  # 더하기 연산 수행
        else:
            return 'Unknown'

    elif next_token == token_code['SUB_OP']:
        read_line.append(token_string)
        lexical()

        # 중복 연산자(-) 오류 검사
        if next_token == token_code['SUB_OP']:
            error_string.append('(Warning) 중복 연산자(-) 제거')
            OP_cnt -= 1  #중복 연산자는 개수 안셈
            is_ok = False
            lexical()

        t1 = term()
        term_tail(t1)
        if t1 != 'Unknown' or t != 'Unknown':
            term_result = t - t1  # 빼기 연산 수행

    return term_result

#<term> → <factor> <factor_tail>


def term():
    term_result = 0
    fa = 0  # factor()의 반환값을 받을 변수
    fa = factor()
    if fa != 'Unknown':
        term_result = factor_tail(fa)  # factor_tail()에서 factor의 반환값을 받아서 * 또는 / 연산 수행
    else:   # 정의되지 않은 변수
        term_result = 'Unknown'
        factor_tail(fa)

    return term_result

#<factor_tail> → <mult_op><factor><factor_tail> | ε
#fa : <term> 내부의 <factor>의 반환값


def factor_tail(fa):
    global is_ok, error_string, OP_cnt
    factor_tail_result = fa
    if next_token == token_code['MULT_OP']:
        read_line.append(token_string)
        lexical()

        #중복 연산자(*) 오류 검사
        if next_token == token_code['MULT_OP']:
            print('(Warning) 중복 연산자(*) 제거')
            OP_cnt -= 1
            is_ok = False
            lexical()

        fa1 = factor()  # fa1 : factor()의 리턴값
        factor_tail(fa1)

        if fa1 != 'Unknown' and fa != 'Unknown':
            factor_tail_result = fa * fa1  # 곱하기 연산

    elif next_token == token_code['DIV_OP']:
        read_line.append(token_string)
        lexical()

        # 중복 연산자(/) 오류 검사
        if next_token == token_code['DIV_OP']:
            print('(Warning) 중복 연산자(/) 제거')
            OP_cnt -= 1
            is_ok = False
            lexical()

        fa1 = factor()   #f1 : factor()의 리턴값
        factor_tail(fa1)
        if fa1 != 'Unknown' and fa != 'Unknown':
            factor_tail_result = fa / fa1  # 나누기 연산

    return factor_tail_result


#<factor> → <left_paren><expression><right_paren> | <ident> | <const>


def factor():
    global is_ok
    factor_result = 0

    # RHS가 (<expression>)이면, lexical을 호출하여 왼쪽 괄호를 전달하고, expression을 호출하고, 오른쪽 괄호를 검사한다.
    if next_token == token_code['LEFT_PAREN']:
        read_line.append(token_string)
        lexical()
        factor_result = expression()
        if next_token == token_code['RIGHT_PAREN']:
            read_line.append(token_string)
            lexical()
        else:
            error_string.append('(Warning): ) 누락')
            is_ok = False


    # 어느 RHS를 파싱할 것인지 결정한다.
    elif next_token == token_code['IDENT']:

        #Error : 선언된 적이 없는 식별자라면 오류메세지 출력
        if token_string not in ident_result:
            s = ('(Error)\"정의되지 않은 변수 (', token_string, ')가 참조됨\"')
            error_string.append(s)
            is_ok = False

            #dictionary에 key값으로 추가
            ident_result[token_string] = 'Unknown'
            factor_result = 'Unknown'

        else:
            #factor()의 반환값으로 변수의 값을 준다.
            factor_result = ident_result[token_string]
            # 다음 토큰을 가져온다

        lexical()

    elif next_token == token_code['CONST']:
        factor_result = int(token_string)
        lexical()

    #왼쪽 괄호, ident, 또는 상수가 아니다.
    else:
        error_string.append('(Error) 왼쪽괄호, ident, 또는 상수 필요')
        is_ok = False

    return factor_result



# 입력 데이터 파일을 열고 그 내용을 처리
#print('파일명을 입력하세요')
args = sys.argv[1:]
file_name = ""
for i in args:
    file_name += i
f = open(file_name, 'r')

getchar()
while next_token != letter_type['EOF']:
    lexical()
    program()

sorted_dict = sorted(ident_result.items())
print('Result ==> ', end='')
for i in range(len(sorted_dict)):
    print(sorted_dict[i][0], ':', sorted_dict[i][1], end='')
    if i != (len(sorted_dict)-1):
        print('; ', end='')
f.close()