Python如何實現(xiàn)一個簡單的遞歸下降分析器

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
Topic: 下降解析器
Desc :
"""
import re
import collections

# Token specification
NUM = r'(&#63;P<NUM>\d+)'
PLUS = r'(&#63;P<PLUS>\+)'
MINUS = r'(&#63;P<MINUS>-)'
TIMES = r'(&#63;P<TIMES>\*)'
DIVIDE = r'(&#63;P<DIVIDE>/)'
LPAREN = r'(&#63;P<LPAREN>\()'
RPAREN = r'(&#63;P<RPAREN>\))'
WS = r'(&#63;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()

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

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

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

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

items ::= items ',' item
  | item

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

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\n'
# 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
>>>