终结符与非终结符

✍ dations ◷ 2025-04-04 11:17:49 #终结符与非终结符

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

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

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

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

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

一种语法的定义由推导规则构成。每个规则规定什么词位可以重写为什么别的词位。这些规则可以用来剖析字符串,也可以用来产生字符串。每个规则有左边和右边。左边有可以被取代的字符串,而右边有可以取代左边的字符串。规则的写法一般为左边 {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> 都是非终结符。

相关

  • 空军部美国空军部(英语:Department of the Air Force,缩写:DAF),是美国国防部下辖的三个军事部门之一。它根据《1947年国家安全法案》,于1947年9月18日成立,下辖美国空军的所有人员。空军
  • UML统一建模语言(英语:Unified Modeling Language,缩写 UML)是非专利的第三代建模和规约语言。UML是一种开放的方法,用于说明、可视化、构建和编写一个正在开发的、面向对象的、软件
  • 陈奇禄陈奇禄(1923年4月27日-2014年10月6日),台湾人类学家,台南将军人。中央研究院院士、吴三连奖基金会及吴三连台湾史料基金会董事长。陈奇禄于大正十二年(1923年)4月27日生于台南州北
  • 华盛顿互惠银行华盛顿互惠公司(Washington Mutual Inc.、近年使用简称:WaMu),是美国一家于1889年至2009年间营运的银行控股公司。成立于1899年,它的最大子公司,华盛顿互惠银行(Washington Mutual
  • 比亚沃维耶扎原始森林比亚沃维耶扎原始森林(白俄罗斯语:Белавеская пушча 波兰语:Puszcza Białowieska)位于布列斯特以北70公里,横跨白俄罗斯及波兰边境,是欧洲现存唯一的原始森林。这
  • 结构与能动性实证主义 · 反实证主义(英语:Antipositivism) 结构主义 · 冲突理论 中层理论 · 形式理论 批判理论 人口 · 团体 · 组织(英语:Organizational theory) · 社会化 社会性
  • 大叶小檗大叶小檗(学名:)为小檗科小檗属的植物,为中国的特有植物。分布在中国大陆的云南等地,生长于海拔100米至2,700米的地区,一般生于山坡、路边或灌丛中,目前尚未由人工引种栽培。
  • 拉菲克·哈里里拉菲克·哈里里(阿拉伯语:رفيق بهاءالدين الحريري‎,拉丁化:Rafik Bahaa Edine Hariri;1944年11月1日-2005年2月14日),黎巴嫩前总理。他从政前是黎巴嫩一位白手
  • 约翰·伯格斯约翰·伯格斯(英语:John William Burgess 1844年8月26日-1931年1月13日)美国政治学家、白人至上主义者,哥伦比亚大学教师,被认为是“该时期最有影响力的政治科学家。”
  • 耳叶紫菀耳叶紫菀(学名:)是菊科紫菀属的植物,是中国的特有植物。分布于中国大陆的贵州、云南、四川等地,生长于海拔1,500米至3,000米的地区,多生于灌从、疏林下或草地,目前尚未由人工引种栽培。银叶紫菀(云南)