系列文章戳这里👇
什么是上下文无关文法、最左推导和最右推导如何判断二义文法及消除文法二义性何时需要消除左递归什么是句柄、什么是自上而下、自下而上分析什么是LL(1)、LR(0)、LR(1)文法、LR分析表LR(0)、SLR(1)、LR(1)、LALR(1)文法之间的关系编译原理第三章习题词法分析、构建DFA、上下文无关文法、LL(1)分析、提取正规式证明LL(1)、SLR(1)、LALR(1)文法编译原理-上下文无关文法、最左推导和最右推导
系列文章戳这里👇什么是上下文有关文法?一、上下文无关文法二、上下文相关文法为什么需要上下文无关文法?什么是最左推导和最右推导?举个例子什么是上下文有关文法?
一、上下文无关文法
上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符,比如:
S→aSbS→abS → aSb\\ S → ab S→aSbS→ab
这个文法有两个产生式,每个产生式左边只有一个非终结符 SSS,这就是上下文无关文法,因为你只要找到符合产生式右边的串,就可以把它归约为对应的非终结符。
二、上下文相关文法
比如:
aSb→aaSbbS→abaSb →aaSbb\\ S →ab aSb→aaSbbS→ab
这就是上下文有关文法,因为它的第一个产生式左边有不止一个符号,所以你在匹配这个产生式中的SSS的时候必需确保这个SSS有正确的“上下文”,也就是左边的aaa和右边的bbb,所以叫上下文相关文法。
为什么需要上下文无关文法?
上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法;实际上,几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LRLRLR 分析器和LLLLLL分析器。
什么是最左推导和最右推导?
最左推导:每一步替换最左边的非终结符
最右推导:每一步替换最右边的非终结符
最右推导称为规范推导。最右推导对应于最左规约(规范规约)
举个例子
文法:
S→ABA→a∣tB→+CDC→aD→aS→AB\\ A→a|t\\ B→+CD\\ C→a\\ D→a S→ABA→a∣tB→+CDC→aD→a
最右推导:
S→AB→A+CD→A+Ca→A+aa→a+aaS→AB→A+CD→A+Ca→A+aa→a+aaS→AB→A+CD→A+Ca→A+aa→a+aa
最左推导:
S→AB→aB→a+CD→a+aD→a+aaS→AB→aB→a+CD→a+aD→a+aaS→AB→aB→a+CD→a+aD→a+aa