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()

讨论

文本解析是一个很大的主题, 一般会占用学生学习编译课程时刚开始的三周时间。 如果你在找寻关于语法,解析算法等相关的背景知识的话,你应该去看一下编译器书籍。 很显然,关于这方面的内容太多,不可能在这里全部展开。

尽管如此,编写一个递归下降解析器的整体思路是比较简单的。 开始的时候,你先获得所有的语法规则,然后将其转换为一个函数或者方法。 因此如果你的语法类似这样:

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的调用)。 这就是算法中”递归”的由来。
  • 如果规则中下一个符号是个特殊符号(比如(),你得查找下一个令牌并确认是一个精确匹配)。 如果不匹配,就产生一个语法错误。这一节中的 _expect() 方法就是用来做这一步的。
  • 如果规则中下一个符号为一些可能的选择项(比如 + 或 -), 你必须对每一种可能情况检查下一个令牌,只有当它匹配一个的时候才能继续。 这也是本节示例中 _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" 会得到35而不是期望的23. 分开使用”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\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
>>>

如果你想在你的编程过程中来点挑战和刺激,编写解析器和编译器是个不错的选择。 再次,一本编译器的书籍会包含很多底层的理论知识。不过很多好的资源也可以在网上找到。 Python自己的ast模块也值得去看一下。

以上就是Python实现一个简单的递归下降分析器的详细内容,更多关于Python实现递归下降分析器的资料请关注我们其它相关文章!

时间: 2020-08-01

Python递归函数特点及原理解析

1 递归函数的特点 特点 一个函数 内部 调用自己 函数内部可以调用其他函数,当然在函数内部也可以调用自己 代码特点 函数内部的 代码 是相同的,只是针对 参数 不同,处理的结果不同 当 参数满足一个条件 时,函数不再执行 这个非常重要,通常被称为递归的出口,否则 会出现死循环! 示例代码 def sum_numbers(num): print(num) # 递归的出口很重要,否则会出现死循环 if num == 1: return sum_numbers(num - 1) sum_number

Python装饰器结合递归原理解析

代码如下: import functools def memoize(fn): print('start memoize') known = dict() @functools.wraps(fn) def memoizer(*args): if args not in known: print('memorize %s'%args) # known[args] = fn(*args) for k in known.keys(): print('%s : %s'%(k, known[k]), en

python 使用递归实现打印一个数字的每一位示例

我就废话不多说了,直接上代码吧! def func(n): # 从高分为开始打印 lengh = len(str(n)) # 确定数字的长度 x = 10**(lengh-1) # 确定数字的分位 if n < 10: print(n) else: print(int(n/x)) func(n % x) # 对n的x分位取余得到 def func1(n): # 从低分位开始打印 if n < 10: print(n) else: print(n % 10) func(int(n / 10))

Python递归调用实现数字累加的代码

我就废话不多说了,直接上代码吧! def sum_numbers(num): # 1.出口 if num == 1: return 1 # 2.数组累加 temp = sum_numbers(num - 1) return num + temp result = sum_numbers(3) print(result) 输出: 6 补充拓展:python递归计数及结束递归 题目:搜索旋转排序数组 class Solution: TOTAL = 0 RUN = True def search(se

Python实现链表反转的方法分析【迭代法与递归法】

本文实例讲述了Python实现链表反转的方法.分享给大家供大家参考,具体如下: Python实现链表反转 链表反转(while迭代实现): 链表的反转引入一个cur_node变量,表示当前节点:同时需要引入一个变量new_link表示反转后的新链表:while循环内还需中间变量tmp存放当前节点的后继节点,防止原链表数据丢失. 在while循环内(循环条件为 cur_node !=None,若设置为cur_node.next将导致最后一个节点无法反转到新链表): 首先需要将当前节点的后继节点传递

python 使用递归的方式实现语义图片分割功能

实现效果 第一张图为原图,其余的图为分割后的图形 代码实现: # -*-coding:utf-8-*- import numpy as np import cv2 #---------------------------------------------------------------------- def obj_clip(img, foreground, border): result = [] height ,width = np.shape(img) visited = set()

python递归函数求n的阶乘,优缺点及递归次数设置方式

递归函数两大特点: 1.能够调用函数自身 2.至少有一个出口(结束函数自身调用) 函数实现: def calnum(num): if num != 1: # 递归调用自身函数 csum = num * calnum(num - 1) else: # 设置递归出口 csum = 1 return csum ret = calnum(5) print(ret) 递归函数的缺点: 占用资源多,一般不会优先选择. 一个程序中python默认只允许调用自身1024次,超过这个次数, python解释器会认

python json 递归打印所有json子节点信息的例子

我就废话不多说了,直接上代码吧 def json_txt(self, dic_json): #self.debug_print("json_txt") if isinstance(dic_json, dict): # 判断是否是字典类型isinstance 返回True false for key in dic_json: #dic_json = json.loads(s) s = dic_json[key] #self.debug_print(str(len(s)) + "

使用70行Python代码实现一个递归下降解析器的教程

 第一步:标记化 处理表达式的第一步就是将其转化为包含一个个独立符号的列表.这一步很简单,且不是本文的重点,因此在此处我省略了很多. 首先,我定义了一些标记(数字不在此中,它们是默认的标记)和一个标记类型: token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'} Token = namedtuple('Token', ['name', 'value']) 下面就是我用来标记 `expr` 表

python实现文法左递归的消除方法

前言 继词法分析后,又来到语法分析范畴.完成语法分析需要解决几个子问题,今天就完成文法左递归的消除. 没借鉴任何博客,完全自己造轮子. 开始之前 文法左递归消除程序的核心是对字符串的处理,输入的产生式作为字符串,对它的拆分.替换与合并操作贯穿始终,处理过程的逻辑和思路稍有错漏便会漏洞百出. 采用直接改写法,不理解左递归消除方法很难读懂代码. 要求 CFG文法判断 左递归的类型 消除直接左递归和间接左递归 界面 源码 import os import tkinter as tk import tk

python非递归全排列实现方法

刚刚开始学习python,当前看到了函数这一节.结合数组操作,写了个非递归的全排列生成.原理是插入法,也就是在一个有n个元素的已有排列中,后加入的元素,依次在前,中,后的每一个位置插入,生成n+1个新的全排列.因为Python切割数组或者字符串,以及合并比较方便,所以,程序会节省很多代码. def getArrayInsertCharToStr(STR,CHAR): arr =[] s_len = len(STR) index =0 while index <= s_len: #分割字符串 ar

Python用csv写入文件_消除空余行的方法

只做简单地记录,方便一下使用!python关于csv模块的介绍网上有很多资料,这里就不在赘诉.直接给出代码和解释. 数据: Symbol,Price,Date,Time,Change,Volume "AA",39.48,"6/11/2007","9:36am",-0.18,181800 "AIG",71.38,"6/11/2007","9:36am",-0.15,195500 "

Python数据类型之列表和元组的方法实例详解

引言 我们前面的文章介绍了数字和字符串,比如我计算今天一天的开销花了多少钱我可以用数字来表示,如果是整形用 int ,如果是小数用 float ,如果你想记录某件东西花了多少钱,应该使用 str 字符串型,如果你想记录表示所有开销的物品名称,你应该用什么表示呢? 可能有人会想到我可以用一个较长的字符串表示,把所有开销物品名称写进去,但是问题来了,如果你发现你记录错误了,想删除掉某件物品的名称,那你是不是要在这个长字符串中去查找到,然后删除,这样虽然可行,那是不是比较麻烦呢. 这种情况下,你是不是

Python字符串拼接、截取及替换方法总结分析

本文实例讲述了Python字符串拼接.截取及替换方法.分享给大家供大家参考,具体如下: python字符串连接 python字符串连接有几种方法,我开始用的第一个方法效率是最低的,后来看了书以后就用了后面的2种效率高的方法,跟大家分享一下. 先介绍下效率比较低的方法: a = ['a','b','c','d'] content = '' for i in a: content = content + i print content content的结果是:'abcd' 后来我看了书以后,发现书上

python实现删除文件与目录的方法

本文实例讲述了python实现删除文件与目录的方法.分享给大家供大家参考.具体实现方法如下: os.remove(path) 删除文件 path. 如果path是一个目录, 抛出 OSError错误.如果要删除目录,请使用rmdir(). remove() 同 unlink() 的功能是一样的 在Windows系统中,删除一个正在使用的文件,将抛出异常.在Unix中,目录表中的记录被删除,但文件的存储还在. os.removedirs(path) 递归地删除目录.类似于rmdir(), 如果子目

python字符串对其居中显示的方法

本文实例讲述了python字符串对其居中显示的方法.分享给大家供大家参考.具体如下: 下面的代码可以让字符串居中,左对齐和右对齐,字符串长度设置为50,居中后左右补充空格,右对齐会在左侧补充空格 string1 = "Now I am here." print string1.center( 50 ) print string1.rjust( 50 ) print string1.ljust( 50 ) 希望本文所述对大家的Python程序设计有所帮助.

Python捕捉和模拟鼠标事件的方法

本文实例讲述了Python捕捉和模拟鼠标事件的方法.分享给大家供大家参考.具体分析如下: 这个假期玩了不少galgame,不过有些很老的游戏没有自动运行模式,点击鼠标又太伤按键了,于是想把滚动鼠标滚轮映射为点击鼠标. 网上搜了一下,没发现什么现成的软件,而按键精灵又太重量级了,于是考虑干脆自己用Python写个算了. 这里需要把PyHook和PyWin32都装上(建议下exe版,免得安装时各种蛋疼). 翻了翻教程,发现实现起来很简单: # -*- coding: utf-8 -*- import

Python实现打印螺旋矩阵功能的方法

本文实例讲述了Python实现打印螺旋矩阵功能的方法.分享给大家供大家参考,具体如下: 一.问题描述 输入N, 打印 N*N 螺旋矩阵 比如 N = 3,打印: 1 2 3 8 9 4 7 6 5 N = 4,打印: 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 二.思路 常规法是不断的对数据边界进行判断会很复杂,不妨考虑通过递归的解决每一层的数字. 三.代码 #coding:utf-8 n = int(raw_input('>')) #初始化数组 arr = [

Python实现将一个正整数分解质因数的方法分析

本文实例讲述了Python实现将一个正整数分解质因数的方法.分享给大家供大家参考,具体如下: 遇到一个python编程联系题目:将一个正整数分解质因数.例如:输入90,打印出90=2*3*3*5. 版本一: 开始,没动脑子就开始写了,结果如下代码 #! /usr/bin/python # 014.py import math number = int(raw_input("Enter a number: ")) while number != 1: for i in range(1,