👩‍🏫 🍅 🧒🏿 再次关于使用递归下降法的表达式分析 🦗 🐕 👨🏻‍🍳

当我从出版社Dialog MEPhI手中买到“初学者课程C和C ++”一书时，我还是一个小学生。正是从这本书中，我了解了面向对象编程的基础知识，这也给我带来了一个我无法解决很长时间的问题。最后是一个列出程序的应用程序，其中一个被称为递归计算器。这是我第一次使用递归下降法分析算术表达式。我仍然记得花了很长时间试图至少理解这段代码中的某些内容。

本文主要是针对那些首次遇到解析表达式任务的用户。

因此，在编写算术表达式的解析器之前，我们需要了解这些表达式的结构。为简单起见，我们暂时不考虑一元减号运算和在表达式中使用函数的可能性。

为了描述结构，我们使用Beckus-Naur形式

E-> T + E | T-E | Ť
T-> F * T | F / t | F
F-> N | （E）

这是竖线“ |” 表示逻辑运算符“或”，以及E，T，F，N-使用这些语句时会将原始表达式拆分成的各种类型的子表达式。在这种情况下，N表示数字。

第一句话意味着类型E的表达式可以由类型T的表达式加上类型E的表达式或者类型T的表达式减去类型E的表达式或者只是类型T的表达式组成。

对于第二句话，一切都相似，但是除了加减运算之外，还有乘法运算和师。

第三句话表示类型F的表达式是数字或括号中的类型E的表达式。

让我们尝试将这三个句子应用于算术表达式的示例

2 + 3 *（4-5）+ 6-7

我们多次应用第一句话

E（2 + 3 *（4-5）+ 6-7）-> 
T（2）+ E（3 *（4-5）+ 6-7）-> 
T（2）+ T（3 *（4-5））+ E（6-7）-> 
T（2）+ T（3 *（4-5））+ T（6）-T（7）

现在，我们的表达式仅由类型T的子表达式组成，因此我们将第二句话应用于每个子表达式。

T（2）-> F（2）
T（3 *（4-5））-> F（3）* T（（4-5））-> F（3）* F（（4-5））
T（6）-> F（6）
T（7）-> F（7）

该是第三句话了

F（2）-> N（2）-> 2
F（3）-> N（3）-> 3
F（（4-5））-> E（4-5）
F（6）-> N（6）-> 6
F（7）-> N（7）-> 7

对于方括号（4-5）中的表达式，我们以递归方式切换到第一句，并且必须类似于该表达式其余部分的内容重复所有动作。如果表达式包含嵌套的方括号，则将有更多这样的递归转换。我建议您独立尝试将所有三个句子应用于包含嵌套括号级别的表达式，例如2 + 2 *（3 + 4 *（5-6）），以确保它们也适用。

现在，我们只需要以代码的形式实施提案执行的操作。这将是使用递归下降方法对表达式进行的分析，但是在开始编写代码之前，让我们通过消除前两个语句的递归来简化句子。

如果我们无休止地将第一个句子替换成它自己，那么我们得到

E-> T±T±T±T±...±T

第二句话可以类似的方式转换。

T-> F * / F * / F * / * / ... * / F

实际上，这意味着我们可以在此处使用循环而不是递归。同样，递归不能从第三句中排除。

我们将用Java编写代码，因为这是我目前最熟悉的编程语言。在我们开始编写代码之前的最后一句话-我省略了令牌化的任务，即将表达式分成不可分割的重要元素（标记）。此类标记是数字，算术运算符号和方括号。假设我们已经有一个令牌数组作为表达式的输入。

String[] tokens = {"2", "+", "3", "*", "(", "4", "-", "5", ")", "+", "6", "-", "7"};

创建将包含方法的下一个解析器类

parse（）开始解析表达式
expression（）处理E类型的表达式
term（）用于处理类型T的表达式
用于处理F和N类型表达式的factor（）

public class RecursiveDescentParser {

    private final String[] tokens;
    private int pos = 0; //   

    public RecursiveDescentParser(String[] tokens) {
        this.tokens = tokens;
    }

    public Double parse() {
        Double result = expression();
        if (pos != tokens.length) {
            throw new IllegalStateException("Error in expression at " + tokens[pos]));
        }
        return result;
    }

    // E -> T±T±T±T± ... ±T
    private Double expression() {
        //   
        Double first = term();

        while (pos < tokens.length) {
            String operator = tokens[pos];
            if (!operator.equals("+") && !operator.equals("-")) {
                break;
            } else {
                pos++;
            }

            //    ()
            Double second = term();
            if (operator.equals("+")) {
                first += second;
            } else {
                first -= second;
            }
        }
        return first;
    }

    // T -> F*/F*/F*/*/ ... */F
    private Double term() {
        //   
        Double first = factor();

        while (pos < tokens.length) {
            String operator = tokens[pos];
            if (!operator.equals("*") && !operator.equals("/")) {
                break;
            } else {
                pos++;
            }

            //    ()
            Double second = factor();
            if (operator.equals("*")) {
                first *= second;
            } else {
                first /= second;
            }
        }
        return first;
    }
    
    // F -> N | (E)
    private Double factor() {
        String next = tokens[pos];
        Double result;
        if (next.equals("(")) {
            pos++;
            //    ,        
            result = expression();  
            String closingBracket;
            if (pos < tokens.length) {
                closingBracket = tokens[pos];
            } else {
                throw new IllegalStateException("Unexpected end of expression");
            }
            if (pos < tokens.length && closingBracket.equals(")")) {
                pos++;
                return result;
            }
            throw new IllegalStateException("')' expected but " + closingBracket);
        }
        pos++;
        //       
        return Double.parseDouble(next);
    }
}

就这样。如果需要，可以教该解析器使用一元减号或表达式中的函数。首先要做的是更改原始句子，以使它们考虑到表达结构的新元素，并且由此可能会有更多建议。一旦对它们进行了适当的修改，实现就几乎成为正式的了。

再次关于使用递归下降法的表达式分析

More articles: