终结符和非终结符是什么？

Question

我正在阅读Rebol 维基百科页面。

"解析表达式是用解析语言编写的，就像执行语言一样，它是数据交换语言的面向表达式的子语言。与执行语言不同，解析语言使用表示运算符和最重要的非终结符的关键字"

你能解释一下什么是 终结符 和 非终结符 吗？我已经读了很多关于语法的东西，但是不理解它们的含义。这里有另一个链接，其中这些词经常被使用。

- Dmitry Bubnenkov

Answer 1

终结符和非终结符的定义与语法有关，不仅特定于Parse，也适用于一般语法。像这个维基页面或Grune的书中的介绍都解释得很好。但如果你对Red Parse的工作方式感兴趣，渴望简单的例子和指导，我建议你去我们专门的聊天室。

---

“Parsing”有稍微不同的含义，但我更喜欢的是通过正式配方（语法）将线性结构（符号字符串，在广义上）转换为分层结构（推导树），或检查给定字符串是否具有由语法指定的类似树状结构（即“字符串”是否属于“语言”）。

在字符串中的所有符号都是终结符，在一棵树上，树的推导在其上“终止”（即它们是树上的叶节点）。另一方面，非终结符是语法规则中使用的一种抽象形式-它们将终结符和非终结符组合在一起（即它们是树上的节点）。

例如，在以下Parse语法中：

greeting: ['hi | 'hello | 'howdy]
person:   [name surname]
name:     ['john | 'jane]
surname:  ['doe | 'smith]
sentence: [greeting person] 

• greeting、person、name、surname 和 sentence 是非终端符号（因为它们从未实际出现在线性输入序列中，只出现在语法规则中）;
• hi、hello、howdy 以及 john、jane、doe 和 smith 是终端符号（因为解析器不能像对待非终端符号那样将它们 "展开" 成一组终端和非终端符号，因此它通过到达底部而 "终止"）。

>> parse [hi jane doe] sentence
== true
>> parse [howdy john smith] sentence
== true
>> parse [wazzup bubba ?] sentence
== false

正如您所看到的，终端符和非终端符是不相交的集合，即一个符号可以属于其中一个，但不能同时属于两个；此外，在语法规则内，只能在左侧写非终端符。

一种语法可以匹配不同的字符串，而一个字符串也可以被不同的语法匹配（在上面的例子中，它可以是 [greeting name surname]，或者 [exclamation 2 noun]，甚至是 [some noun]，只要定义了exclamation和noun非终结符）。

通常一张图片胜过千言万语：

希望这有所帮助。

- 9214

---

算术表达式中的+、-、*、/、(、)符号是终结符还是非终结符？从AST的角度来看，它们不是叶子节点，但在表达式输入中确实会出现。 - Konstantin Zyubin

抽象语法树（AST）与解析器派生的具体语法树（CST）不是同一回事。在AST中，算术运算符通常是节点，根据优先级规则将操作数和其他运算符分组在一起，而在CST中，它们将作为输入中的标记叶子。请参见此处的示例。 - 9214

它们是语法中的叶子节点。你会有一个规则，像 expr :: expr '+' expr | expr '-' expr。解析 3 + 3，你需要另一条定义 expr 的规则来决定如何处理这两个3，而这条规则本身足以识别 +；不需要额外的规则。 - chepner

Answer 2

把它想象成这样：

一个数字可以是1-9

现在我要告诉你，在一页纸上写下一个数字。

所以你知道你可以写下1、2、3、4、5、6、7、8、9

基本上，非终端符号是“数字”。

而 末端符号 是 1、2、3、4、5、6、7、8、9。

当我告诉你在一页纸上写下一个数字时，你写下了1或2或3或4或5或6或7或8或9。

你没有写下单词“ digit”，你写下了1或2或3等等......

你看到我要表达什么了吗？

我们来试试制定自己的“规则”。

让我们“创建”一个非终端符号，我们称之为“ Olaf ”。

Olaf 可以是一只狗（注意：狗是末端符号）。

Olaf 可以是一只猫（注意：猫是末端符号）。

Olaf 可以是一个数字（注意：数字是非终端符号）。

现在我告诉你，你可以在一页纸上写下一个 Olaf。

那意味着你可以写下“狗”

你也可以写下“猫”

你也可以写下数字，这意味着你可以写下1或2或3等等......

因为非终端符号是代表了数字的符号，因此你不会写下“ digit ”而是写下数字所代表的符号，即1、2、3等......

最后，在“页面”上只写入了末端符号。

还有一件事我必须说，这是你可能在某一天遇到的，基本上当你说“一个 非终端 可以是某个东西”时。

这有一个特殊术语，基本上被称为“生成规则”（也可以称为“生成”）。

例如

Olaf 可以是“狗”

Olaf 可以是“猫”

Olaf 可以是数字

我们在这里得到了3个生成规则，换句话说，我们得到了3个 Olaf 的定义。

编程语言的规范在定义语言的语法时经常使用这些思想。

- AngryJohn