编译原理怎么压缩文法

❶ 一个关于编译原理中LR(1)文法的问题

当·到达最后的时候就可以规约了，当·没到最后就移入，实际中句子的下一个字符是什么是确定的，比如在状态|1，此时句子结束，相当于下一个字符是#，按G->S·#移入，形成G->S#·可以规约；如果在状态|1，下一个字符是(，就按S->S·(S)#/(移入，这里不存在冲突
展望符的作用是，当同一个状态里有两个产生式都可以规约的时候，句子下一个字符与哪个产生式的展望符相同就按哪个规约

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

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

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

产生式

可以简写为：

如上例中，

可以简写为：

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

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

推导的反过程称为 归约 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右线性文法）

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

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

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

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

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

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

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

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

❸ 四种文法的类型(编译原理)

乔姆斯基（Chomsky）按产生式的类型把文法分为四种类型：0、1、2、3型文法。

*在下文中的产生式中，箭头左边的大写字母为严格的非终结符，而其左边的小写字母不严格要求为非终结符，如[0型文法]中的第2条产生式。

【0型文法】

产生式形式：α→β

要求：箭头左边的α 至少 含有 一个非终结符 ， 其余 不加任何限制

    例如，G：C→AaB

                     aA→a

                     B→b|Bb

【1型文法】

产生式形式：α→β

要求： |α|≤|β| (产生式左端的长度<=右端的长度)，S→ε除外。

例如G： C→aAB

               aA→aBa

               B→b|Bb 

【2型文法】(上下文无关文法)

产生式形式：A→β，A∈VN(终结符) ，β∈V *(VN∪VT，即可为终结符也可为非终结符) 

说明：当以β替换A时，与A的上下文环境无关；

          大部分程序设计语言近似于2型文法。

【3型文法】(正规文法 / 右线性文法)

产生式形式：A→a，A→aB，

说明：a∈VT(终结符) ，  A，B∈VN(非终结符)，即产生式右端的第一个符号必须为 终结符

例如 G：A→aB

              B→b|bB

【其他说明】对于这四种类型的文法：

*包含关系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'译为A包含B)

*严格程度：3 > 2 > 1 > 0

*判断文法所属类型的顺序：3 → 2 → 1 → 0

❹ 编译原理中怎样写文法和语言

写文法：首先要清楚语言集的特征，即找出其特殊值及通式，然后再按此考虑去写出文法
写语言：要先理解推导、句型、句子的概念，语言就是句子的全体。

❺ 编译原理-文法定义

文法定义公式如下:

Chomsky 文法分类将文法分为四种，0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。

又被称为无限制文法(Unrestricted Grammar), 或者短语结构文法（Phrase Structure Grammar）
定义: 对于产生式 α→β ， α 至少包含一个非终结符。

为什么要叫无限制文法，明明它要求产生式的左部必须包含一个非终结符。

又被称为上下文有关文法(Context-Sensitive Grammar)
定义：对于产生式 α→β , |α| <= |β| , 仅仅 S→ε 除外

为什么叫做上下文有关文法？

一般情况下，这种产生式的形式为 α1Aα2→α1βα2

又被称为上下文无关文法(Context-Free Grammar)
定义：对任一产生式 α→β ，都有 α∈VN，β∈(VN∪VT)*

为什么叫上下文无关文法？

又被称为正则文法（Regular Grammar，RG），分为右线性（Right Linear）文法和左线性（Left Linear）文法。

定义: 对任一产生式 α→β ，都有 α∈VN，β最多两个字符元素，如果有二个字符必须是（终结符+非终结符）的格式，如果是一个字符，那么必须是终结符。

根据产生式右部非终结符位置不同，分为右线性文法和左线性文法。

可以看出，不同文法就是对产生式进行逐层的限制，所以各个文法是包含关系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最后包含3型文法。

❻ 编译原理中的文法设计这题该怎么做，能给一下思路和答案吗

文法的设计需要考虑文法的类型和表达能力。一种可能的思路是：

• 首先，确定值为非负的5的倍数或3的李腊消倍数的数字串有什么特征，例如结尾只能是0或5或3或6或9，不能有前导0等。

• 然后，选择合适的文法类型来描述这些特征，例如正规文法、上下文无关文法等。

• 最后，根据文法类哪知型的规则，给出局宽产生式和开始符号。

一种可能的答案是：

• 使用正规文法来描述这个语言。

• 产生式如下：

• S -> 0 | 3 | 5 | 6 | 9


• S -> A0 | A3 | A5 | A6 | A9


• A -> S


• A -> AA



• 开始符号为S。

❼ 编译原理-LL1文法详细讲解

我们知道2型文法( CFG )，它的每个产生式类型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一个表达式的文法:

最终推导出 id + (id + id) 的句子，那么它的推导过程就会构成一颗树，即 CFG 分析树：

从分析树可以看出，我们从文法开始符号起，不断地利用产生式的右部替换产生式左部的非终结符，最终推导出我们想要的句子。这种方式我们称为自顶向下分析法。

从文法开始符号起，不断用非终结符的候选式(即产生式)替换当前句型中的非终结符，最终得到相应的句子。
在每一步推导过程中，我们需要做两个选择:

因为一个句型中，可能存在多个非终结符，我们就不确定选择那一个非终结符进行替换。
对于这种情况，我们就需要做强制规定，每次都选择句型中第一个非终结符进行替换(或者每次都选择句型中最后一个非终结符进行替换)。

自顶向下的语法分析采用最左推导方式，即总是选择每个句型的最左非终结符进行替换。

最终的结果是要推导出一个特定句子(例如 id + (id + id) )。
我们将特定句子看成一个输入字符串，而每一个非终结符对应一个处理方法，这个处理方法用来匹配输入字符串的部分，算法如下:

方法解析:

这种方式称为递归下降分析( Recursive-Descent Parsing )：

当选择的候选式不正确，就需要回溯( backtracking )，重新选择候选式，进行下一次尝试匹配。因为要不断的回溯，导致分析效率比较低。

这种方式叫做预测分析( Predictive Parsing )：

要实现预测分析，我们必须保证从文法开始符号起，每一个推导过程中，当前句型最左非终结符 A 对于当前输入字符 a ,只能得到唯一的 A 候选式。

根据上面的解决方法，我们首先想到，如果非终结符 A 的候选式只有一个以终结符 a 开头候选式不就行了么。
进而我们可以得出，如果一个非终结符 A ，它的候选式都是以终结符开头，并且这些终结符都各不相同，那么本身就符合预测分析了。

这就是S_文法，满足下面两个条件:

例子:

这就是一个典型的S_文法，它的每一个非终结符遇到任一终结符得到候选式是确定的。如 S -> aA | bAB , 只有遇到终结符 a 和 b 的时候，才能返回 S 的候选式，遇到其他终结符时，直接报错，匹配不成功。

虽然S_文法可以实现预测分析，但是从它的定义上看，S_文法不支持空产生式(ε产生式)，极大地限制了它的应用。

什么是空产生式(ε产生式)？

例子

这里 A 有了空产生式，那么 S 的产生式组 S -> aA | bAB ，就可以是 a | bB ,这样 a , bb , bc 就变成这个文法 G 的新句子了。

根据预测分析的定义，非终结符对于任一终结符得到的产生式是确定的，要么能获取唯一的产生式，要么不匹配直接报错。

那么空产生式何时被选择呢？

由此可以引入非终结符 A 的后继符号集的概念:
定义: 由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符 a 的集合，就是这个非终结符 A 的后继符号集，记为 FOLLOW(A) 。

因此对于 A -> ε 空产生式，只要遇到非终结符 A 的后继符号集中的字符，可以选择这个空产生式。
那么对于 A -> a 这样的产生式，只要遇到终结符 a 就可以选择了。

由此我们引入的产生式可选集概念:
定义: 在进行推导时，选用非终结符 A 一个产生式 A→β 对应的输入符号的集合，记为 SELECT(A→β)

因为预测分析要求非终结符 A 对于输入字符 a ,只能得到唯一的 A 候选式。
那么对于一个文法 G 的所有产生式组，要求有相同左部的产生式，它们的可选集不相交。

在 S_文法基础上，我们允许有空产生式，但是要做限制:

将上面例子中的文法改造:

但是q_文法的产生式不能是非终结符打头，这就限制了其应用，因此引入LL(1)文法。

LL(1)文法允许产生式的右部首字符是非终结符，那么怎么得到这个产生式可选集。
我们知道对于产生式:

定义: 给定一个文法符号串 α ， α 的 串首终结符集 FIRST(α) 被定义为可以从 α 推导出的所有串首终结符构成的集合。

定义已经了解清楚了，那么该如何求呢？
例如一个文法符号串 BCDe , 其中 B C D 都是非终结符， e 是终结符。

因此对于一个文法符号串 X1X2 … Xn ，求解 串首终结符集 FIRST(X1X2 … Xn) 算法:

但是这里有一个关键点，如何求非终结符的串首终结符集？

因此对于一个非终结符 A , 求解 串首终结符集 FIRST(A) 算法:

这里大家可能有个疑惑，怎么能将 FIRST(Bβ) 添加到 FIRST(A) 中，如果问文法符号串 Bβ 中包含非终结符 A ，就产生了循环调用的情况，该怎么办?

对于 串首终结符集 ，我想大家疑惑的点就是，串首终结符集到底是针对 文法符号串 的，还是针对 非终结符 的，这个容易弄混。
其实我们应该知道， 非终结符 本身就属于一个特殊的 文法符号串 。
而求解 文法符号串 的串首终结符集，其实就是要知道文法符号串中每个字符的串首终结符集:

上面章节我们知道了，对于非终结符 A 的 后继符号集 :
就是由文法 G 推导出来的所有句型，可以出现在非终结符 A 后边的终结符的集合，记为 FOLLOW(A) 。

仔细想一下，什么样的终结符可以出现在非终结符 A 后面，应该是在产生式中就位于 A 后面的终结符。例如 S -> Aa ，那么终结符 a 肯定属于 FOLLOW(A) 。

因此求非终结符 A 的 后继符号集 算法：

如果非终结符 A 是产生式结尾，那么说明这个产生式左部非终结符后面能出现的终结符，也都可以出现在非终结符 A 后面。

我们可以求出 LL(1) 文法中每个产生式可选集:

根据产生式可选集，我们可以构建一个预测分析表，表中的每一行都是一个非终结符，表中的每一列都是一个终结符，包括结束符号 $ ，而表中的值就是产生式。
这样进行语法推导的时候，非终结符遇到当前输入字符，就可以从预测分析表中获取对应的产生式了。

有了预测分析表，我们就可以进行预测分析了，具体流程:

可以这么理解：

我们知道要实现预测分析，要求相同左部的产生式，它们的可选集是不相交。
但是有的文法结构不符合这个要求，要进行改造。

如果相同左部的多个产生式有共同前缀，那么它们的可选集必然相交。
例如:

那么如何进行改造呢？
其实很简单，进行如下转换:

如此文法的相同左部的产生式，它们的可选集是不相交，符合现预测分析。

这种改造方法称为 提取公因子算法 。

当我们自顶向下的语法分析时，就需要采用最左推导方式。
而这个时候，如果产生式左部和产生式右部首字符一样(即A→Aα)，那么推导就可能陷入无限循环。
例如:

因此对于:

文法中不能包含这两种形式，不然最左推导就没办法进行。

例如:

它能够推导出如下:

你会惊奇的发现，它能推导出 b 和 (a)* (即由 0 个 a 或者无数个 a 生成的文法符号串)。其实就可以改造成:

因此消除 直接左递归 算法的一般形式：

例如:

消除间接左递归的方法就是直接带入消除，即

消除间接左递归算法：

这个算法看起来描述很多，其实理解起来很简单：

思考 : 我们通过 Ai -> Ajβ 来判断是不是间接左递归，那如果有产生式 Ai -> BAjβ 且 B -> ε ,那么它是不是间接左递归呢？
间接地我们可以推出如果一个产生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那么这个产生式是不是间接左递归。

❽ 一个编译原理问题

首先写出指定句型的规范推导：

S→(L)→(L,S)→(L,(L))→(L,(S))→(L,(a))→(S,(a))

然后画出分析树如下图

根据分析树的叶子结点可以找出该句型的所有短语：

aS(a)S,(a)(S,(a))

直接短语，就是经过一次非终结符替换得到的短语：

aS没了

句柄就是最左直接短语，要进行规约的部分，根据分析树我们找到最左直接短语为：

S

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

【定义】

文法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是开始符号