终结符和非终结符的定义与语法有关,不仅特定于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
非终结符)。
通常一张图片胜过千言万语:
希望这有所帮助。
把它想象成这样:
一个数字可以是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 的定义。
编程语言的规范在定义语言的语法时经常使用这些思想。
expr :: expr '+' expr | expr '-' expr
。解析3 + 3
,你需要另一条定义expr
的规则来决定如何处理这两个3,而这条规则本身足以识别+
;不需要额外的规则。 - chepner