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

上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。

而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。

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

产生式

可以简写为：

如上例中，

可以简写为：

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

如上例中， 可以推导出 或 或 等等。

如果 ，

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

推导的反过程称为 归约 。

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

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

即：

例

文法

表示什么呢？

代表小写字母；

代表数字；

表示若干个字母和数字构成的字符串；

说明 是一个字母、或者是字母开头的字符串。

那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。

并、连接、幂、克林闭包、正闭包。

如上例表示为：

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

产生式一般形式：

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

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

产生式的一般形式：

即产生式左边都是非终结符。

右线性文法 ：

左线性文法 ：

以上都成为正则文法。

即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。

例：（右线性文法）

以上文法满足右线性文法。

以上文法生成一个以字母开头的字母数字串（标识符）。

以上文法等价于 上下文无关文法 ：

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

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

根节点 表示文法开始符号S；

内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；

叶节点 （又称边缘）既可以是非终结符也可以是终结符。

给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。

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

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

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

二义性原因：多个if只有一个else；

消岐规则：每个else只与最近的if匹配。

（1）

G'(S)

S->(L)|aT

T->+S|e

L->L,S|S

提取了 公共左因子

（2）

是LL(1)文法

LL分析法和LR分析法。

1、自上而下语法分析方法（LL分析法）

给定文法G和源程序串r。从G的开始符号S出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出r 。 是一种产生的方法，面向目标的方法。分析的主旨为选择产生式的合适的侯选式进行推导，逐步使推导结果与r匹配。

2、自下而上语法分析方法（LR分析法）

从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号S。是一种辨认的方法，基于目标的方法。分析的主旨为寻找合适的子串与P的侯选式进行匹配，直到归约到G的S为止 。

扩展资料

LALR分析器可以对上下无关文法进行语法分析。LALR即“Look-AheadLR”。其中，Look-Ahead为“向前看”，L代表对输入进行从左到右的检查，R代表反向构造出最右推导序列。

LALR分析器可以根据一种程序设计语言的正式语法的产生式而对一段文本程序输入进行语法分析，从而在语法层面上判断输入程序是否合法。

实际应用中的LALR分析器并不是由人手工写成的，而是由类似于yacc和GNU Bison之类的LALR语法分析器生成工具构成。由机器自动生成的代码相比较于程序员手工的代码，拥有更好的运行效率而且减少了程序员的工作量。

参考资料来源：百度百科-语法分析器

参考资料来源：百度百科-语法分析

这是编译原理里的问题

文法 可以通俗的说是一个东西产生所遵循的规则，如语言中的主谓宾，就是语言的文法

G[S] 这是文法G ：S->0S0 S->1 这就是他里面的规则

S-> 0 S 0 或S->1

N 表示一个数遵循文法G

n->0s0->00s00->00100

或者说他永远遵循文法G中S->0s0规则那么只可能为0

若遵循文法S-> 0 S 0 或S->1则大于0

在编译原理中，语法规则和词法规则不同之处在于：规则主要识别单词,而语法主要识别多个单词组成的句子。

词法分析和词法分析程序：

词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。

语法分析（Syntax analysis或Parsing）和语法分析程序（Parser）

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等语法分析程序判断源程序在结构上是否正确源程序的结构由上下文无关文法描述

语义分析（Syntax analysis）

语义分析是编译过程的一个逻辑阶段 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配

以上就是关于【编译原理】第二章：语言和文法全部的内容，包括:【编译原理】第二章：语言和文法、设文法g(s) 判断该文法是否为ll1文法、语法分析最常用的两类方法等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！