파싱/하향식

1. 개요

2. 고려 사항

2.1. Left recursion 문제

• parser가 non-terminal [math(\textbf{A})] 생성 규칙을 적용하려 한다.
• 규칙 [math(\textbf{A}::= \textbf{A} \text{b})]를 적용 후 다시 non-terminal [math(\textbf{A})]를 만난다. 이 non-terminal A를 파싱하기 위해, 규칙 [math(\textbf{A}::= \textbf{A} \text{b})]를 다시 적용하려할 것이다. 이러한 과정이 계속 반복된다.
• parser가 [math(\textbf{A})]를 다시 구문 분석하려고 할 때마다 호출 스택에 재귀 호출이 계속 추가되므로, 스택 오버플로 오류가 발생하게 된다.

2.2. Left factoring

3. 재귀 하강 파서(Recursive Descent Parser)

3.1. Pseudo code

3.2. Python 구현 예시

#!syntax python
class RecursiveDescentParser:
    def __init__(self, input_string):
        self.input = input_string.replace(" ", "")
        self.index = 0

    def parse(self):
        result = self.expr()
        if self.index < len(self.input):
            raise SyntaxError("Unexpected character at index {}".format(self.index))
        return result

    def expr(self):
        # expr ::= binary + binary | binary
        left = self.binary()
        if self.index < len(self.input) and self.input[self.index] == "+":
            self.index += 1  # skip '+'
            right = self.binary()
            return left and right  # 두 binary의 문법 일치 여부 출력
        else:
            return left # 단일 binary의 경우

    def binary(self):
        # binary ::= digit | digit binary
        if not self.digit():
            return False
        while self.index < len(self.input) and self.input[self.index] in "01":
            self.index += 1
        return True

    def digit(self):
        # digit ::= 0 | 1
        if self.index < len(self.input) and self.input[self.index] in "01":
            self.index += 1
            return True
        else:
            return False


# 예시: 101 + 010
code = "101 + 010"
parser = RecursiveDescentParser(code)
result = parser.parse()
print(result) # True

4. Predictive Parser(예측 파서)