编译原理上下文文法

㈠ 编译原理：构造产生此语言的上下文无关文法G

对于文法G=(V, T, S, P)，如果产生式的形式如下：
A -> xB
A -> x
其中A, B属于V，x属于T*，则称为右线性文法；相似的，如果产生式的形式如下：
A -> Bx
A -> x
则称为左线性文法。右线性文法和左线性文法统称为正则文法。
正则表达式的表达能力等价于正则文法，正则表达式的定义如下：
字母表中的任意字母是正则表达式，空串和空集也是正则表达式；
如果r, s是正则表达式，那么r|s, rs, r*, (r)也是正则表达式。
正则表达式的扩展：
r+：一个或多个重复
. ：任意字符
[a-z]：字符范围
[^abc]：不在给定集合中的任意字符
r?：可选
正则表达式只能使用终结符（字母表中的字符），因而很容易变得复杂又难懂，实际中，经常使用正则描述，正则描述允许使用非终结符定义表达式，很像EBNF，但是它限制在未完全定义之前，不能使用非终结符，也就是说不允许递归或自嵌套。
像正则表达式的表达能力等价于正则文法一样，BNF范式的表达能力等价于上下文无关文法。BNF是“Backus Naur Form”的缩写。John Backus和Peter Naur首次引入一种形式化符号来描述给定语言的语法。
BNF的元符号：
::= 表示“定义为 ”，有的书上用-->
| 表示“或者”
< > 尖括号用于括起非终结符。
BNF的扩展EBNF：
可选项被括在元符号“[”和“]”中
重复项（零个或者多个）被括在元符号“{”和“}”中
仅一个字符的终结符用引号（"）引起来，以和元符号区别开来
上述操作符不是严格限定的，有的人喜欢直接使用扩展正则表达式的操作符描述EBNF。除了方便表达以外，引入EBNF的另一个主要原因是为了更紧密地把文法映射到递归下降分析程序的真实代码。当需要手动构造归下降分析程序的时候，通常把上下文无关文法改写为EBNF是必需的。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
BNF的扩展EBNF：
可选项被括在元符号“[”和“]”中
重复项（零个或者多个）被括在元符号“{”和“}”中
仅一个字符的终结符用引号（"）引起来，以和元符号区别开来
上述操作符不是严格限定的，有的人喜欢直接使用扩展正则表达式的操作符描述EBNF。除了方便表达以外，引入EBNF的另一个主要原因是为了更紧密地把文法映射到递归下降分析程序的真实代码。当需要手动构造归下降分析程序的时候，通常把上下文无关文法改写为EBNF是必需的。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。
如上所述，上下文无关文法的递归性，对其分析方法也有很大影响。首先，用作识别这些结构的算法必须使用递归调用或显式管理的分析栈。其次，用作表示语言语义结构的数据结构现在也必须是递归的（通常是一颗分析树），而不再是线性的（如同用于词法和记号中的一样）了。
在程序设计语言中，通常用正则表达式描述词法规则。但是正则表示式的表达能力有限，她无法表达括号配对等语法形式，因而，需要引入表达能力更强的上下文无关文法。编译程序中常用正则文法表示词法，用上下文无关文法表示语法。那么程序语言中那些属于词法哪些属于语法呢？一个简单的办法，把所有能用正则文法表示的规则成为词法，即我们用尽可能的使用正则文法表示更多的东西，那些无法用正则表示式表示的成为句法，如c语言中的{ statement; }语法形式。语言中有些规则使用上下文无关文法仍然无法描述，例如变量的定义在使用之前，类型匹配等等，这些通常称为（静态）语义，它们在编译程序的静态语义检查阶段进行检测。
如果一个上下文无关文法G不是自嵌套或自递归的，即不存在如下推导：
U =>* xUy
那么L(G)是正则语言。自嵌套的上下文无关文法不一定是正则语言。事实上，一个上下文无关文法是严格的，既不可能由正则文法产生，当且仅当该语言的一切文法都是自嵌套的。

㈡ 编译原理 文法类型

    0型文法(Type-0 Grammar)

    1型文法(Type-1 Grammar)

    2型文法(Type-2 Grammar)

    3型文法(Type-3 Grammar)

无限制文法(Unrestricted Grammar) /短语结构文法(Phrase Structure Grammar, PSG )

∀α → β∈P， α中至少包含1个非终结符

0型语言

由0型文法G生成的语言L(G )

上下文有关文法(Context-Sensitive Grammar , CSG )

∀α → β∈P，｜α｜≤｜β｜

产生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )

上下文有关语言（1型语言）

由上下文有关文法(1型文法) G生成的语言L(G )

上下文无关文法(Context-Free Grammar, CFG )

∀α → β∈P，α ∈ VN

产生式的一般形式：A→β

上下文无关语言（2型语言）

由上下文无关文法(2型文法) G生成的语言L(G )

正则文法(Regular Grammar, RG )

右线性(Right Linear)文法： A→wB 或 A→w

左线性(Left Linear) 文法： A→Bw 或 A→w

左线性文法和右线性文法都称为正则文法

0型文法：α中至少包含1个非终结符

1型文法（CSG） ：｜α｜≤｜β｜

2型文法（CFG） ：α ∈ VN

3型文法（RG）：A→wB 或 A→w (A→Bw 或A→w)

0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法

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

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

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

产生式

可以简写为：

如上例中，

可以简写为：

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

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

推导的反过程称为 归约 。

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

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

例
文法

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

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

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

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

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

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

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

例：（右线性文法）

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

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

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

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

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

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

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

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

㈣ 上下文无关文法适合描述什么规则....很急（编译原理的）

上下无关文法，适合用来描述程序设计的语言。c语言，php，java的语法规则都涉及到上下无关文法。
正规文法用来识别单词。

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

通过算法对文法的每一产生式进行分析,如果存在复杂递归,则必是上下文无关文法,否则就是正则文法.
1、像A->Aa|ε这样的文法,虽然存在递归,但却是单一的自递归,可以通过有穷自动机表示和分析处理,所以是正则文法；
2、但是像E->E+T,T->id|(E)这样的文法显然非单一的自递归,而是存在复杂递归,自动机是无法表示和处理的,必然是上下文无关文法.
另外还请注意：
1、正则文法是上下文文法的子集,正则文法也属于上下文无法,但有的上下文文法不一定是正则文法；
2、同时再结合这两个的形式定义认真揣摩必定能悟出一二.

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

乔姆斯基（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

㈦ 在编译原理中，什么是上下文无关文法什么是语言

二型文法如下:S->AcS->ScA->abA->aAb三型文法如下:S->aSA->bAB->cBB->cA->BbA、2型文法是上下文无关文法，表现在产生式上就是产生式的左部只有一个非终结符；3型文法从广义上讲包括左线形文法、右线形文法和正规文法。B、左线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最左端。C、右线形文法产生式的右部要么没有非终结符，如果有非终结符也只能有一个，且必须位于产生式右部的最右端。D、正规文法是右线形文法的一个子集，其产生式右部只有三种情况：1）空串2）只有一个终结符3）只有一个终结符后接一个非终结符E、所有的3型文法都是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型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。

㈨ 编译原理-文法定义

文法定义公式如下:

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型文法。

㈩ 编译原理

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

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

(10)编译原理上下文文法扩展阅读：

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

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

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