1.上下文无关文法定义
文法:它描述语言语法结构的一组形式规则。
上下文无关文法:它定义的语法范畴(或语法单位)是完全独立于这种范畴可能出现的环境。例如,在程序设计语言中,当碰到一个算术表达式时,我们完全可以“就事论事”处理,而不必考虑它所处的上下文。然而,在自然语言中,随便一个词,甚至一个字的意思在不同的上下文中都有可能有不同的意思。幸运的是,当今的程序设计语言都是上下文无关的
。
好像有点抽象,来个例子
”→”表示箭头左边的由箭头右边的定义
把He gave me a book与上述规则进行对照,看其中的语法范畴是否处于适当的位置,如果你了解英语的话,你应该可以确认这是一个正确的句子。做科学研究都有一个过程从现象得出一般结论,再用实验验证这个一般性结论。有了这个语法规则我们可以造出很多这种英文句子(简单假设,英文语法远比这复杂)。如果我们要造一个句子表达我们自己的意思,利用这个规则,很容易。
根据上述规则,句子无需考虑上下文,就可以判断正确性(符合<主语><谓语><间接宾语><直接宾语>的规则)。
其中,He,me等为终结符号,<主语>、<谓语>、<间接宾语>等为非终结符号。
这个文法最终要定义<句子>语法结构,所以<句子>在这里称为开始符号;<谓语>→<动词>这种书写形式称之为产生式。
归纳一下:上下文无关语法G包括四个部分:一组终结符号,一组非终结符号,一个开始符号,以及一组产生式。
说明一下:终结符号是组成语言不可再分的基本符号,在程序语言中就是保留字、标识符、常数等;非终结符号是一个给定的语法概念,是一个类(或集合)记号,而是不是某个个体记号;开始符号是一个特殊的非终结符号,是语言中我们最终想得到的字符串(在程序语言中,我们最终感兴趣的是“程序”这个语法范畴,其他的语法都是构造“程序”的基石);产生式(也称产生规则或者简称规则)是语法范畴的一种书写规则。
你想嘛,gave这个单词,拆分为一个个字母,就不再是gave了,没有什么特别的含义;而非终结符号就是诸如gave的动词的集合。
额,有个细节好像忽略了,产生式的形式:
A→α
箭头左边是一个非终结符,称之为产生式的左部,箭头右边称之为右部。
A是一个非终结符,α是由 非终结符号和终结符号的并集 的闭包 中的元素 组成的符号串
形式化的上下文无关文法定义:
一个四元数组G=(VN,VT,S,P)
VN:非空有限的非终结符集合
VT:非空有限的终结符集
S:开始符号
P:产生式集合
其中,VN∩VT=∅,S∈VN
P中产生式一般形式为A→α|β,其中A∈VN,α,β∈(VN∪VT)*
通常用大写字母表示非终结符,小写字母表示终结符,α、β、γ等代表由 终结符和非终结符号的并集的闭包 中的元素 组成的符号串。
例如:E→i|EAE A→+|*
是上下文无关语法,E、A是非终结符,E是开始符,而i,+和*是终结符
2.用上下文无关语法定义一个语言
一个上下文无关语法如何定义一个语言呢,主要思想是从文法的开始符号出发,反复连续使用产生式,对非终结符进行替换和展开。
例如:
算术表达式的定义可以写为:
E→i
E→E+E
E→E*E
E→(E)
E代表算术表达式,i代表变量。这四个产生式的后三个是递归的。
我们可以定义如下文法G
E→E+E|E*E|(E)|i
开始符号为E,从E出发E=>(E)=>(E+E)=>(E*E+E)=>(i*E+E)=>(i*i+E)=>(i*i+i)
符号”=>”表示仅推导一步
我们定义αAβ=>αγβ为αAβ直接推导出αγβ,仅当A→γ是一个产生式,且α,β∈(VN∪VT)* 。
如果a1=>a2=>a3=>…=>an,我们称这个序列是从a1到an的一个推导。若存在一个从a1到an的推导,则称之为a1可推导出an。用a1=>an表示从a1出发经过零步或若干步,可推导出an。
假设G是一个文法,S是它的开始符号,如果S=>α则称α是一个句型。仅含终结符号的句型是句子。文法G所产生的句子全体是一个语言记为L(G)。
L(G)={α|S+=>α&α∈VT*}
例如:文法G1:
S→bA
A→aA|a
从符号S出发我们可以推出,S=>bA=>ba
S=>bA=>baA=>baa
.
.
.
S=>bA=>baA=>…=>ba…a
归纳得出所有以b开头后头跟一个或者多个a的字符串L(G1)={ban|n>=1}
转载于:https://www.cnblogs.com/GaussianPrince/p/6158943.html
今天的文章上下文无关文法_计算机文法推导「建议收藏」分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/73966.html