编译原理文法扩展

① 编译原理为什么存在递归文法

编译原理中存在递归文法是因为编程语言的语法和结构往往具有递归性质。递归文法是一种用来描述编程语言语法的形式化表示方法，其中规则可以包含对同一语法结构的递归引用。这种递归性质反映了编程语言中常见的嵌套和递归结构。
以下是一些原因，说明为什么编译原理中存在递归文法：
1. 语法结构的嵌套：编程语言中的语法结构通常可以嵌套在其他语法结构中，例如，一个函数可以包含其他函数，一个条件语句可以包含另一个条件语句，等等。递归文法可以很自然地表示这种嵌套结构。
2. 语法的可扩展性：编程语言通常需要具有可扩展性，允许程序员定义新的语法结构或数据类型。递归文法可以轻松地扩展以包括新的语法规则。
3. 函数调用和表达式求值：编程语言中的函数调用和表达式求值通常是递归的过程。递归文法可以用于清晰地描述这些递归计算过程。
4. 简洁性和可读性：递归文法可以帮助编译器设计者更简洁地表示语言的语法，这有助于提高编译器的可读性和维护性。
5. 符合语言设计的自然表示：递归文法使得语法规则的表示更符合编程语言设计的自然结构，因为它们允许对语法结构进行递归定义，而不需要多次重复相似的规则。
虽然递归文法在编译原理中非常有用，但它们也需要谨慎使用，以避免无限递归或歧义性。编译器设计者需要确保递归文法能够被正确解析和处理，通常需要使用递归下降解析器或其他技术来处理递归文法。

② 编译原理

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

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

(2)编译原理文法扩展扩展阅读：

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

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

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

③ 编译原理中的语法和文法一样吗

编译原理中的语法和文法是不一样的，但却融会贯通。
在计算机科学中，文法是编译原理的基础，是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型，即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型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。

④ 在编译原理中： 文法S——>SS+|SS*|a能产生什么语言，并验证！ 求高人指导！

为了使问题简化，我们考虑文法S->ss+|a，考虑s->ss*时，只要把+换成*即可。
0层递归是，s->a,文法的语言是{a}。是后缀表达式。
1层以内递归时，文法语言是{a,aa+}。是后缀表达式。
2层以内递归时，文法语言是{a,aa+}.{a,aa+}.{+}。其中.表示连接，是后缀表达式。
依此类推，多少层的递归都是后缀表达式。
把表达式的+换成*后依然为后缀表达式。
下面证明文法产生的语言是所有的以a为变量，以+和*为运算符的后缀表达式。
因为每个表达式都对应一个常规的表达式（如1*2+3就是常规表达式），下面只需证明语言能产生的后缀表达式对应所有的常规表达式。当常规表达式只有一个运算符，对应aa+或aa*。当常规表达式有两个运算符，可写成(表达式1）.{+|*}.(表达式2），因为表达式1和2都只含一个运算符，所以可以用语言表示，上述常规表达式可用后缀表达式（表达式1）.（表达式2）.{+l*}表示。所以不管常规表达式有多少个运算符，都可以由语言的后缀表达式对应。

⑤ 语法分析中怎么消除左递归、怎么确保正确的优先级和结合性“编译原理”

在探讨如何消除左递归、确保正确的优先级和结合性时，我们首先回顾一下左递归、优先级和结合性的基本概念。左递归是指在二元表达式语法规则中，如果产生式的第一个元素是它自身，程序会无限递归，如“加法表达式 + 乘法表达式”。优先级和结合性是计算机语言中与表达式相关的核心概念，涉及语法规则的设计。通常，我们使用上下文无关文法和巴科斯范式（BNF）来书写语法规则。

为了确保正确的优先级，我们通常设计语法规则时，将具有较高优先级的操作放在较低优先级操作的下层。例如，乘法运算在加法运算之前。在表达式语法中，我们按照优先级从低到高排列：赋值运算、逻辑运算、比较运算、加减运算、乘除运算和基础表达式。

结合性问题涉及到运算符的计算顺序，通常，算术运算符是左结合的，即从左到右计算。例如，表达式“2+3+4”应该先计算“3+4”，然后与“2”相加。为了确保正确的结合性，我们可以通过调整语法规则，例如将递归项放在运算符的左侧，来解决左递归问题。

消除左递归的方法通常是将左递归文法转换为非左递归形式。例如，将“add -> add + mul”转换为“add -> a | add + mul”。这样，对于“2+3+4”这样的表达式，我们可以正确生成AST，并确保结合性。

在实际应用中，我们还需要考虑表达式语法的扩展，例如使用扩展巴科斯范式（EBNF）来表示规则，其中可以使用正则表达式的一些写法，如使用“*”表示可重复0到多次的子表达式。

通过阅读语言的语法规则文件，我们可以了解各种运算符的优先级和结合性，这对于理解语言的内部机制非常有用。此外，使用现代编译工具如ANTLR或Yacc时，这些规则通常以BNF或EBNF的形式表示，可以帮助我们构建语法分析器。

消除左递归和确保正确的优先级与结合性的关键在于设计合理的语法规则，确保在解析表达式时能够生成正确的AST，并且遵循正确的运算顺序。这通常涉及到调整语法规则、使用适当的递归结构以及理解运算符的优先级和结合性。

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

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

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

产生式

可以简写为：

如上例中，

可以简写为：

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

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

推导的反过程称为 归约 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右线性文法）

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

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

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

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

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

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

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

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

⑦ 编译原理的题目：对于文法G(E):E→T|E+T|E-T T→F|T*F|T/F F→(E)|i

终极符集合Vt={+,-,*,/,(,),i}
非终极符集合Vi={E,T,F}
最右推导：E => E-T => E-F => E-(E) => E-(T) => E-(T+F) => E-(T+i) => E-(T*F+i)
直接短语：T*F,i