使用70行Python代码实现一个递归下降解析器的教程
第一步:标记化
处理表达式的第一步就是将其转化为包含一个个独立符号的列表。这一步很简单,且不是本文的重点,因此在此处我省略了很多。
首先,我定义了一些标记(数字不在此中,它们是默认的标记)和一个标记类型:
token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'} Token = namedtuple('Token', ['name', 'value'])
下面就是我用来标记 `expr` 表达式的代码:
split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr) tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr]
第一行是将表达式分割为基本标记的技巧,因此
'1.2 / ( 11+3)' --> ['1.2', '/', '(', '11', '+', '3', ')']
下一行命名标记,这样分析器就能通过分类识别它们:
['1.2', '/', '(', '11', '+', '3', ')'] -> [Token(name='NUM', value='1.2'), Token(name='MUL', value='/'), Token(name='LPAR', value='('), Token(name='NUM', value='11'), Token(name='ADD', value='+'), Token(name='NUM', value='3'), Token(name='RPAR', value=')')]
任何不在 token_map 中的标记被假定为数字。我们的分词器缺少称为验证的属性,以防止非数字被接受,但幸运的是,运算器将在以后处理它。
就是这样
第二步: 语法定义
我选择的解析器实现自一个本地垂直解析器,其来源于LL解析器的一个简单版本。它是一个最简单的解析器实现,事实上,只有仅仅14行代码。它是一种自上而下的解析器,这意味着解析器从最上层规则开始解析(like:expression),然后以递归方式尝试按照其子规则方式解析,直至符合最下层的规则(like:number)。换句话解释,当自底向上解析器(LR)逐步地收缩标记,使规则被包含在其它规则中,直到最后仅剩下一个规则,而自顶向下解析器(LL)逐步展开规则并进入到少数的抽象规则,直到它能够完全匹配输入的标记。
在深入到实际的解析器实现之前,我们可对语法进行讨论。在我之前发表的文章中,我使用过LR解析器,我可以像如下方式定义计算器语法(标记使用大写字母表示):
add: add ADD mul | mul; mul: mul MUL atom | atom; atom: NUM | '(' add ')' | neg; neg: '-' atom;
(如果您还不理解上述语法,请阅读我之前发表的文章)
现在我使用LL解析器,以如下方式定义计算器的语法:
rule_map = { 'add' : ['mul ADD add', 'mul'], 'mul' : ['atom MUL mul', 'atom'], 'atom': ['NUM', 'LPAR add RPAR', 'neg'], 'neg' : ['ADD atom'], }
大家可以看到,这里有一个微妙的变化。有关"add and mul"的递归定义被反转了。这是个非常重要的细节,我会向大家详细说明这一点。
LR版本使用了左递归的模式。当LL解析器遇到递归的时候,它会尝试去匹配规则。所以,当左递归发生是,解析器会进入无穷递归。甚至连聪明的LL解析器例如ANTLR也逃避不了这个问题,它会以友好的错误提示代替无穷的递归,而不像我们这个玩具解析器那样。
左递归可以很容易的转变为右递归,我就这么做的。但是解析器并不是那么简单,它又会产生另一个问题:当左递归正确的解析 3-2-1 为(3-2)-1,而右递归却错误的解析为3-(2-1)。我还没想到一个简单的解决办法,所以为了让事情简单,我决定让它继续使用错误的解析格式,并在后面处理这个问题(请看步骤4)
第三步:解析为一个AST
算法其实很简单。我们会定义一个接收两个参数的递归方法:第一个参数是我们要尝试匹配的规则名称,第二个参数是我们要保留的标识列表。我们从add(最上层规则)方法开始,其已包含完整的标识列表,递归调用已非常明确。方法将返回一个数组,其包含元素为:一个是当前匹配项,另一个是保留匹配的标识列表。我们将实现标识匹配功能,以使这段代码可用(它们都是字符串类型;一个是大写格式,另一个是小写格式)。
以下是解析器实现的代码:
RuleMatch = namedtuple('RuleMatch', ['name', 'matched']) def match(rule_name, tokens): if tokens and rule_name == tokens[0].name: # 是否匹配标识? return RuleMatch(tokens[0], tokens[1:]) for expansion in rule_map.get(rule_name, ()): # 是否匹配规则? remaining_tokens = tokens matched_subrules = [] for subrule in expansion.split(): matched, remaining_tokens = match(subrule, remaining_tokens) if not matched: break # 运气不好,跳出循环,处理下一个扩展定义! matched_subrules.append(matched) else: return RuleMatch(rule_name, matched_subrules), remaining_tokens return None, None # 无匹配结果
代码4至5行说明:如果规则名称(rule_name)确实是一个标识,并被包含在标识列表(tokens)中,同时检查其是否匹配当前标识。如果是,表达式将返回匹配方法,标识列表任然进行使用。
代码第6行说明:迭代将循环检查是否匹配该规则名称对应的子规则,通过递归实现每条子规则的匹配。如果规则名称满足匹配标识的条件,get()方法将返回一个空数组,同时代码将返回空值(见16行)。
第9-15行,实现迭代当前的sub-rule,并尝试顺序地匹配他们。每次迭代都尽可能多的匹配标识。如果某一个标识无法匹配,我们就会放弃整个sub-rule。但是,如果所有的标识都匹配成功,我们就到达else语句,并返回rule_name的匹配值,还有剩下标识。
现在运行并看看1.2/(11+3)的结果。
>>> tokens = [Token(name='NUM', value='1.2'), Token(name='MUL', value='/'), Token(name='LPAR', value='('), Token (name='NUM', value='11'), Token(name='ADD', value='+'), Token(name='NUM', value='3'), Token(name='RPAR', value=')')] >>> match('add', tokens) (RuleMatch(name='add', matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='1.2')]), Token(name='MUL', value='/'), RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='LPAR', value='('), RuleMatch(name='add', matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='11')])]), Token(name='ADD', value='+'), RuleMatch(name='add', matched=[RuleMatch(name='mul', matched=[RuleMatch(name='atom', matched=[Token(name='NUM', value='3')])])])]), Token(name='RPAR', value=')')])])])]), [])
结果是一个tuple,当然我们并没有看到有剩下的标识。匹配结果并不易于阅读,所以让我吧结果画成一个图:
add mul atom NUM '1.2' MUL '/' mul atom LPAR '(' add mul atom NUM '11' ADD '+' add mul atom NUM '3' RPAR ')'
这就是概念上的AST。通过你思维逻辑,或者在纸上描绘,想象解析器是如何运作的,这样是个很好的锻炼。我不敢说这样是必须的,除非你想神交。你可以通过AST来帮助你实现正确的算法。
到目前为止,我们已经完成了可以处理二进制运算,一元运算,括号和操作符优先权的解析器。
现在只剩下一个错误待解决,下面的步骤我们将解决这个错误。
第四步:后续处理
我的解析器并非在任何场合管用。最重要的一点是,它并不能处理左递归,迫使我把代码写成右递归方式。这样导致,解析 8/4/2 这个表达式的时候,AST结果如下:
add mul atom NUM 8 MUL '/' mul atom NUM 4 MUL '/' mul atom NUM 2
如果我们尝试通过AST计算结果,我们将会优先计算4/2,这当然是错误的。一些LL解析器选择修正树里面的关联性。这样需要编写多行代码;)。这个不采纳,我们需要使它扁平化。算法很简单:对于AST里面的每个规则 1)需要修正 2)是一个二进制运算 (拥有sub-rules)3) 右边的操作符同样的规则:使后者扁平成前者。通过“扁平”,我意思是在其父节点的上下文中,通过节点的儿子代替这个节点。因为我们的穿越是DFS是后序的,意味着它从树的边缘开始,并一直到达树根,效果将会累加。如下是代码:
fix_assoc_rules = 'add', 'mul' def _recurse_tree(tree, func): return map(func, tree.matched) if tree.name in rule_map else tree[1] def flatten_right_associativity(tree): new = _recurse_tree(tree, flatten_right_associativity) if tree.name in fix_assoc_rules and len(new)==3 and new[2].name==tree.name: new[-1:] = new[-1].matched return RuleMatch(tree.name, new)
这段代码可以让任何结构的加法或乘法表达式变成一个平面列表(不会混淆)。括号会破坏顺序,当然,它们不会受到影响。
基于以上的这些,我可以把代码重构成左关联:
def build_left_associativity(tree): new_nodes = _recurse_tree(tree, build_left_associativity) if tree.name in fix_assoc_rules: while len(new_nodes)>3: new_nodes[:3] = [RuleMatch(tree.name, new_nodes[:3])] return RuleMatch(tree.name, new_nodes)
但是,我并不会这样做。我需要更少的代码,并且把计算代码换成处理列表会比重构整棵树需要更少的代码。
第五步:运算器
对树的运算非常简单。只需用与后处理的代码相似的方式对树进行遍历(即 DFS 后序),并按照其中的每条规则进行运算。对于运算器,因为我们使用了递归算法,所以每条规则必须只包含数字和操作符。代码如下:
bin_calc_map = {'*':mul, '/':div, '+':add, '-':sub} def calc_binary(x): while len(x) > 1: x[:3] = [ bin_calc_map[x[1]](x[0], x[2]) ] return x[0] calc_map = { 'NUM' : float, 'atom': lambda x: x[len(x)!=1], 'neg' : lambda (op,num): (num,-num)[op=='-'], 'mul' : calc_binary, 'add' : calc_binary, } def evaluate(tree): solutions = _recurse_tree(tree, evaluate) return calc_map.get(tree.name, lambda x:x)(solutions)
我使用 calc_binary 函数进行加法和减法运算(以及它们的同阶运算)。它以左结合的方式计算列表中的这些运算,这使得我们的 LL语法不太容易获取结果。
第六步:REPL
最朴实的REPL:
if __name__ == '__main__': while True: print( calc(raw_input('> ')) )
不要让我解释它 :)
附录:将它们合并:一个70行的计算器
'''A Calculator Implemented With A Top-Down, Recursive-Descent Parser''' # Author: Erez Shinan, Dec 2012 import re, collections from operator import add,sub,mul,div Token = collections.namedtuple('Token', ['name', 'value']) RuleMatch = collections.namedtuple('RuleMatch', ['name', 'matched']) token_map = {'+':'ADD', '-':'ADD', '*':'MUL', '/':'MUL', '(':'LPAR', ')':'RPAR'} rule_map = { 'add' : ['mul ADD add', 'mul'], 'mul' : ['atom MUL mul', 'atom'], 'atom': ['NUM', 'LPAR add RPAR', 'neg'], 'neg' : ['ADD atom'], } fix_assoc_rules = 'add', 'mul' bin_calc_map = {'*':mul, '/':div, '+':add, '-':sub} def calc_binary(x): while len(x) > 1: x[:3] = [ bin_calc_map[x[1]](x[0], x[2]) ] return x[0] calc_map = { 'NUM' : float, 'atom': lambda x: x[len(x)!=1], 'neg' : lambda (op,num): (num,-num)[op=='-'], 'mul' : calc_binary, 'add' : calc_binary, } def match(rule_name, tokens): if tokens and rule_name == tokens[0].name: # Match a token? return tokens[0], tokens[1:] for expansion in rule_map.get(rule_name, ()): # Match a rule? remaining_tokens = tokens matched_subrules = [] for subrule in expansion.split(): matched, remaining_tokens = match(subrule, remaining_tokens) if not matched: break # no such luck. next expansion! matched_subrules.append(matched) else: return RuleMatch(rule_name, matched_subrules), remaining_tokens return None, None # match not found def _recurse_tree(tree, func): return map(func, tree.matched) if tree.name in rule_map else tree[1] def flatten_right_associativity(tree): new = _recurse_tree(tree, flatten_right_associativity) if tree.name in fix_assoc_rules and len(new)==3 and new[2].name==tree.name: new[-1:] = new[-1].matched return RuleMatch(tree.name, new) def evaluate(tree): solutions = _recurse_tree(tree, evaluate) return calc_map.get(tree.name, lambda x:x)(solutions) def calc(expr): split_expr = re.findall('[\d.]+|[%s]' % ''.join(token_map), expr) tokens = [Token(token_map.get(x, 'NUM'), x) for x in split_expr] tree = match('add', tokens)[0] tree = flatten_right_associativity( tree ) return evaluate(tree) if __name__ == '__main__': while True: print( calc(raw_input('> ')) )

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











PHP는 웹 개발 및 빠른 프로토 타이핑에 적합하며 Python은 데이터 과학 및 기계 학습에 적합합니다. 1.PHP는 간단한 구문과 함께 동적 웹 개발에 사용되며 빠른 개발에 적합합니다. 2. Python은 간결한 구문을 가지고 있으며 여러 분야에 적합하며 강력한 라이브러리 생태계가 있습니다.

PHP는 주로 절차 적 프로그래밍이지만 객체 지향 프로그래밍 (OOP)도 지원합니다. Python은 OOP, 기능 및 절차 프로그래밍을 포함한 다양한 패러다임을 지원합니다. PHP는 웹 개발에 적합하며 Python은 데이터 분석 및 기계 학습과 같은 다양한 응용 프로그램에 적합합니다.

VS 코드는 Windows 8에서 실행될 수 있지만 경험은 크지 않을 수 있습니다. 먼저 시스템이 최신 패치로 업데이트되었는지 확인한 다음 시스템 아키텍처와 일치하는 VS 코드 설치 패키지를 다운로드하여 프롬프트대로 설치하십시오. 설치 후 일부 확장은 Windows 8과 호환되지 않을 수 있으며 대체 확장을 찾거나 가상 시스템에서 새로운 Windows 시스템을 사용해야합니다. 필요한 연장을 설치하여 제대로 작동하는지 확인하십시오. Windows 8에서는 VS 코드가 가능하지만 더 나은 개발 경험과 보안을 위해 새로운 Windows 시스템으로 업그레이드하는 것이 좋습니다.

VS 코드는 파이썬을 작성하는 데 사용될 수 있으며 파이썬 애플리케이션을 개발하기에 이상적인 도구가되는 많은 기능을 제공합니다. 사용자는 다음을 수행 할 수 있습니다. Python 확장 기능을 설치하여 코드 완료, 구문 강조 및 디버깅과 같은 기능을 얻습니다. 디버거를 사용하여 코드를 단계별로 추적하고 오류를 찾아 수정하십시오. 버전 제어를 위해 git을 통합합니다. 코드 서식 도구를 사용하여 코드 일관성을 유지하십시오. 라인 도구를 사용하여 잠재적 인 문제를 미리 발견하십시오.

VS 코드 확장은 악의적 인 코드 숨기기, 취약성 악용 및 합법적 인 확장으로 자위하는 등 악성 위험을 초래합니다. 악의적 인 확장을 식별하는 방법에는 게시자 확인, 주석 읽기, 코드 확인 및주의해서 설치가 포함됩니다. 보안 조치에는 보안 인식, 좋은 습관, 정기적 인 업데이트 및 바이러스 백신 소프트웨어도 포함됩니다.

vs 코드에서는 다음 단계를 통해 터미널에서 프로그램을 실행할 수 있습니다. 코드를 준비하고 통합 터미널을 열어 코드 디렉토리가 터미널 작업 디렉토리와 일치하는지 확인하십시오. 프로그래밍 언어 (예 : Python의 Python Your_file_name.py)에 따라 실행 명령을 선택하여 성공적으로 실행되는지 여부를 확인하고 오류를 해결하십시오. 디버거를 사용하여 디버깅 효율을 향상시킵니다.

Python은 부드러운 학습 곡선과 간결한 구문으로 초보자에게 더 적합합니다. JavaScript는 가파른 학습 곡선과 유연한 구문으로 프론트 엔드 개발에 적합합니다. 1. Python Syntax는 직관적이며 데이터 과학 및 백엔드 개발에 적합합니다. 2. JavaScript는 유연하며 프론트 엔드 및 서버 측 프로그래밍에서 널리 사용됩니다.

VS 코드는 Mac에서 사용할 수 있습니다. 강력한 확장, GIT 통합, 터미널 및 디버거가 있으며 풍부한 설정 옵션도 제공합니다. 그러나 특히 대규모 프로젝트 또는 고도로 전문적인 개발의 경우 VS 코드는 성능 또는 기능 제한을 가질 수 있습니다.
