编译原理中什么叫推导

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

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

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

产生式

可以简写为：

如上例中，

可以简写为：

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

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

推导的反过程称为 归约 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右线性文法）

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

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

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

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

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

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

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

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

Ⅱ 求最左推导和最右推导

最左推导（Leftmost Derivation）

最左推导是一种从文法的起始符号开始，总是优先替换最左边的非终结符的推导过程。具体步骤如下：

• 从文法的起始符号开始。

• 在每一步中，找到当前字符串中的最左边的非终结符，并用其某个产生式进行替换。

• 重复第2步，直到得到一个只包含终结符的字符串为止。

最右推导（Rightmost Derivation）

最右推导与最左推导相反，它总是优先替换最右边的非终结符。具体步骤如下：

• 从文法的起始符号开始。

• 在每一步中，找到当前字符串中的最右边的非终结符，并用其某个产生式进行替换。

• 重复第2步，直到得到一个只包含终结符的字符串为止。

示例

考虑以下简单的上下文无关文法：

• S → A B

• A → a A

• A → ε

• B → b B

• B → ε

最左推导示例：

• S （起始符号）

• A B （S → A B）

• a A B （A → a A，替换最左边的A）

• a a A B （A → a A，替换最左边的A）

• a a b B （B → b B，替换最左边的B）

• a a b b B （B → b B，替换最左边的B）

• a a b b （B → ε，替换最左边的B）

最右推导示例：

• S （起始符号）

• A B （S → A B）

• A a B （A → a A，替换最右边的A）

• A a b B （B → b B，替换最右边的B）

• A a b b B （B → b B，替换最右边的B）

• A a b b （B → ε，替换最右边的B）

• a A b b （A → a A，替换最右边的A）

• a a A b b （A → a A，替换最右边的A）

• a a b b b b （A → ε 和 B → ε，分别替换最右边的A和B）

Ⅲ 编译原理

编译原理)：利用编译程序从源语言编写的源程序产生目标程序的过程； 用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。

编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成

(3)编译原理中什么叫推导扩展阅读：

编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。

编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。

而自下而上分析法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。

Ⅳ 编译原理的LL(1)文法是什么意思

LL(1)的含义：第1个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将用最左到推倒，1表明只需向右看一个符号便可决定如何推倒即选择哪个产生式（规则）进行推导，类似也可以有LL（k）文法，也就是需要向前查看k个符号才能确定选用哪个产生式。
这是从我们编译原理课本上抄来的，希望对你有帮助

Ⅳ 什么叫活前缀,用通俗的话解答下,或者简单的例子。 这个题是编译原理的。

活前缀：右句型的前缀，而且其右端不会超过该句型的最右边句柄的末端。
右句型：最右推导可得到的句型。
最右推导：每步推导都替代最右非终结符的推导。
推导：我们说αBγ推导出αβγ，是说存在产生式B->β。
产生式：左边为非终结符，右边为终结符与非终结符组合成的串。
非终结符：是字符串的集合。
终结符：组成语言的词。如c语言中的2，a，int，if等。
句型：开始符经过若干步推导后得到的串。
前缀：如abc的前缀为a、ab、abc。
开始符：开始符是整个语言的集合。
句柄：非形式的，句柄是和某个产生式右部匹配的字符串，把句柄归约成产生式左部的非终结符，可以得到最右推导的逆过程的一步。形式的定义为：开始符s经过若干步最右推导得到αBγ，αBγ经过一步最右推导得到αβγ，若γ为终结符的集合，则β为句柄。举例：
E->E+E|E*E|-E|(E)|id，对于id+id*id，其中一个最右推导为E->E+E->E+E*E->E+E*id->E+id*id->id+id*id。在id+id*id归约成E+id*id的过程中，最左边的id是句柄。E+id*id归约成E+E*id时，最左边的id是句柄，把E+E*id归约成E+E*E时，id是句柄。把E+E*E归约成E+E时E*E是句柄。E+E归约成E时，E+E是句柄。
归约：可理解为把产生式右边的串用产生式左边的非终结符代替。
注1：再说一下活前缀，举个例子，比如E+E*E归约成E+E，句柄是E*E，那么它的活前缀就是E、E+、E+E、E+E*、E+E*E。又比如id+id*id归约成E+id*id，句柄是最左边的id，那么它的活前缀是id，因为不能超过句柄。
注2：至于为什么要给出活前缀的定义和如何用归约的方法实现语法分析，还要进一步学习。

Ⅵ 什么是*＝>星推导(编译原理) 星推导和加推导的区别

在编译原理中，产生式的推导可以细分为  *=>  "星推导"和 +=> "加推导"，

那么这两个分别是什么意思呢？

其实，'*' 和 '+' 这两个符号是来自 正则表达式 的，正则表达式是什么大家可以先不了解，弄懂这个问题暂时只需要知道 '*' 和 '+' 这两个符号的意思就可以了。

符号 * ：[1, n)  1到多

符号 + ：[0, n) 0到多

则， *=>  "星推导" 为对产生式进行1到多次推导； +=> "加推导" 为对产生式进行0到多次推导。

【举例】

（1）v +＝> w：意为产生式左端的 v 经过1到多次推导后能得到右端的 w

（2）v * => w： 意为产生式左端的 v 经过0到多次推导后能得到右端的w(其实，

                 就是比第（1）条多了一种情况，即 v= w，当 v= w 时，v不需要推导即可得到w，所以推导的次数为0)