常规语法与上下文无关语法

StackOverflow https://stackoverflow.com/questions/559763

题

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

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

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

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

有帮助吗？

解决方案

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

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

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结果 正规文法是右手或左线性，而上下文无关文法是基本上终端和非终端的任何组合。因此，我们可以说，正规文法是上下文无关文法的一个子集。 这些特性后，我们可以说，上下文无关语言设置还包含设置常规语言

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

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

不隶属于 StackOverflow
scroll top