终结符与非终结符

✍ dations ◷ 2025-04-02 13:13:08 #终结符与非终结符

终结符和非终结符在计算机科学和语言学的领域是用来指定推导规则的元素。在某个形式语法之中,终结符和非终结符是两个不交的集合。

是一个形式语言的基本符号。就是说,它们能在一个形式语法的推导规则的输入或输出字符串存在,而且它们不能被分解成更小的单位。确切地说,一个语法的规则不能改变终结符。例如说,下面的语法有两个规则:

在这种语法之中,是一个终结符,因为没有规则可以把变成别的符号。不过,有两个规则可以把变成别的符号,所以是非终结符。一个形式语法所推导的形式语言必须完全由终结符构成。

非终结符是可以被取代的符号。一个形式文法中必须有一个起始符号;这个起始符号属于非终结符的集合。

在上下文无关文法中,每个推导规则的左边只能有一个非终结符而不能有两个以上的非终结符或终结符。并非所有的语言都可以被上下文无关文法产生。

一种语法的定义由推导规则构成。每个规则规定什么词位可以重写为什么别的词位。这些规则可以用来剖析字符串,也可以用来产生字符串。每个规则有左边和右边。左边有可以被取代的字符串,而右边有可以取代左边的字符串。规则的写法一般为左边 {displaystyle rightarrow } 右边。比如,z0 → z1 这个规则规定 z0 可以重写为 z1。左边为一个非终结符,但是右边不一定是个终结符。

下面的形式文法代表一个整数。整数可能是有符号,就是说,可能是负数。下面使用巴科斯范式的变种来表示:

<integer> ::=  <digit> {<digit>}<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

在这个例子之中,符号 (-,0,1,2,3,4,5,6,7,8,9) 都是终结符,而 <digit> 和 <integer> 都是非终结符。

相关

  • 瑞士安乐死议题瑞士是全世界第一个、也是少数可合法实施被动安乐死的国家。瑞士在1941年通过安乐死相关法案,合法化协助自杀;协助方式局限于为被动(例如除去病人的维生系统或让病人停止服药)而
  • 唐桥唐桥(?-?),京都人,正二位権中纳言高松公祐的长女。1804年以乐宫乔子女王的小上腊入主西之丸大奥。徳川家齐七女峰姫出嫁时作为陪嫁的上腊御年寄。最后回到京都。
  • 火山气体火山气体包括从活跃的(或者有时从休眠的)火山释放出的多种挥发物质的总称。这些物质包括被困在火山岩孔穴(泡)中的气体,在岩浆和熔岩里溶解或游离气体,或直接从熔岩散发的气体,或间
  • 同一健康同一健康(英语:One health),又名唯一健康、一体化健康、防疫一体,是涉及人类、动物、环境卫生保健各个方面的一种跨学科跨地域(国家、地区、全球)协作和交流的新策略,致力于共同促进
  • 牛虻 (电影)电影《牛虻》(英语:The Gadfly,俄语:Овод),是一部根据小说《牛虻》的电影,由前苏联拍摄。因政治原因,本片部分内容在中国上映期间曾有删减。五十年代,对于在中国内地的中国人来
  • 计算机伦理计算机伦理(Computer ethics)是有关电脑专业人士在专业及社会相关事务上,如何进行决策的伦理学,属于实用哲学(英语:practical philosophy)。 南乔治亚大学数学及电脑系的教授 Marga
  • 微笑曲线微笑曲线(Smile Curve)是1992年时,当时的宏碁电脑董事长施振荣在《再造宏碁:开创、成长与挑战》一书中所提出的企业竞争战略。微笑曲线分成左、中、右三段,左段为技术、专利,中段
  • 光明余氏宗祠光明余氏宗祠,位于中国福建省将乐县光明乡光明村,为一个省级文物保护单位,类型为古建筑,为第七批福建省文物保护单位,公布时间为2009年11月16日。光明余氏宗祠的历史年代为清。
  • 时代错误遗物时代错误遗物(英文:Out-of-place artifacts,简称OOPARTS)又称欧帕兹,是由美国博物学家伊万·桑德森(英语:Ivan Sanderson)提出,用于史学、人类学、考古学、主流科学和禁忌人类学上,主要针对近些年来从古老地层中掘出的、已如动植物化石般的疑似人造物品,意即在不该出现的地方出土的加工物。时代错误遗物被年轻地球创造论、外星生物创造论、古代太空人的支持者当成证据,反对者则视之为伪科学。以下是常用的定义:
  • 树林镇南宫坐标:.mw-parser-output .geo-default,.mw-parser-output .geo-dms,.mw-parser-output .geo-dec{display:inline}.mw-parser-output .geo-nondefault,.mw-parser-output .geo-multi-punct{display:none}.mw-parser-output .longitude,.mw-parser-output .latitude{white-space:n