使用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 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

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

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

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

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

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

뜨거운 주제











DeepSeek Xiaomi를 다운로드하는 방법? Xiaomi App Store에서 "Deepseek"을 검색하십시오. 요구 사항 (검색 파일, 데이터 분석)을 식별하고 DeepSeek 기능이 포함 된 해당 도구 (예 : 파일 관리자, 데이터 분석 소프트웨어)를 찾으십시오.

DeepSeek을 효과적으로 사용하는 열쇠는 질문을 명확하게 요청하는 것입니다. 질문을 직접 그리고 구체적으로 표현하십시오. 구체적인 세부 사항 및 배경 정보를 제공합니다. 복잡한 문의의 경우 여러 각도 및 반박 의견이 포함됩니다. 코드의 성능 병목 현상과 같은 특정 측면에 중점을 둡니다. 당신이 얻는 답변에 대한 비판적 사고를 유지하고 당신의 전문 지식을 바탕으로 판단하십시오.

강력한 시맨틱 분석 알고리즘과 함께 제공되는 검색 기능을 사용하면 검색 의도를 정확하게 이해하고 관련 정보를 제공 할 수 있습니다. 그러나 인기가없는 최신 정보 또는 고려해야 할 문제가있는 검색의 경우 키워드를 조정하거나보다 구체적인 설명을 사용하고 다른 실시간 정보 소스와 결합하며 DeepSeek이 필요한 도구라는 것을 이해해야합니다. 적극적이고 명확하며 세련된 검색 전략.

DeepSeek은 프로그래밍 언어가 아니라 깊은 검색 개념입니다. DeepSeek을 구현하려면 기존 언어를 기반으로 선택해야합니다. 다양한 응용 프로그램 시나리오의 경우 적절한 언어 및 알고리즘을 선택하고 기계 학습 기술을 결합해야합니다. 코드 품질, 유지 관리 및 테스트가 중요합니다. 귀하의 요구에 따라 올바른 프로그래밍 언어, 알고리즘 및 도구를 선택하고 고품질 코드를 작성하면 성공적으로 구현할 수 있습니다.

질문 : DeepSeek은 회계에 이용 가능합니까? 답변 : 아니요, 재무 데이터를 분석하는 데 사용할 수있는 데이터 마이닝 및 분석 도구이지만 회계 소프트웨어의 회계 기록 및 보고서 생성 기능이 없습니다. DeepSeek을 사용하여 재무 데이터를 분석하려면 데이터 구조, 알고리즘 및 DeepSeek API에 대한 지식으로 데이터를 처리하기 위해 코드를 작성해야합니다. 잠재적 문제 (예 : 프로그래밍 지식, 학습 곡선, 데이터 품질).

Python은 배우기 쉽고 강력한 기능을 통해 초보자에게 이상적인 프로그래밍 입문 언어입니다. 기본 사항은 다음과 같습니다. 변수: 데이터(숫자, 문자열, 목록 등)를 저장하는 데 사용됩니다. 데이터 유형: 변수의 데이터 유형(정수, 부동 소수점 등)을 정의합니다. 연산자: 수학 연산 및 비교에 사용됩니다. 제어 흐름: 코드 실행(조건문, 루프) 흐름을 제어합니다.

Python은 초보자에게 문제 해결 능력을 부여합니다. 사용자 친화적인 구문, 광범위한 라이브러리 및 변수, 조건문 및 루프 사용 효율적인 코드 개발과 같은 기능을 제공합니다. 데이터 관리에서 프로그램 흐름 제어 및 반복 작업 수행에 이르기까지 Python은 제공합니다.

DeepSeekapi Access and Call에 대한 자세한 설명 : 빠른 시작 안내서이 기사는 DeepSeekapi에 액세스하고 전화하는 방법에 대해 자세히 안내하여 강력한 AI 모델을 쉽게 사용할 수 있도록 도와줍니다. 1 단계 : API 키를 가져와 DeepSeek 공식 웹 사이트에 액세스하고 오른쪽 상단의 "오픈 플랫폼"을 클릭하십시오. 특정 수의 무료 토큰을 얻게됩니다 (API 사용량을 측정하는 데 사용됨). 왼쪽의 메뉴에서 "Apikeys"를 클릭 한 다음 "Apikey 만들기"를 클릭하십시오. Apikey (예 : "테스트")의 이름을 지정하고 생성 된 키를 즉시 복사하십시오. 한 번만 표시 되므로이 키를 올바르게 저장하십시오.
