实验一：最左推导¶

背景¶

在课堂上，我们学习了上下文无关语言的最左推导和语法分析树，以及正规表达式的定义。在本实验中，大家将实现一个最左推导过程，并得到一个上下文无关语言的串的语法分析树。

根据正规表达式的定义可知，Σ上的（不含变量的）正规表达式集合R是一种上下文无关语言，将R中的每个中缀表达式转换为波兰式以去除复杂的括号（将正规表达式中的连接视为省略了运算符-的运算），得到的语言R'仍是一种上下文无关语言，我们可以写出其上下文无关文法如下：

G'=({S}, {+, -, *, ε}∪Σ, P, S)

其中产生式集合P为：

S → +SS

S → -SS

S → *S

∀a∈{ε}∪Σ, S → a （注意此处的ε应当是一个常量而不是空串）

根据这一无二义的文法，我们可以方便地进行最左推导，并根据最左推导得到语法分析树。

任务¶

在expression-parser/to_polish.h中已经实现了正规表达式转化成了波兰式，你需要将homework/lib_char.h中的

// #include "expression-parser/parser.h"

取消注释，然后完成homework/expression-parser/parser.h中的TODO，解析传入的R'中的串并返回语法分析树，使项目通过CI/CD。

提示¶

判断下一步最左推导使用哪个产生式时，可以根据剩余串的首位来确定：
- 若接下来的串以+开头，则下一步必使用S → +SS以匹配这个+
- 若接下来的串以-开头，则下一步必使用S → -SS以匹配这个-
- 若接下来的串以*开头，则下一步必使用S → *S以匹配这个*

为了支持更多字符类型，请尽量避免使用 char 类型的变量和常量，而应使用 T 类型的变量和consts.h中声明的常量，泛型的文法直观表示如下：

S → regex_union<T> S S

S → regex_concatenation<T> S S

S → regex_closure<T> S

S → epsilon<T>

∀a∈Σ, S → a （Σ由类型为T且不等于regex_union<T>， regex_concatenation<T>， regex_closure<T>，epsilon<T>的所有符号组成）

以下代码可能有助于减少你打字的量：

typedef typename ParseTree<T>::node Node;
auto Variable = Node::LabelType::Variable;
auto Terminal = Node::LabelType::Terminal;
auto Epsilon = Node::LabelType::Epsilon;
T S = T('S');

建议使用std::make_shared和语法分析树节点的构造函数（node(LabelType label_type, T label_value, std::shared_ptr<node> parent)）来创建新的语法分析树节点，例如
```
pt.root = std::make_shared<Node>(Variable, S, nullptr);
```

思考题目¶

试写出Σ上的正规表达式集合R的无二义上下文无关文法G。

作者：张英奇 (92.0%), 张英奇 (8.0%)

实验一：最左推导¶

背景¶

任务¶

提示¶

思考题目¶

评论