How to implement recursive descent Parser in Python

1. Arithmetic expression evaluation

To parse this type of text, another specific grammar rule is required. We introduce here the grammatical rules Backus Normal Form (BNF) and Extended Backus Normal Form (EBNF) that can represent context free grammar. From as small as an arithmetic expression to as large as almost all programming languages, they are defined using context-free grammars.

For simple arithmetic operation expressions, it is assumed that we have used word segmentation technology to convert it into an input tokens stream, such as NUM NUM*NUM (see the previous blog post for word segmentation method).

On this basis, we define the BNF rule as follows:

expr ::= expr + term
     | expr - term 
     | term
term ::= term * factor
     | term / factor
     | factor
factor ::= (expr)
     | NUM

Of course, this method is not concise and clear enough. What we actually use is the EBNF form:

expr ::= term { (+|-) term }*
term ::= factor { (*|/) factor }*
factor ::= (expr) 
       | NUM

## Each rule of #BNF and EBNF (an expression in the form of ::=) can be regarded as a substitution, that is, the symbol on the left can be replaced by the symbol on the right. We try to use BNF/EBNF to match the input text with grammar rules during the parsing process to complete various substitutions and expansions. In EBNF, rules placed within {...}* are optional, and * indicates that they can be repeated zero or more times (analogous to regular expressions).

The following figure vividly shows the relationship between the "recursion" and "descent" parts of the recursive descent parser (parser) and ENBF:

In practice During the parsing process, we scan the tokens stream from left to right, and process the tokens during the scanning process. If it gets stuck, a syntax error will be generated. Each grammar rule is converted into a function or method. For example, the above ENBF rule is converted into the following method:

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

In the process of calling the method corresponding to a rule, if we find the next symbol If we need to use another rule to match, we will "descend" to another rule method (such as calling term in expr and factor in term), which is the "descending" part of the recursive descent.

Sometimes methods that are already executing are called (for example, term is called in expr, factor is called in term, and expr is called in factor, which is equivalent to an ouroboros), which is recursive descent. The "recursive" part.

For the repeated parts that appear in the grammar (such as

expr ::= term { ( |-) term }*), we implement it through a while loop.

Let’s look at the specific code implementation. The first is the word segmentation part. Let’s refer to the previous article to introduce the code of the word segmentation blog.

import re
import collections

# 定义匹配token的模式
NUM = r'(?P\d+)'  # \d表示匹配数字，+表示任意长度
PLUS = r'(?P\+)'  # 注意转义
MINUS = r'(?P-)'
TIMES = r'(?P\*)'  # 注意转义
DIVIDE = r'(?P/)'
LPAREN = r'(?P\()'  # 注意转义
RPAREN = r'(?P\))'  # 注意转义
WS = r'(?P\s+)'  # 别忘记空格，\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

The following is the specific implementation of the expression evaluator:

class ExpressionEvaluator():
    """ 递归下降的Parser实现，每个语法规则都对应一个方法，
    使用 ._accept()方法来测试并接受当前处理的token，不匹配不报错，
    使用 ._except()方法来测试当前处理的token，并在不匹配的时候抛出语法错误
    """

    def parse(self, text):
        """ 对外调用的接口 """
        self.tokens = generate_tokens(text)
        self.tok, self.next_tok = None, None  # 已匹配的最后一个token，下一个即将匹配的token
        self._next()  # 转到下一个token
        return self.expr()  # 开始递归

    def _next(self):
        """ 转到下一个token """
        self.tok, self.next_tok = self.next_tok, next(self.tokens, None)

    def _accept(self, tok_type):
        """ 如果下一个token与tok_type匹配，则转到下一个token """
        if self.next_tok and self.next_tok.type == tok_type:
            self._next()
            return True
        else:
            return False

    def _except(self, tok_type):
        """ 检查是否匹配，如果不匹配则抛出异常 """
        if not self._accept(tok_type):
            raise SyntaxError("Excepted"+tok_type)

    # 接下来是语法规则，每个语法规则对应一个方法
    
    def expr(self):
        """ 对应规则： expression ::= term { ('+'|'-') term }* """
        exprval = self.term() # 取第一项
        while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
            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._except("RPAREN") # 别忘记检查是否有右括号，没有则抛出异常
            return exprval
        else:
            raise SyntaxError("Expected NUMBER or LPAREN")

We enter the following expression for testing:

e = ExpressionEvaluator()
print(e.parse("2"))
print(e.parse("2+3"))
print(e.parse("2+3*4"))
print(e.parse("2+(3+4)*5"))

The evaluation results are as follows:

2

5
14
37

If the text we enter does not comply with the grammatical rules:

print(e.parse("2 + (3 + * 4)"))

, a SyntaxError exception will be thrown:

Expected NUMBER or LPAREN. In summary, it can be seen that our expression evaluation algorithm runs correctly.

2. Generate expression tree

We got the result of the expression above, but what if we want to analyze the structure of the expression and generate a simple expression parsing tree? Then we need to make certain modifications to the methods of the above classes:

class ExpressionTreeBuilder(ExpressionEvaluator):
    def expr(self):
            """ 对应规则： expression ::= term { ('+'|'-') term }* """
            exprval = self.term() # 取第一项
            while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
                op = self.tok.type 
                # 再取下一项，即运算符右值
                right = self.term() 
                if op == "PLUS":
                    exprval = ('+', exprval, right)
                elif op == "MINUS":
                    exprval -= ('-', 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 = ('*', termval, right)
            elif op == "DIVIDE":
                termval = ('/', 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._except("RPAREN") # 别忘记检查是否有右括号，没有则抛出异常
            return exprval
        else:
            raise SyntaxError("Expected NUMBER or LPAREN")

Enter the following expression to test:

print(e.parse("2+3"))
print(e.parse("2+3*4"))
print(e.parse("2+(3+4)*5"))
print(e.parse('2+3+4'))

The following is the generated result:

(' ' , 2, 3)

(' ', 2, ('*', 3, 4))
(' ', 2, ('*', (' ', 3, 4), 5))
(' ', (' ', 2, 3), 4)

You can see that the expression tree is generated correctly.

Our example above is very simple, but the recursive descent parser can also be used to implement quite complex parsers. For example, Python code is parsed through a recursive descent parser. If you are interested in this, you can check the

Grammar file in the Python source code to find out. However, as we will see below, writing a parser yourself comes with various pitfalls and challenges.

Left recursion and operator precedence trap

Any grammar rule involving the

left recursion form cannot be solved by the recursive descent parser. The so-called left recursion means that the leftmost symbol on the right side of the rule expression is the rule header. For example, for the following rules:

items ::= items ',' item 
      | item

To complete the analysis, you may define the following method:

def items(self):
    itemsval = self.items() # 取第一项，然而此处会无穷递归！
    if itemsval and self._accept(','):
        itemsval.append(self.item())
    else:
        itemsval = [self.item()]

This will In the first line,

self.items() is called infinitely, resulting in an infinite recursion error.

There is also an error in the grammar rules themselves, such as operator precedence. If we ignore the operator precedence and directly simplify the expression as follows:

expr ::= factor { ('+'|'-'|'*'|'/') factor }*
factor ::= '(' expr ')'
       | NUM

PYTHON Copy full screen

This syntax can be technically implemented, but the calculation order convention is not followed, resulting in "3 4* 5" evaluates to 35 instead of 23 as expected. Therefore, separate expr and term rules are required to ensure the correctness of the calculation results.

The above is the detailed content of How to implement recursive descent Parser in Python. For more information, please follow other related articles on the PHP Chinese website!