我正在为我的学习 计算语言 测试,有一个想法我无法理解。

我明白 常规语法 更简单并且不能包含歧义,但不能完成编程语言所需的许多任务。我也明白了 上下文无关语法 允许歧义,但允许一些编程语言必需的东西(例如回文)。

我遇到的困难是理解如何通过知道以下内容来得出上述所有内容 正则语法非终结符 可以映射到一个终结符或一个非终结符,后跟一个终结符,或者上下文无关的非终结符映射到终结符和非终结符的任意组合。

有人可以帮我把所有这些放在一起吗?

有帮助吗?

解决方案

普通语法或者是向右或向左线性,而上下文无关文法是基本上终端和非终端的任何组合。因此,你可以看到,常规语法是上下文无关文法的一个子集

因此,对于例如回文,具有以下形式,

S->ABA
A->something
B->something

可以清楚地看到,回文不能在常规语法因为它需要是右边或左边线性,因此不能有在两侧的非末端表达。

由于常规语法是无歧义的,仅存在一个对于给定的非终端的产生式规则,而可以有多于一个的上下文无关文法的情况下

其他提示

我觉得你要考虑是各种抽lemmata什么。有规律的语言可以被有限自动机识别。甲上下文无关语言需要一个栈,和上下文敏感的语言需要两个叠层(其等同于说这需要一个完整的图灵机。)

所以,如果我们考虑抽引理正规语言说话算数,实质上是,任何规则语言可以被分解成三个部分, X ýž,其中该语言的所有实例都在 XY * Z (其中,*是克林重复,即,0或更多个拷贝的ý)。您基本上有一个 “非末端” 可被扩展。

现在,怎么样上下文无关语言?有打破串在语言分为五个类似的抽引理上下文无关语言份, uvxyz ,并且其中该语言的所有实例都在 UV XY ž,其中i≥现在0,则必须 2 “非终结点”可被复制,或泵,只要具有相同数量的

常规语法和上下文无关语法的区别:(N、Σ、P、S):终端、非终端、产生式、起始状态 终端符号

● 由形式语法定义的语言的基本符号

●ABC

非终结符号(或语法变量)

● 按生产规则用多组端子符号代替

●ABC

常规语法:右或左常规语法右法语法,所有规则遵守表格

  1. B → a,其中 B 是 N 中的非终结符,a 是 Σ 中的终结符
  2. B → aC 其中 B 和 C 在 N 中,a 在 Σ 中
  3. B → ε 其中 B 在 N 中,ε 表示空串,即长度为0的字符串

离开常规语法,所有规则都遵循形式

  1. A → a,其中 A 是 N 中的非终结符,a 是 Σ 中的终结符
  2. A → Ba 其中 A 和 B 在 N 中,a 在 Σ 中
  3. A → ε 其中 A 在 N 中,ε 是空字符串

上下文无关语法(CFG)

○ 形式语法,其中每个产生式规则的形式为 V → w

○ V 是单个非终结符

○ w 是终结符和/或非终结符的字符串(w 可以为空)

常用表达

  • 词法分析的基础
  • 代表常规语言

上下文无关语法

  • 解析基础
  • 表示语言结构

enter image description here

普通语法: - 的含有生产如下语法是RG:

V->TV or VT
V->T

其中V =可变的,并且T =终端

RG可以留线性语法或右班轮语法,但没有中间线性语法。

正如我们所知道的所有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永远固有歧义

一个语法是上下文无关,如果所有的生产规则具有以下形式:A(即,规则的左边只能是单个可变;右侧是不受限制的,并且可以是终端和变量的任意序列) 。 我们可以定义一个语法作为4元组,其中V是一个有限集(变量),_是一个有限集(端子),S是开始可变,且R是一个有限的一组规则,其中每一个是一个映射V结果 正规文法是右手或左线性,而上下文无关文法是基本上终端和非终端的任何组合。因此,我们可以说,正规文法是上下文无关文法的一个子集。 这些特性后,我们可以说,上下文无关语言设置还包含设置常规语言

基本上正规文法是上下文无关文法的一个子集,但我们不能说每一个上下文无关文法是正规的语法。主要上下文文法是不明确的和定期的语法可以是不明确的。

常规语法是绝不含糊,因为它要么是左线,右线,所以我们不能让正规语法两个决策树,因此它总是比正规文法都是可能会或可能不会经常

scroll top