Python 은 간단 한 재 귀 하강 분석 기 를 실현 합 니 다.

문제.
문법 규칙 에 따라 텍스트 를 해석 하고 명령 을 수행 하거나 입력 을 대표 하 는 추상 문법 트 리 를 만 들 고 싶 습 니 다.문법 이 매우 간단 하 다 면 프레임 워 크 를 사용 하지 않 고 스스로 이 해석 기 를 쓸 수 있다.
해결 방안
이 문제 에서 우 리 는 특수 문법 에 따라 텍스트 를 해석 하 는 문 제 를 집중 적 으로 토론 한다.이렇게 하기 위해 서 는 먼저 BNF 나 EBNF 형식 으로 표준 문법 을 지정 해 야 한다.예 를 들 어 간단 한 수학 표현 식 문법 은 다음 과 같 을 수 있 습 니 다.
expr ::= expr + term
    |   expr - term
    |   term
term ::= term * factor
    |   term / factor
    |   factor
factor ::= ( expr )
    |   NUM
또는 EBNF 형식 으로:
expr ::= term { (+|-) term }*
term ::= factor { (*|/) factor }*
factor ::= ( expr )
    |   NUM
EBNF 에서{...}* 에 포 함 된 규칙 은 선택 할 수 있 습 니 다.*0 회 또는 여러 번 반복 되 는 것 을 의미 합 니 다.
현재 BNF 의 작업 체제 에 대해 잘 모 르 면 좌우 기호 가 서로 바 꿀 수 있 는 규칙 으로 생각 하 세 요.일반적으로 해석 의 원 리 는 입력 텍스트 와 문법 규칙 에 맞 게 BNF 를 이용 하여 여러 개의 교체 와 확장 을 완성 하 는 것 이다.프레젠테이션 을 위해 서3 + 4 * 5와 같은 표현 식 을 해석 하고 있다 고 가정 하 십시오.이 표현 식 은 먼저 2.18 절 에서 소개 한 기술 을 사용 하여 토 큰 흐름 으로 분해 해 야 합 니 다.결 과 는 다음 과 같은 토 큰 시퀀스 일 수 있 습 니 다.
NUM + NUM * NUM
이 를 바탕 으로 해석 동작 은 문법 을 바 꾸 어 토 큰 을 입력 하려 고 합 니 다.
expr
expr ::= term { (+|-) term }*
expr ::= factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM { (*|/) factor }* { (+|-) term }*
expr ::= NUM { (+|-) term }*
expr ::= NUM + term { (+|-) term }*
expr ::= NUM + factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM { (*|/) factor}* { (+|-) term }*
expr ::= NUM + NUM * factor { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM * NUM { (*|/) factor }* { (+|-) term }*
expr ::= NUM + NUM * NUM { (+|-) term }*
expr ::= NUM + NUM * NUM
아래 의 모든 해석 절 차 는 시간 이 좀 걸 릴 수 있 지만,그 원 리 는 입력 을 찾 아 문법 규칙 에 맞 게 시도 하 는 것 이다.첫 번 째 입력 토 큰 은 NUM 이기 때문에 바 꾸 기 는 먼저 그 부분 과 일치 합 니 다.매 칭 에 성공 하면 다음 토 큰+에 들 어 갑 니 다.다음 영패 와 일치 하지 않 는 것 이 확인 되 었 을 때 오른쪽 부분(예 를 들 어{(*/)factor}*)이 삭 제 됩 니 다.성공 적 인 해석 에서 전체 오른쪽 부분 이 입력 토 큰 흐름 과 일치 하도록 완전히 펼 쳐 집 니 다.
앞의 지식 배경 이 있 습 니 다.다음 에 우 리 는 간단 한 예 를 들 어 재 귀적 하강 식 구 치 프로그램 을 어떻게 구축 하 는 지 보 여 드 리 겠 습 니 다.

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
Topic:      
Desc :
"""
import re
import collections

# Token specification
NUM = r'(?P<NUM>\d+)'
PLUS = r'(?P<PLUS>\+)'
MINUS = r'(?P<MINUS>-)'
TIMES = r'(?P<TIMES>\*)'
DIVIDE = r'(?P<DIVIDE>/)'
LPAREN = r'(?P<LPAREN>\()'
RPAREN = r'(?P<RPAREN>\))'
WS = r'(?P<WS>\s+)'

master_pat = re.compile('|'.join([NUM, PLUS, MINUS, TIMES,
                 DIVIDE, LPAREN, RPAREN, WS]))
# Tokenizer
Token = collections.namedtuple('Token', ['type', 'value'])


def generate_tokens(text):
  scanner = master_pat.scanner(text)
  for m in iter(scanner.match, None):
    tok = Token(m.lastgroup, m.group())
    if tok.type != 'WS':
      yield tok


# Parser
class ExpressionEvaluator:
  '''
  Implementation of a recursive descent parser. Each method
  implements a single grammar rule. Use the ._accept() method
  to test and accept the current lookahead token. Use the ._expect()
  method to exactly match and discard the next token on on the input
  (or raise a SyntaxError if it doesn't match).
  '''

  def parse(self, text):
    self.tokens = generate_tokens(text)
    self.tok = None # Last symbol consumed
    self.nexttok = None # Next symbol tokenized
    self._advance() # Load first lookahead token
    return self.expr()

  def _advance(self):
    'Advance one token ahead'
    self.tok, self.nexttok = self.nexttok, next(self.tokens, None)

  def _accept(self, toktype):
    'Test and consume the next token if it matches toktype'
    if self.nexttok and self.nexttok.type == toktype:
      self._advance()
      return True
    else:
      return False

  def _expect(self, toktype):
    'Consume next token if it matches toktype or raise SyntaxError'
    if not self._accept(toktype):
      raise SyntaxError('Expected ' + toktype)

  # Grammar rules follow
  def expr(self):
    "expression ::= term { ('+'|'-') term }*"
    exprval = self.term()
    while self._accept('PLUS') or self._accept('MINUS'):
      op = self.tok.type
      right = self.term()
      if op == 'PLUS':
        exprval += right
      elif op == 'MINUS':
        exprval -= right
    return exprval

  def term(self):
    "term ::= factor { ('*'|'/') factor }*"
    termval = self.factor()
    while self._accept('TIMES') or self._accept('DIVIDE'):
      op = self.tok.type
      right = self.factor()
      if op == 'TIMES':
        termval *= right
      elif op == 'DIVIDE':
        termval /= right
    return termval

  def factor(self):
    "factor ::= NUM | ( expr )"
    if self._accept('NUM'):
      return int(self.tok.value)
    elif self._accept('LPAREN'):
      exprval = self.expr()
      self._expect('RPAREN')
      return exprval
    else:
      raise SyntaxError('Expected NUMBER or LPAREN')


def descent_parser():
  e = ExpressionEvaluator()
  print(e.parse('2'))
  print(e.parse('2 + 3'))
  print(e.parse('2 + 3 * 4'))
  print(e.parse('2 + (3 + 4) * 5'))
  # print(e.parse('2 + (3 + * 4)'))
  # Traceback (most recent call last):
  #  File "<stdin>", line 1, in <module>
  #  File "exprparse.py", line 40, in parse
  #  return self.expr()
  #  File "exprparse.py", line 67, in expr
  #  right = self.term()
  #  File "exprparse.py", line 77, in term
  #  termval = self.factor()
  #  File "exprparse.py", line 93, in factor
  #  exprval = self.expr()
  #  File "exprparse.py", line 67, in expr
  #  right = self.term()
  #  File "exprparse.py", line 77, in term
  #  termval = self.factor()
  #  File "exprparse.py", line 97, in factor
  #  raise SyntaxError("Expected NUMBER or LPAREN")
  #  SyntaxError: Expected NUMBER or LPAREN


if __name__ == '__main__':
  descent_parser()

토론 하 다.
텍스트 해석 은 매우 큰 주제 로 학생 들 이 컴 파일 과정 을 공부 할 때 처음 시작 하 는 3 주 를 차지한다.문법,해석 알고리즘 등 배경 지식 을 찾 고 있다 면 컴 파일 러 책 을 읽 어 봐 야 한다.이 방면 에 관 한 내용 이 너무 많아 서 여기 서 다 펼 칠 수 없 음 이 분명 하 다.
그럼 에 도 불구 하고 재 귀 하강 해석 기 를 만 드 는 전체적인 사 고 는 간단 하 다.시작 할 때,당신 은 먼저 모든 문법 규칙 을 얻 은 후에 그것 을 함수 나 방법 으로 바 꿉 니 다.그래서 만약 당신 의 문법 이 이와 비슷 하 다 면:

expr ::= term { ('+'|'-') term }*

term ::= factor { ('*'|'/') factor }*

factor ::= '(' expr ')'
  | NUM

너 는 먼저 그것들 을 아래 와 같은 방법 으로 바 꿔 야 한다.

class ExpressionEvaluator:
  ...
  def expr(self):
  ...
  def term(self):
  ...
  def factor(self):
  ...

모든 방법 이 완성 해 야 할 임 무 는 간단 합 니 다.-문법 규칙 의 모든 부분 을 왼쪽 에서 오른쪽으로 옮 겨 다 니 며 모든 토 큰 을 처리 해 야 합 니 다.어떤 의미 에서 볼 때 방법의 목적 은 문법 규칙 을 다 처리 하거나 문법 오류 가 발생 하 는 것 이다.이렇게 하기 위해 서 는 아래 의 이러한 실현 방법 을 채택 해 야 한다.

만약 에 규칙 중의 다음 기호 가 다른 문법 규칙 의 이름(예 를 들 어 term 또는 factor)이 라면 같은 이름 의 방법 을 간단하게 호출 하면 된다.이것 이 바로 이 알고리즘 에서'하강'의 유래 이다.-제어 가 다른 문법 규칙 으로 떨 어 졌 다.때때로 규칙 은 이미 실 행 된 방법(예 를 들 어factor ::= '('expr ')'에서 expr 에 대한 호출)을 호출 할 수 있다.이것 이 바로 알고리즘 중의'재 귀'의 유래 이다.4567918)

만약 에 규칙 중의 다음 기호 가 특수 기호(예 를 들 어()라면 다음 토 큰 을 찾 아서 정확 한 일치 임 을 확인 해 야 한다).일치 하지 않 으 면 문법 오류 가 발생 합 니 다.이 절의 _expect() 방법 은 바로 이 단 계 를 하 는 데 쓰 인 다.4567918)

만약 에 규칙 중의 다음 기호 가 가능 한 선택 항목(예 를 들 어+또는-)이 라면 모든 가능 한 상황 에 대해 다음 토 큰 을 검사 해 야 합 니 다.하나 가 일치 할 때 만 계속 할 수 있 습 니 다.이것 도 이 절의 예시_accept() 방법의 목적 이다.그것 은 에 해당 한다expect()방법의 약화 버 전 입 니 다.일치 하 는 버 전 을 찾 으 면 계속 되 지만 찾 지 못 하면 오류 가 발생 하지 않 고 스크롤 백(후속 검 사 를 계속 할 수 있 도록 합 니 다).

중복 부분 이 있 는 규칙(예 를 들 어 규칙 표현 식::= term { ('+'|'-') term }* 에서 반복 동작 은 while 순환 을 통 해 이 루어 집 니 다.순환 주 체 는 다른 요소 가 없 을 때 까지 모든 중복 요 소 를 수집 하거나 처리 합 니 다.

전체 문법 규칙 처리 가 완료 되면 모든 방법 은 특정한 결 과 를 호출 자 에 게 되 돌려 준다.이것 이 바로 해석 과정 에서 값 이 어떻게 누적 되 는 원리 이다.예 를 들 어 표현 식 값 구하 기 프로그램 에서 표현 식 해석 후의 일부 결 과 를 되 돌려 줍 니 다.마지막 으로 모든 값 은 최상 위 문법 규칙 방법 에서 합 쳐 집 니 다.

간단 한 예 임 에 도 불구 하고 재 귀 하강 해석 기 는 매우 복잡 한 해석 을 실현 할 수 있 습 니 다.예 를 들 어 Python 언어 자체 가 재 귀 하강 해석 기 를 통 해 설명 한 것 이다.관심 이 있다 면 Python 소스 파일 Grammar/Grammar 를 살 펴 보고 바 텀 문법 체 제 를 연구 할 수 있 습 니 다.보고 나 면 수 동 으로 해석 기 를 실현 하 는 데 한계 와 부족 한 점 이 많다 는 것 을 알 게 될 것 이다.
그 중의 한 계 는 왼쪽 재 귀 를 포함 하 는 문법 규칙 에 사용 되 지 못 한 다 는 것 이다.예 를 들 어 다음 규칙 을 번역 해 야 한다 면:

items ::= items ',' item
  | item

이렇게 하기 위해 서 는 아래 와 같이items() 방법 을 사용 할 수 있 습 니 다.

def items(self):
  itemsval = self.items()
  if itemsval and self._accept(','):
    itemsval.append(self.item())
  else:
    itemsval = [ self.item() ]

유일한 문 제 는 이 방법 이 근본적으로 일 을 할 수 없다 는 것 이다.사실상 그것 은 무한 한 귀속 오류 가 발생 할 수 있다.
문법 규칙 자체 에 대해 서도 까다 로 운 문제 에 부 딪 힐 수 있다.예 를 들 어 다음 과 같은 간단 한 문법 표현 이 적절 한 지 알 고 싶 을 수도 있 습 니 다.

expr ::= factor { ('+'|'-'|'*'|'/') factor }*

factor ::= '(' expression ')'
  | NUM

이 문법 은 보기 에는 아무런 문제 가 없 는 것 같 지만,표준 사 칙 연산 중의 연산 자 우선 순 위 를 알 아차 리 지 못 한다.예 를 들 어 표현 식'3 + 4 * 5"은 기대 하 는 23 이 아 닌 35 를 얻 을 수 있 습 니 다.'expr'와'term'규칙 을 분리 해서 사용 하면 올 바른 작업 을 할 수 있 습 니 다.
복잡 한 문법 에 대해 서 는 PyParsing 이나 PLY 같은 해석 도 구 를 선택 하 는 것 이 좋 습 니 다.다음은 PLY 를 사용 하여 표현 식 값 을 구 하 는 프로그램의 코드 를 다시 쓰 는 것 입 니 다.

from ply.lex import lex
from ply.yacc import yacc

# Token list
tokens = [ 'NUM', 'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'LPAREN', 'RPAREN' ]
# Ignored characters
t_ignore = ' \t
'
# Token specifications (as regexs)
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

# Token processing functions
def t_NUM(t):
  r'\d+'
  t.value = int(t.value)
  return t

# Error handler
def t_error(t):
  print('Bad character: {!r}'.format(t.value[0]))
  t.skip(1)

# Build the lexer
lexer = lex()

# Grammar rules and handler functions
def p_expr(p):
  '''
  expr : expr PLUS term
    | expr MINUS term
  '''
  if p[2] == '+':
    p[0] = p[1] + p[3]
  elif p[2] == '-':
    p[0] = p[1] - p[3]


def p_expr_term(p):
  '''
  expr : term
  '''
  p[0] = p[1]


def p_term(p):
  '''
  term : term TIMES factor
  | term DIVIDE factor
  '''
  if p[2] == '*':
    p[0] = p[1] * p[3]
  elif p[2] == '/':
    p[0] = p[1] / p[3]

def p_term_factor(p):
  '''
  term : factor
  '''
  p[0] = p[1]

def p_factor(p):
  '''
  factor : NUM
  '''
  p[0] = p[1]

def p_factor_group(p):
  '''
  factor : LPAREN expr RPAREN
  '''
  p[0] = p[2]

def p_error(p):
  print('Syntax error')

parser = yacc()

이 프로그램 에서 모든 코드 는 비교적 높 은 단계 에 있다.영패 에 정규 표현 식 과 규칙 이 일치 할 때의 고급 처리 함수 만 쓰 면 됩 니 다.실제 실행 해상도 기,영 패 를 받 아들 이 는 등 바 텀 동작 은 라 이브 러 리 함수 에 의 해 이 루어 졌 다.
다음은 분석 대상 을 어떻게 사용 하 는 지 예 입 니 다.

>>> parser.parse('2')
2
>>> parser.parse('2+3')
5
>>> parser.parse('2+(3+4)*5')
37
>>>

프로 그래 밍 과정 에서 도전 과 자극 을 주 고 싶다 면 해상도 와 컴 파일 러 를 만 드 는 것 이 좋 습 니 다.또한 컴 파일 러 의 책 에는 밑바닥 의 이론 지식 이 많이 담 겨 있다.하지만 좋 은 자원 도 인터넷 에서 찾 을 수 있다.Python 자체 ast 모듈 도 가 볼 만하 다.
이상 은 Python 이 간단 한 재 귀 하강 분석 기 를 실현 하 는 상세 한 내용 입 니 다.Python 이 재 귀 하강 분석 기 를 실현 하 는 데 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 세 요!