‘壹’ 【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
‘贰’ 编译原理：c语言标识符的正则表达式
是缺了。这个只能匹配字母开头、字母数字组成的标示符
LZ可以自己加上，加在letter里
‘叁’ 编译原理，左线性文法
{l}{l,d}*表示集合 {l}和{l,d}*的乘积，具体含义为“以l开头的、后面跟着由l和d组成的任意串”。
该文法就是一般语言中的“标识符”的定义（其中：l代表字母letter，d代表数字digit）
‘肆’ 四种文法的类型(编译原理)
乔姆斯基（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
‘伍’ 求解编译原理的一道题:设有文法如下
首先要做这题你要知道判别文法类型
包括四个层次：
0-型文法（无限制文法或短语结构文法）包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串，这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别，后者是前者的一个真子集，是能够被一个总停机的图灵机判定的语言。
1-型文法（上下文相关文法）生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号，而 α, β 和 γ 是包含非终结符号与终结符号的字串；α, β 可以是空串，但 γ 必须不能是空串；这种文法也可以包含规则 S->ε ，但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号，γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
3-型文法（正规文法）生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号，产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号；如果所有产生式的右侧都不含初始符号 S ，规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受，也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类，上下文无关语言类包含于上下文相关语言类，上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系，也就是说：存在递归可枚举语言不属于上下文相关语言类，存在上下文相关语言不属于上下文无关语言类，存在上下文无关语言不属于正规语言类。
1）本题应该是--上下文无关文法
句子是产生式在推导时“仅仅有终结符”的任何一步
2）%mm%nn 是一个句子
由于下面一题的图我等级不够 不能贴图 发你邮箱
‘陆’ 编译原理：构造表示“标识符”的正则表达式标识符定义：以字母开头的字母数字串，标识符可以有后缀，
^([A-Za-z]\w*)([.]([A-Za-z]\w*))*$
不知理解得对不对
比如
(java).(util).(Locale)
java util Locale三组都是以字母开头,后接单词字符(即[A-Za-z0-9_]的缩写\w)的表达式
‘柒’ 编译原理中怎样写文法和语言
写文法：首先要清楚语言集的特征，即找出其特殊值及通式，然后再按此考虑去写出文法
写语言：要先理解推导、句型、句子的概念，语言就是句子的全体。
‘捌’ 什么是文法(编译原理)
【定义】
文法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是开始符号
‘玖’ 编译原理的文法是什么
文法是描述语言规则的形式规则。实际上就是用一个四元组G=(VT,VN,S,P)定义的一个推理方式。其中VT是终结符，VN是非终结符，S是开始符号，P是一组产生规则。
‘拾’ 你好，我正在学习编译原理，对定义文法不是很清楚，您能否举例一个语言，并定义其文法。
抱歉，今天才上网。
题目：写一个文法，使其语言是奇数集，且每个基数不以0开头。
分析：奇数集可以是个位数13579；可以是多位数（最高位不为0，中间0到9，个位是13579）
解答：文法G（S）：S-->A|NMA
A-->1|3|5|7|9
N-->1|2|3|4|5|6|7|8|9
M-->(空的字符我打不出来)|0|MA|A