2.19 实现一个简单的递归下降分析器.pdfVIP

2.19 实现⼀个简单的递归下降分析器 问题 你想根据⼀组语法规则解析⽂本并执⾏命令，或者构造⼀个代表输⼊的抽 语法树。 如果语法⾮常简单，你可以⾃⼰写这个解析器，⽽不是使⽤⼀些框架。 解决⽅案 在这个问题中，我们集中讨论根据特殊语法去解析⽂本的问题。为了这样做，你⾸先 要以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 }* )就会被清理掉。在⼀个成功的解析中，整个右 边部分会完全展开来匹配输⼊令牌流。 有了前⾯的知识背景，下⾯我们举⼀个简单⽰例来展⽰如何构建⼀个递归下降表达式 求值程序： # !/ sr/bin/env python # -*- encoding: tf-8 -*- Topic: 下降解析器 Desc : import re import collections # Token specification NUM = r(?PNUM\d+) PLUS = r(?PPLUS\+) MINUS = r(?PMINUS-) TIMES = r(?PTIMES\*) DIVIDE = r(?PDIVIDE/) LPAREN = r(?PLPAREN\() RPAREN = r(?PRPAREN\)) WS = r(?PWS\s+) master_pat = pile(|.join([NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, WS])) # Tokenizer Token = dt ple(Token, [type, val