我正在攻读我的计算机语言测试,并且我有一些问题 .
我知道常规语法更简单,不能包含歧义,但不能完成编程语言所需的大量任务 . 我也理解无上下文语法允许模糊,但允许编程语言(如回文)所需的一些东西 .
我遇到的问题是通过了解常规语法非终结符可以映射到终端或非终结符后跟终端,或者无上下文非终结符映射到终端和非终结符的任意组合,从而理解我如何得出以上所有内容 .
有人可以帮我把所有这些放在一起吗?
常规语法是右或左线性的,而无上下文语法基本上是终端和非终端的任何组合 . 因此,您可以看到常规语法是无上下文语法的子集 .
所以对于一个回文,例如,形式,
S->ABA A->something B->something
您可以清楚地看到,回文不能用常规语法表达,因为它需要是正确的或左对齐的,因此两侧都不能有非终端 .
由于常规语法是非模糊的,因此对于给定的非终端只有一个生成规则,而在无上下文语法的情况下可以有多个生成规则 .
常用表达
词法分析的基础
代表常规语言
上下文免费语法
解析的基础
代表语言结构
我想你想要考虑的是各种泵浦引理 . 常规语言可以通过有限自动机识别 . 无上下文语言需要堆栈,而上下文敏感语言需要两个堆栈(相当于说它需要一个完整的图灵机 . )
因此,如果我们考虑pumping lemma for regular languages,它本质上说的是,任何常规语言都可以分解为三个部分,x,y和z,其中语言的所有实例都在xy * z中(其中*是Kleene重复,即y的0或更多副本 . )你基本上有一个可以扩展的"nonterminal" .
现在,无上下文语言呢?有一个类似的pumping lemma for context-free languages将语言中的字符串分成五个部分,uvxyz,并且语言的所有实例都在uvixyiz中,因为i≥0 . 现在,你有两个"nonterminals"可以复制或抽取,只要你有相同的号码 .
基本上常规语法是上下文无关语法的子集,但我们不能说Every Context自由语法是一种常规语法 . 主要是无上下文语法是模糊的,常规语法可能是模糊的 .
The difference between regular and context free grammar: (N,Σ,P,S):终端,非终端,产生,起始状态终端符号
●由形式语法定义的语言的基本符号
●abc
非终结符号(或句法变量)
●根据 生产环境 规则由终端符号组替换
●ABC
regular grammar: right or left regular grammar right regular grammar, all rules obey the forms
B→a其中B是N中的非终结符,a是Σ中的终端
B→aC其中B和C在N中,a在Σ中
B→ε其中B在N中,ε表示空字符串,即长度为0的字符串
left regular grammar, all rules obey the forms
A→a其中A是N中的非终结符,a是Σ中的终结符
A→Ba其中A和B在N中,a在Σ中
A→ε其中A在N中,ε是空字符串
context free grammar (CFG)
○形式语法,其中每个 生产环境 规则的形式为V→w
○V是单个非终结符号
○w是一串终端和/或非终端(w可以为空)
如果所有 生产环境 规则都具有以下形式,则语法是无上下文的:A(即,规则的左侧只能是单个变量;右侧不受限制,可以是任何序列的终端和变量) . 我们可以将语法定义为4元组,其中V是有限集(变量),_是有限集(终端),S是起始变量,R是有限的规则集,每个规则都是映射V常规语法是右或左线性的,而无上下文语法基本上是终端和非终端的任何组合 . 因此我们可以说常规语法是无上下文语法的一个子集 . 在这些属性之后,我们可以说Context Free Languages集也包含Regular Languages set
常规语法: - 包含如下 生产环境 的语法是RG:
V->TV or VT V->T
其中V =变量,T =终端
RG可以是Left Linear Grammar或Right Liner Grammar,但不是Middle Linear Grammar .
我们知道所有RG都是线性语法,但只有左线性或右线性语法是RG .
常规语法可能不明确 .
S->aA|aB A->a B->a
模糊语法: - 对于字符串x,它们存在多个LMD或超过RMD或多于一个解析树或一个LMD和一个RMD,但两者都产生不同的解析树 .
S S / \ / \ a A a B \ \ a a
这个语法是模棱两可的语法因为两个解析树 .
CFG: - 一个语法说如果其 生产环境 形式为CFG:
V->@ where @ belongs to (V+T)*
DCFL: - 我们知道所有DCFL都是LL(1)语法,所有LL(1)都是LR(1)所以它永远不会模糊不清 . 所以DCFG永远不会含糊不清 .
我们也知道所有RL都是DCFL,因此RL永远不会模棱两可 . 请注意,RG可能不明确,但RL不是 .
CFL:CFl可能或可能不含糊 .
注意:RL从来就不是含糊不清的 .
一个普通的语法永远不会模糊,因为它要么是线性的,要么是线性的,所以我们不能为常规语法做出两个决策树,所以它总是明确的 . 但是,除了常规语法以外,它们都可能是也可能不是常规的
8 回答
常规语法是右或左线性的,而无上下文语法基本上是终端和非终端的任何组合 . 因此,您可以看到常规语法是无上下文语法的子集 .
所以对于一个回文,例如,形式,
您可以清楚地看到,回文不能用常规语法表达,因为它需要是正确的或左对齐的,因此两侧都不能有非终端 .
由于常规语法是非模糊的,因此对于给定的非终端只有一个生成规则,而在无上下文语法的情况下可以有多个生成规则 .
常用表达
词法分析的基础
代表常规语言
上下文免费语法
解析的基础
代表语言结构
我想你想要考虑的是各种泵浦引理 . 常规语言可以通过有限自动机识别 . 无上下文语言需要堆栈,而上下文敏感语言需要两个堆栈(相当于说它需要一个完整的图灵机 . )
因此,如果我们考虑pumping lemma for regular languages,它本质上说的是,任何常规语言都可以分解为三个部分,x,y和z,其中语言的所有实例都在xy * z中(其中*是Kleene重复,即y的0或更多副本 . )你基本上有一个可以扩展的"nonterminal" .
现在,无上下文语言呢?有一个类似的pumping lemma for context-free languages将语言中的字符串分成五个部分,uvxyz,并且语言的所有实例都在uvixyiz中,因为i≥0 . 现在,你有两个"nonterminals"可以复制或抽取,只要你有相同的号码 .
基本上常规语法是上下文无关语法的子集,但我们不能说Every Context自由语法是一种常规语法 . 主要是无上下文语法是模糊的,常规语法可能是模糊的 .
The difference between regular and context free grammar: (N,Σ,P,S):终端,非终端,产生,起始状态终端符号
●由形式语法定义的语言的基本符号
●abc
非终结符号(或句法变量)
●根据 生产环境 规则由终端符号组替换
●ABC
regular grammar: right or left regular grammar right regular grammar, all rules obey the forms
B→a其中B是N中的非终结符,a是Σ中的终端
B→aC其中B和C在N中,a在Σ中
B→ε其中B在N中,ε表示空字符串,即长度为0的字符串
left regular grammar, all rules obey the forms
A→a其中A是N中的非终结符,a是Σ中的终结符
A→Ba其中A和B在N中,a在Σ中
A→ε其中A在N中,ε是空字符串
context free grammar (CFG)
○形式语法,其中每个 生产环境 规则的形式为V→w
○V是单个非终结符号
○w是一串终端和/或非终端(w可以为空)
如果所有 生产环境 规则都具有以下形式,则语法是无上下文的:A(即,规则的左侧只能是单个变量;右侧不受限制,可以是任何序列的终端和变量) . 我们可以将语法定义为4元组,其中V是有限集(变量),_是有限集(终端),S是起始变量,R是有限的规则集,每个规则都是映射V
常规语法是右或左线性的,而无上下文语法基本上是终端和非终端的任何组合 . 因此我们可以说常规语法是无上下文语法的一个子集 . 在这些属性之后,我们可以说Context Free Languages集也包含Regular Languages set
常规语法: - 包含如下 生产环境 的语法是RG:
其中V =变量,T =终端
RG可以是Left Linear Grammar或Right Liner Grammar,但不是Middle Linear Grammar .
我们知道所有RG都是线性语法,但只有左线性或右线性语法是RG .
常规语法可能不明确 .
模糊语法: - 对于字符串x,它们存在多个LMD或超过RMD或多于一个解析树或一个LMD和一个RMD,但两者都产生不同的解析树 .
这个语法是模棱两可的语法因为两个解析树 .
CFG: - 一个语法说如果其 生产环境 形式为CFG:
DCFL: - 我们知道所有DCFL都是LL(1)语法,所有LL(1)都是LR(1)所以它永远不会模糊不清 . 所以DCFG永远不会含糊不清 .
我们也知道所有RL都是DCFL,因此RL永远不会模棱两可 . 请注意,RG可能不明确,但RL不是 .
CFL:CFl可能或可能不含糊 .
注意:RL从来就不是含糊不清的 .
一个普通的语法永远不会模糊,因为它要么是线性的,要么是线性的,所以我们不能为常规语法做出两个决策树,所以它总是明确的 . 但是,除了常规语法以外,它们都可能是也可能不是常规的