How to implement recursive descent Parser in Python

王林
Release: 2023-05-17 08:44:06
forward
1599 people have browsed it

    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
    Copy after login

    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
    Copy after login
    ## 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:

    How to implement recursive descent Parser in Python

    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):
            ...
    Copy after login

    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&#39;(?P<NUM>\d+)&#39;  # \d表示匹配数字,+表示任意长度
    PLUS = r&#39;(?P<PLUS>\+)&#39;  # 注意转义
    MINUS = r&#39;(?P<MINUS>-)&#39;
    TIMES = r&#39;(?P<TIMES>\*)&#39;  # 注意转义
    DIVIDE = r&#39;(?P<DIVIDE>/)&#39;
    LPAREN = r&#39;(?P<LPAREN>\()&#39;  # 注意转义
    RPAREN = r&#39;(?P<RPAREN>\))&#39;  # 注意转义
    WS = r&#39;(?P<WS>\s+)&#39;  # 别忘记空格,\s表示空格,+表示任意长度
    
    master_pat = re.compile(
        &#39;|&#39;.join([NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN, WS]))
    
    # Tokenizer
    Token = collections.namedtuple(&#39;Token&#39;, [&#39;type&#39;, &#39;value&#39;])
    
    
    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 != &#39;WS&#39;:  # 过滤掉空格符
                yield tok
    Copy after login

    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 { (&#39;+&#39;|&#39;-&#39;) 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 { (&#39;*&#39;|&#39;/&#39;) 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")
    Copy after login

    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"))
    Copy after login

    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)"))
    Copy after login

    , 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 { (&#39;+&#39;|&#39;-&#39;) term }* """
                exprval = self.term() # 取第一项
                while self._accept("PLUS") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
                    op = self.tok.type 
                    # 再取下一项,即运算符右值
                    right = self.term() 
                    if op == "PLUS":
                        exprval = (&#39;+&#39;, exprval, right)
                    elif op == "MINUS":
                        exprval -= (&#39;-&#39;, exprval, right)
                return exprval
        
        def term(self):
            """ 对应规则: term ::= factor { (&#39;*&#39;|&#39;/&#39;) factor }* """
            
            termval = self.factor() # 取第一项
            while self._accept("TIMES") or self._accept("DIVIDE"): # 如果下一项是"+"或"-"
                op = self.tok.type 
                # 再取下一项,即运算符右值
                right = self.factor() 
                if op == "TIMES":
                    termval = (&#39;*&#39;, termval, right)
                elif op == "DIVIDE":
                    termval = (&#39;/&#39;, 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")
    Copy after login

    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(&#39;2+3+4&#39;))
    Copy after login

    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 &#39;,&#39; item 
          | item
    Copy after login

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

    def items(self):
        itemsval = self.items() # 取第一项,然而此处会无穷递归!
        if itemsval and self._accept(&#39;,&#39;):
            itemsval.append(self.item())
        else:
            itemsval = [self.item()]
    Copy after login

    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 { (&#39;+&#39;|&#39;-&#39;|&#39;*&#39;|&#39;/&#39;) factor }*
    factor ::= &#39;(&#39; expr &#39;)&#39;
           | NUM
    Copy after login
    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!

    Related labels:
    source:yisu.com
    Statement of this Website
    The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
    Popular Tutorials
    More>
    Latest Downloads
    More>
    Web Effects
    Website Source Code
    Website Materials
    Front End Template
    About us Disclaimer Sitemap
    php.cn:Public welfare online PHP training,Help PHP learners grow quickly!