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

Question

我正在阅读 Rebol Wikipedia page .

"Parse expressions are written in the parse dialect, which, like the do dialect, is an expression-oriented sublanguage of the data exchange dialect. Unlike the do dialect, the parse dialect uses keywords representing operators and the most important nonterminals"

你能解释一下什么是终端和非终端吗？我读了很多关于语法的知识，但不明白它们的意思。这是另一个link这个词经常被使用的地方。

Answer 1

终结符和非终结符的定义不是特定于 Parse 的，而是与一般语法有关。像this之类的东西维基页面或简介 Grune's book很好地解释了它们。 OTOH，如果您对 Red Parse 的工作原理感兴趣并渴望简单的示例和指导，我建议您访问我们的专用 chat room .

<小时/>

“解析”的含义略有不同，但我更喜欢的是通过正式配方(语法)将线性结构(广义上的符号字符串)转换为层次结构(推导树)，或者检查是否给定的字符串具有由语法指定的树状结构(即，如果“字符串”属于“语言”)。

字符串中的所有符号都是终结符，从某种意义上说，树派生在它们上“终止”(即它们是树中的叶子)。反过来，非终结符是语法规则中使用的一种抽象形式 - 它们将终结符和非终结符分组在一起(即它们是树中的节点)。

例如，在以下 Parse 语法中:

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

• 问候语、人、姓名、姓氏和句子是非终结符(因为它们实际上从未出现在线性输入序列中，仅出现在语法规则中)；
• hi、hello、howdy 和 john、jane、doe 和 smith 是终端(因为解析器无法像处理非终端那样将它们“扩展”为一组终端和非终端，因此它通过到达底部)。

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

正如你所看到的，终结符和非终结符是不相交的集合，即一个符号可以在其中一个集合中，但不能同时在两个集合中；而且，在语法规则中，只有非终结符可以写在左侧。

一种语法可以匹配不同的字符串，一个字符串也可以匹配不同的语法(在上面的例子中，可以是[问候语姓名]，或者[感叹号2名词] ，甚至是[some noun]，前提是定义了感叹号和名词非终结符)。

而且，像往常一样，一张图片胜过一千个文字:

希望有帮助。