编译原理单词的文法

Ⅰ 编译原理：LL, LR 文法浅析

在编译原理的学习中，文法概念常令人困惑，尤其是LL(k)、SLR(k)、LALR(k)、LR(k)等。首先，澄清一下，context-free grammar（上下文无关文法）并不等同于无二义性文法。上下文无关文法允许任意替换，每个非终结符号下的产生式是等价的，即使在解析过程中，主语或宾语的改变也不会影响合法性。二义性则是文法内部的一种特性。

关键的疑惑在于文法类型的相互关系。LL和LR算法之间的差异主要体现在解析过程的策略上：LL算法（类似于先序遍历）在线性推进输入时，通过有限的前瞻预测子节点的父节点，而LR（如后序遍历）则在完全看到子节点后决定插入父节点。LR(k)文法在前瞻相同的情况下，由于看完整个子结构，优势更明显。

LL(0)和LR(0)分别代表在解析初期不依赖前瞻信息和仅根据当前输入的子结构做出决策，LL(0)由于缺乏前瞻无实用价值，而LR(0)虽然简单，却能处理更多文法。SLR(0)和LR(0)的不同在于前瞻字符的处理方式，理论上SLR(0)等于LR(0)。然而，判断文法是否无二义性是一个复杂问题，LL和LR算法可以在无冲突的文法中保证线性复杂度，但并非所有无二义文法都能被它们处理。

GLR解析器可以处理任意CFG，但不直接处理文法的二义性问题，它通过全面遍历来生成可能的抽象语法树。工业界中的编译器在实际应用中可能需要结合LL和LR的特性，如LR处理运算符优先级，LL优化错误报告，通过层次化设计来平衡性能和复杂性。在编写自定义解析器时，需要通过测试来确保正确性，如与已有的解析器生成的AST序列进行对比。

Ⅱ 编译原理的LL（1）文法是什么意思

1.文法不含左递归，没有公共左因子
2.对于文法中的每个非终结符A的产生式的候选首符集两两不相交。
3.对于文法中的每个非终结符A，它存在某个候选首符集包括ε，则FIRST（A）∩FOLLOW（A）=空
满足以上条件的文法为LL（1）文法

Ⅲ 编译原理文法定型规则

编译原理中的文法定型规则是指将任意上下文无关文法（Context-Free Grammar, CFG）转化为某个特定形式的上下文无关文法的规则。这个特定形式的上下文无关文法通常是Chomsky范式或Greibach范式。
以下是文法定型规则的具体步骤：
1. 消除文法中的ε产生式（epsilon-proction），即产生空串的产生式。
2. 消除文法中的单一产生式（unit-proction），即右侧只有一个非终结符的产生式。
3. 消除文法中的左递归产生式（left-recursive proction）。
4. 将文法转化为无二义性的文法。
上述步骤的具体实现方法如下：
1. 消除文法中的ε产生式：
1. 对于所有含有ε产生式的非终结符，将其ε产生式删除。
2. 对于所有产生式右侧含有已删除非终结符的产生式，将其右侧的已删除非终结符替换为ε。
3. 重复执行上述步骤，直到所有含有ε的产生式都被消除为止。
2. 消除文法中的单一产生式：
1. 对于所有单一产生式A → B，将其删除。
2. 对于所有产生式右侧含有被删除产生式的非终结符的产生式，将其替换为被删除产生式的右侧符号B。
3. 重复执行上述步骤，直到所有单一产生式都被消除为止。
3. 消除文法中的左递归产生式：
1. 对于每个非终结符A，将所有形如A → Aα的产生式改为A → β1A'、A' → β2A' | ε的形式。
2. 其中，β1是所有右侧不含有A的A产生式的右侧符号串，β2是所有右侧含有A的A产生式的右侧符号串，α是所有产生式右侧不含有A的符号串。
3. 重复执行上述步骤，直到所有左递归产生式都被消除为止。
4. 将文法转化为无二义性的文法：
1. 消除文法中的二义性产生式，即产生式右侧存在两个或以上的不同符号串。
2. 引入新的非终结符，将二义性产生式拆分为多个不同的产生式。
3. 对于所有产生式右侧含有多个符号的产生式，使用括号或其他符号进行明确区分。
4. 重复执行上述步骤，直到文法不存在二义性为止。
以上是文法定型规则的具体步骤和实现方法。通过执行这些步骤，可以将任意上下文无关文法转化为某个特定形式的上下文无关文法，从而方便进行语法分析和编译。

Ⅳ 什么是文法(编译原理)

【定义】

文法G定义为四元组（VN，VT，P，S）

其中 VN   ：非终结符号(即语法变量)集

        VT   ： 终结符号集

                   VN∩VT =Φ，令V= VN∪VT，V称为文法G的字母表或字汇表。

        P  ：产生式(α→β)集

        S ：开始符号，且S∈VN ，S至少要在一条规则的左部出现。

【约定】

一般地，文法G的 四元组 不用全部给出 ，而只将产生式写出。

约定：

    （1）第一条产生式的左部是开始符号

    （2）用尖括号括起来的（或 大写字母 ）是非终结符号

    （3）不用尖括号括起来（或 小写字母 ）是终结符号

    （4）还有一种习惯写法，即 G[S] ，其中 S 是 开始符号 。

【举例】

    例: G=（VN，VT，P，S）

           其中  VN={S}，

           VT ={0，1}，

           P={S→0S1，S→01}

           S是开始符号

Ⅳ 编译原理中文法二义性问题

二义性文法

【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。

二义性文法会引起歧义，应尽量避免之！

E E

E + E E * E

i E * E E + E i

i i i i

都可以表示i+i*i

所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二义性。

文法二义性的消除：

【方法1】不改变文法的原有规则,加进一些非形式规定。

加进运算符的优先顺序和结合规则对G(E)，规定*优于+，*和+服从左结合

【方法2】构造一个等价的无二义性文法，将排除 二义性的规则合并到文法中

G(E) -> G´(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;

Ⅵ 编译原理的文法

“文法是以有穷的集合刻画无穷的集合的一个工具”，有穷的集合应该是已经出现的，人们普遍接受的词、词组或句子，无穷的集合就是有穷的集合的词、词组或句子，创造新的集合过程和结果，有待进一步认识接受。
我们的文法规定内涵是已经明确定义的和正在定义（声明）的内容。反映到计算机语言程序中就是编程时已经定义的和正在定义（声明）的字符或字符串。文法可以以表的形式，或词典形式存放。

Ⅶ 编译原理中，形式语言里怎么区分2型文法与3型文法

二型文法，也称为上下文无关文法，其产生式的特点是左部仅包含一个非终结符。例如，给定的文法可以表示为：S->Ac, S->Sc, A->ab, A->aAb。这些产生式定义了如何从初始符号S推导出字符串，其中A, S是文法中的非终结符，a, b, c是终结符。

三型文法则更具体地分为几种类型：左线形文法、右线形文法和正规文法。左线形文法的产生式右部要么为空，要么只有一个非终结符且位于最左端，如S->aS, B->cB。右线形文法则相反，其产生式右部要么为空，要么只有一个非终结符且位于最右端，如B->cB, A->Bb。正规文法是右线形文法的一个子集，其产生式右部只能是空串、一个终结符或一个终结符后接一个非终结符，如S->aS, A->bA, B->cB, B->c, A->Bb。

在文法分类中，所有的三型文法都属于二型文法。这意味着所有三型文法的产生式结构都满足二型文法的定义。因此，二型文法的范围比三型文法广，涵盖了所有的三型文法以及更多类型的产生式。通过理解这两种文法的区别，可以更好地分析和设计形式语言。

值得注意的是，二型文法允许产生式中非终结符出现在右部的任意位置，这为定义更复杂的语言提供了灵活性。而三型文法则通过限制产生式右部的形式，使得生成的语言更加受限，适用于定义更简单、更直接的字符串。

在实际应用中，理解二型文法和三型文法的区别有助于构建解析器和编译器，尤其是在处理自然语言处理和编程语言编译时，这些文法类型对于语法分析至关重要。

总之，二型文法与三型文法之间的主要差异在于产生式右部非终结符的位置和数量的限制，这直接关系到生成语言的复杂度和灵活性。通过掌握这些文法类型，可以更有效地构建和优化形式语言。

Ⅷ 编译原理简单文法归约计算

编译原理中的语法和文法是不一样的，但却融会贯通。
在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
形式语言，这种理论对计算机科学有着深刻的影响，特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。
多数程序设计语言的单词的语法都能用正规文法或3型文法（3型文法G=(VN，VT，P，S)的P中的规则有两种形式：一种是前面定义的形式，即：A→aB或A→a其中A，B∈VN ，a∈VT*，另一种形式是：A→Ba或A→a，前者称为右线性文法，后者称为左线性文法。正规文法所描述的是VT*上的正规集）来描述。
四个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。

Ⅸ 【编译原理】第二章：语言和文法

上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。

约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：

产生式

可以简写为：

如上例中，

可以简写为：

给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。

如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。

推导的反过程称为 归约 。

如果 ，则称 是 的一个 句型（sentential form ）。

由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：

例
文法

表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。

并、连接、幂、克林闭包、正闭包。
如上例表示为：

中必须包含一个 非终结符 。

产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。

上下文有关文法不包含空产生式（ ）。

产生式的一般形式：
即产生式左边都是非终结符。

右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。

例：（右线性文法）

以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：

正则文法能描述程序设计语言中的多数单词。

正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。

根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。

给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。

直接短语一定是某产生式的右部，但反之不一定。

如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。

二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。