课本上的两个例子
这些课堂笔记记录了一个程序的扩展示例，该程序可以解析和计算用户输入的代数表达式。这个例子部分基于课本中的两个例子，第5.11节的递归下降解释器和第6.12节的表达式树例子（第三版第6.10节）。读完这些课堂讲稿后，你可能会想要复习课本中的这些章节。
完整的示例源代码
这里是包含此示例完整源代码的归档文件。
语法、解析树和解析器
我们将在课堂讲稿中开发的程序用一种简单的编程语言读取和解释语句。下面是该程序的一个典型运行示例。
A = 2 2 b = A + 3 5 A *2 + b - 5
每次用户键入一行输入时，程序将计算该输入并输出该输入的值。该程序接受为变量设置值的语句，并允许您键入使用这些变量的算术表达式。用户可以在该程序中输入的有效表达式集由一种非常简单的编程语言控制。该程序有能力分析其输入的结构，然后对其进行评估。
赢博体育编程语言都必须遵循一组结构规则——最常见的是，这些结构规则可以通过与上下文无关的语法来表示。语法是一组结构规则，描述如何将语言中的语句分解为更小的元素，一直分解到语句中的单个元素，如数字、变量和操作符。
下面是我们的程序将要使用的简单语言的一组语法规则。
语句->赋值|计算赋值->变量‘=’ sum end计算-> sum end sum -> product (('+' product)|('-' product))* product -> factor (('*' factor)|('/' factor))* factor -> power | term power -> term '^' factor term -> group | variable | number group -> '(' sum ')‘)’
语法规则由语法变量、终端符号和操作符组成。每个语法规则由一个语法变量、->箭头和一个右手边组成。右手边由一个或多个由操作符连接的语法表达式组成。在我们的示例语法中出现的两个操作符是或操作符|和Kleene星号操作符*。or操作符告诉我们，语法变量可以展开为一个或多个替代项。例如，语法规则
因子->项|次方
表示变量因子可以展开为项变量或幂变量。
Kleene星号运算符表示我们可以有0个或多个实例。例如，规则
Product -> factor (('*' factor)|('/' factor))*
表示产品是单个因子，后面跟着0个或多个（“*”因子）或（“/”因子）实例。
语法规则用于构造派生。在派生中，我们从语法的start符号语句（在本例中）开始，并赢博体育一系列语法规则。每次赢博体育一个语法规则时，我们都用它来用一组新的变量或结束符号替换其中一个语法变量。
这里有一个具体的例子。表达式
3 + 4 * （5 + 2）
在我们的语言中是一个有效的表达式。我们可以通过构造一个以变量语句开始并以等价于上面文本的内容结束的派生来证明表达式是有效的：
声明= = > >计算总和端= >产品“+”端= >因素“+”产品= >任期结束' + '产品结束= >数量' + '产品结束= >数量' + '因素‘*’因素结束= >数量' + '结束词‘*’因素= >号“+”号‘*’因素结束= >号“+”号‘*’组结束= >号“+”号‘*’”(“总和”)结束= >数量”+“数量”*“(“产品”+“产品”)“数量= >终结”+“数量”*“(“因素”+“产品”)“数量= >终结”+“数量”*“(“术语”+“产品”)“结束= >号码”+“数字‘*’”(“号码”+“产品”)的结束= >号“+”号‘*’”(“号码”+“因素”)的结束= >号“+”号‘*’”(“号码”+“术语”)的结束= >号“+”号‘*’”(“号码”+“数量”)的结束
解析器是一种软件程序，它将表达式作为输入，并尝试使用可用的语法规则为表达式构造派生。在下面的示例程序中，我将构造一种特殊类型的解析器，称为递归下降解析器。这种类型的解析器使用一组递归函数复制语法规则。
下面是我将要使用的解析器类的类声明。
类解析器{公共：解析器（char* line）；~解析器();表达式*语句();private: Tokenizer* tokens；表达式*分配();计算表达式* ();表达式* sum ();表达式*产品();表达式()*因素;表达式* ();表达式*术语();表达式*组();表达式*数量();表达式*变量();}；
这里首先要注意的是，解析器类为表达式语法中的每个语法变量都包含一个方法。每种方法的目的都是确定输入中是否存在可以从特定语法变量派生的某些结构。
下面是其中一个成员函数的示例。
表达式* Parser::factor(){表达式*exp = nullptr；如果((exp=power()) | (exp=term())；返回经验;｝
该方法对语法规则进行建模
因子->次方|项
该方法试图通过首先试图证明存在有效功率来确定是否存在有效因子。如果失败，它将尝试证明存在一个项。这里使用的精确机制利用了c++ ||运算符的短路求值规则。c++将从左到右计算逻辑值，但只会直到找到一个计算结果为真的项。一旦遇到该true，则不会对or中的其余表达式进行求值。这段代码以一种微妙而重要的方式利用了这种行为。if中的or表达式首先调用power（）。如果power（）返回的值不是nullptr（表示成功），则将该值赋值给exp。赋值的副作用是对赋值的值求值，在本例中是指针值。由于指针值不是nullptr，因此它的计算结果为true，在我们有机会尝试调用term（）之前短路了or。另一方面，如果power（）返回nullptr，则or中的第一个子句的计算结果将为false，这将迫使我们继续尝试第二个子句。第二个子句调用term()，它现在可以返回一个指向有效对象的指针。
Parser类构造函数接受一个参数，即指向包含输入表达式的字符数组的指针。构造函数将使用该文本初始化第二个对象Tokenizer。标记器的目的是将输入分解成不同的块，称为标记。这些记号对应于语法中的终结符号。我们在这里使用的示例语法有四个结束符号，数字，变量，结束和各种字符。
下面是Parser类中的一个方法示例，该方法使用Tokenizer查找特定类型的令牌。
Expression* Parser::assignment() {int mark = tokens->mark()；变量表达式*var = nullptr；表达式*rhs = nullptr；如果(（var=tokens->变量（））&& token ->字符（'='）&& (rhs=sum（)) && token ->atEnd()）返回新的AssignmentExpression(var, rhs)；如果（var）删除var；如果（rhs）删除rhs；令牌- >重置(马克);返回nullptr;｝
这个方法符合语法规则
赋值->变量‘=’ sum结束
在这个规则中，sum是一个语法变量，而variable和end是结束符号。注意该方法如何使用标记器中的variable（）方法来确定该元素是否出现在输入中的当前位置。
除了简单地确定输入中是否存在特定的结构之外，解析器方法还有一个重要的副作用。每当其中一个解析器方法找到一个有效的结构时，它将构造一个包含有关该结构的信息的表达式树。本例中的结构树由Expression节点组成。如果其中一个解析器方法失败，它将通过返回nullptr而不是指向表达式树的指针来表示失败。
解析器类还具有回溯失败解析的能力。一些语法规则要求我们在一个序列中找到几个结构。如果我们在失败之前完成了该序列的一半，我们将不得不回到输入的早期点并尝试不同的选择。上面的assignment（）示例展示了这是如何工作的。
Expression* Parser::assignment() {int mark = tokens->mark()；变量表达式*var = nullptr；表达式*rhs = nullptr；如果(（var=tokens->变量（））&& token ->字符（'='）&& (rhs=sum（)) && token ->atEnd()）返回新的AssignmentExpression(var, rhs)；如果（var）删除var；如果（rhs）删除rhs；令牌- >重置(马克);返回nullptr;｝
为了完成赋值操作，我们需要看到一个变量、一个“=”符号、一个完整的和，以及输入的结尾。如果我们没有看到赢博体育这些东西，我们必须删除我们在此过程中构造的赢博体育部分表达式，并将Tokenizer重置为我们开始该过程时的状态。
重置输入的机制通过Tokenizer类中的mark（）和reset（）方法工作。mark（）方法返回一个int值，告诉我们在输入字符串中的当前位置。通过保存此位置并最终在失败时将其传递回reset（）方法，我们可以将Tokenizer重置回其先前的位置，以便解析器可以尝试替代路由。
上面的例子还说明了c++中逻辑的短路行为。在c++中，从左到右计算逻辑和表达式，直到其中一个表达式的计算结果为false。此时，赢博体育求值停止，整个and表达式求值为false。这种短路行为对于解析器来说很重要，因为一旦解析器看到不合适的东西，它就应该停止尝试并重置回以前的位置。例如，如果遇到的第一个元素不是变量，上面的assignment（）解析器方法将立即停止。
表达式树
当解析器成功地找到特定输入字符串的有效派生时，它将通过为输入表达式构造表达式树来响应。例如，我们在上面确定了输入表达式
3 + 4 * （5 + 2）
通过构造一个有效的派生，在我们的语言中是一个有效的表达式。下面是解析器方法将在解析结束时返回的表达式树的图片：
在一次有效解析之后，我们将最终构造的树是异构结构的一个例子。异构结构是由由指针连接在一起的节点组成的数据结构，但节点的类型并不相同。
这就提出了一个明显的问题。由于树结构中的许多节点需要指向子节点，如果我们不知道子节点是什么类型的东西，我们如何设置这些指针？
解决这个问题的方法是使用c++语言特性、继承和多态性的强大组合。
我们首先为表达式节点创建一个基类，expression类：
类表达式{公共：表达式（）；虚拟~表达式();静态无效initvar ()；静态双查找（const std::string& var）；静态空记录（const std::string& var，双精度值）；虚拟双精度的evaluate() = 0；static std::map<std::string, double> vars；}；
然后，我们创建一系列从这个基类继承的更具体的类：NumberExpression、VariableExpression、ArithmeticExpression和AssignmentExpression类。例如，下面是ArithmeticExpression类的声明：
类算术表达式：公共表达式{公共：算术表达式（char op，表达式*左，表达式*右）；虚拟~ ArithmeticExpression ();Virtual double evaluate()；private：表达式*左，*右；char op;}；
public Expression语法表示ArithmeticExpression类继承自Expression类。在这种关系中，我们说Expression类是基类，而ArithmeticExpression是派生类。
还要注意，ArithmeticExpression类自然包含两个指向子对象的指针。这些指针被声明为指向Expression对象的指针。由于赢博体育的派生类（如NumberExpression或VariableExpression）都派生自Expression，因此指向这些类型中的任何一种的指针都算作指向有效Expression对象的指针。
Expression类声明的一个重要部分是这一行：
虚拟双精度的evaluate() = 0；
这个声明建立了一种特殊的成员函数，称为虚函数。虚函数与继承层次协同工作，并有助于解决使用指向基类的指针所引起的一些问题。考虑下面的例子：
表达式*lhs = new NumberExpression("2")；表达式*rhs = new NumberExpression("3")；表达式*exp =新算术表达式（'+',lhs,rhs）；Double value = exp->evaluate()；
首先，这段代码是有效的，因为算术表达式在技术上也是一个表达式，所以我们可以在变量exp中存储一个指向算术表达式的指针。当我们执行exp->evaluate（）时，会出现有趣的行为。当编译器遇到此代码时，它将首先检查Expression类是否包含evaluate（）方法。Expression类确实包含这样一个方法，而且该方法被声明为虚方法。当一个方法被声明为virtual时，系统将计算出exp所指向的对象的实际类型，并调用适合该类型对象的evaluate（）方法的版本。在本例中，exp实际上指向一个ArithmeticExpression对象，因此我们最终将调用虚函数的ArithmeticExpression版本。
从上面的类声明中可以看到，ArithmeticExpression包含evaluate（）方法的重载，因此虚函数机制将正确调用该版本的evaluate()，而不是在Expression类中找到的版本。此外，由于派生自Expression类的每个类都有自己对evaluate（）方法的重写，因此Expression类甚至不需要该方法的版本。其实，什么宣言
虚拟双精度的evaluate() = 0；
实际上说的是evaluate（）是Expression类中的虚方法，但我们不会提供该方法的实现。相反，每个派生类都将提供自己版本的evaluate（）。
虚函数使一些非常强大的行为成为可能。下面是ArithmeticExpression类版本的evaluate（）方法的代码：
双算术表达式：：evaluate(){如果（左== nullptr ||右== nullptr）返回0；Double result = 0；Double a = left->evaluate()；Double b =右->evaluate()；Switch (op) {case '+': result = a + b；打破;Case '-': result = a - b；打破;Case '*': result = a * b；打破;Case '/': result = a / b；打破;Case '^': result = std::pow(a, b)；打破;}返回结果；｝
算术表达式类包含两个子指针，左和右。这两个指针都被声明为指向Expression对象的指针。实际上，这些指针指向的对象可能具有许多不同类型中的任何一种，例如NumberExpression、VariableExpression或ArithmeticExpression。当上面的代码在两个子对象上调用evaluate（）方法时，虚函数机制将自动为每个子对象调用正确版本的evaluate（）方法，因此我们不必担心子对象实际上是什么类型的对象。
在析构函数中使用虚函数的另一个地方。下面是ArithmeticExpression类的析构函数：
算术表达式：：~算术表达式（）{if (left) delete left；如果（右）删除右；｝
此方法在两个子指针上调用delete，从而导致运行这些子对象的析构函数。如果您回顾一下上面的Expression和ArithmeticExpression类的声明，您将看到Expression类中的析构函数被声明为虚函数。同样，这使得在对其中一个子指针调用delete时自动选择正确的析构函数成为可能。
编程任务
在本作业中，您将扩展程序可以处理的简单语言，以包含函数调用。为此，您将向底层语言添加两个新功能：定义函数的能力和在函数定义后调用该函数的能力。下面是一个程序运行的例子来说明它是如何工作的：
f (x) = x ^ 2 + 1 0 (3) 10 f (f (1)) 5 = 1 1 b = 0 - 2 2 f f (a + b) / 0.2 (a - b)
第一次求值定义了一个新函数f(x)，随后的求值演示了对该函数的调用。
要将此功能添加到程序中，您需要做以下事情：
- 类的两个新子类
表达式类,FunctionCallExpression和FunctionDeclareExpression． - 类中添加其他解析器方法
解析器类来识别函数声明和函数调用。 - 类中添加第二个静态映射
表达式类。您将使用这个映射来存储函数的定义。map中的每个条目将存储定义函数时使用的形参名称，以及指向对象的指针表达式。该指针将指向原始函数定义右侧的表达式。 - 添加一个新的虚方法
双精度替换（std::string var，双精度值）到表达式类及其派生类。此方法将对表达式求值，同时将给定值替换为名称为的变量var． - 的
evaluate ()的方法。FunctionCallExpression班级将执行以下步骤： - 它会调用
evaluate ()在函数的参数上生成一个值。 - 它将在存储函数定义的静态映射中查找函数的条目。
- 它会调用
substitute ()在函数定义的函数体上，将原始定义中给出的参数名替换为上面步骤5.1中计算的值。 - 它将返回替换的结果作为其结果。
下面是关于函数定义和函数调用过程应该如何工作的一些进一步的细节。
我们首先输入一个函数定义：
F (x) = x^2 + 1
在这个例子中，F是新函数的名称，x是它的形式参数。表达式x^2+1变成了函数体。
当解析器解析这个表达式时，它将生成一个FunctionDeclareExpression，该表达式存储函数名、形式形参的名称和指向主体表达式的指针。在这个对象上调用evaluate（）将导致它在映射中放置一个新的函数定义。它通过在函数映射中的函数名处放置一个新条目来实现这一点。这个新条目是一对，存储形式形参的名称和指向主体表达式的指针。
接下来，输入一个包含函数调用的表达式：
1 / f (2/10 ^ 2)
当解析器遇到函数调用时，它将为函数调用创建一个FunctionCallExpression对象。对结果表达式求值最终将导致我们在FunctionCallExpression对象上调用evaluate（）。然后Evaluate（）将执行以下操作：
- 它将函数调用的实参求值为double类型，
0.02． - 它查找函数的定义
f。定义说的是形式参数f是x的主体f是x ^ 2 + 1． - 然后调用
substitute ()在…身上f，告诉它更换x与实际参数，0.02。其计算结果为1.0004． evaluate ()返回1.0004结果是。
在完全计算我们输入的表达式后，计算器返回最终结果0.9996。