当前位置：文档之家 › 编译原理第二章

编译原理第二章

  • 格式：ppt
  • 大小：1.05 MB
  • 文档页数：36

下载文档原格式

  / 36

合集下载

编译原理第二章

编译原理第二章
安徽理工大学 《编译原理》 信息安全系 sb
19
…… <数字>::=9 该文法的字汇表V为：V={0, 1, …, 9, <无 符号整数>, <数字串>, <数字>} •终结符与非终结符： 终结符与非终结符： 终结符与非终结符 给定文法G， 给定文法 ，凡出现在规则左部的符号称 为非终结符，其组成的集合记为： 为非终结符，其组成的集合记为： Vn。凡 不属于V 的符号称为终结符， 不属于 n 的符号称为终结符，其组成的集 合记为： Vt 。 合记为： 字汇表:V= Vn∪Vt 字汇表 Vn∩Vt = φ 若无特殊说 我们用大写字母表示非终结符。 明，我们用大写字母表示非终结符。
安徽理工大学 《编译原理》 信息安全系 sb
17
<代词> ::=I <谓语> ::=<动词><直接宾语> <动词> ::=love <直接宾语> ::=<物主代词><名词> <物主代词> ::=my <名词> ::=motherland 其中，带有尖括号的称为语法成分或语法 类，不带尖括号的称为单词符号或单词。 •文法与字汇表： 文法与字汇表： 文法与字汇表 文法(G[Z])是规则的非空有穷集合。 是规则的非空有穷集合。 文法 是规则的非空有穷集合
安徽理工大学 《编译原理》 信息安全系 sb
8
2.符号串的运算 2.符号串的运算 •符号串相等： 符号串相等： 符号串相等 是字母表∑上的两个符号串 设x, y是字母表 上的两个符号串，若x与y 是字母表 上的两个符号串， 与 的诸符号依次相等，则符号串x, 相等 相等。 的诸符号依次相等，则符号串 y相等。记 为： x=y •符号串的长度： 符号串的长度： 符号串的长度 设x为字母表 上的符号串，符号串中包 为字母表∑上的符号串， 为字母表 上的符号串 含的符号的个数称为符号串x的长度 的长度。 含的符号的个数称为符号串 的长度。用|x| 表示。 表示。

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

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

语言的语法结构
总结词
语言的语法结构是语言形成和发展的核心要素，决定 了语言的表达方式和意义。
详细描述
语言的语法结构是指语言的组织规律和规则，包括词 法、句法、语义等方面的规则。词法规定了词汇的构 成和变化规则，如名词、动词、形容词等词类的划分 ；句法规定了句子结构的规则，如主语、谓语、宾语 等句子的成分及其排列顺序；语义则涉及到词汇和句 子的意义和解释。语言的语法结构是语言理解和生成 的基础，也是语言演变和发展的关键因素。
文法和语言的应用前景
1 2
人工智能领域
文法和语言是人工智能领域的重要基础，可用于 自然语言处理、机器翻译、语音识别等技术的研 究和应用。
计算机科学教育
文法和语言是计算机科学专业的重要课程之一， 对于培养计算机科学人才具有重要意义。
3
软件工程领域
文法和语言可用于软件工程领域中的编译器设计 和开发，提高软件开发的效率和可靠性。
05
文法和语言的未来发展
文法和语言的研究方向
形式语言理论
深入研究形式语言的基本理论， 包括语法、语义和语用等方面， 为自然语言处理和人工智能等领 域提供理论基础。
自然语言处理
结合自然语言处理技术，研究自 然语言的语法、语义和语用规律， 提高自然语言处理的准确性和效 率。
计算语言学
将计算语言学与形式语言理论相 结合，研究语言处理算法和模型， 为机器翻译、语音识别等领域提 供技术支持。
文法和语言的发展趋势
深度学习与文法和语言的结合
01
随着深度学习技术的发展，文法和语言的研究将更加注重与深
度学习的结合，以提高语言处理的性能和效率。
跨媒体语言处理
02
随着多媒体数据的普及，文法和语言的研究将逐渐扩展到跨媒

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

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

第一节 文法的直观概念
当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需 列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例， 人们无法列出全部句子， 但是人们可以给出一些规则， 用这些规则来说明 （或 者定义）句子的组成结构，比如： “我是大学生” 。是汉语的一个句子。汉语句子可以是由主语后随 谓语而成，构成谓语的是动词和直接宾语，我们采用 EBNF 来表示这种句子的构成规则： 〈句子〉∷＝〈主语〉 〈谓语〉 〈主语〉∷＝〈代词〉|〈名词〉 〈代词〉∷＝我|你|他 〈名词〉∷＝王明|大学生|工人|英语 〈谓语〉∷＝〈动词〉 〈直接宾语〉 〈动词〉∷＝是|学习 〈直接宾语〉∷＝〈代词〉|〈名词〉 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。 这些规则成为我们判别句子结构合法与否的依据。 一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。我们开始去找∷＝ 左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成： 〈句子〉 〈主语〉 〈谓语〉 ，然后在得到的串〈主语〉 〈谓语〉中，选取〈主语〉或〈谓语〉 ，再用相应的规则∷＝右端 代替之。比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉 ，那么得到： 〈主语〉 〈谓语〉〈代 词〉 〈谓语〉 ，重复做下去，我们得到句子： “我是大学生”的全部动作过程是： 〈句子〉 〈主语〉 〈谓语〉 〈谓语〉 〈代词〉 我〈谓语〉 〈直接宾语〉 我〈动词〉 我是〈直接宾语〉 我是〈名词〉 我是大学生 符号 的含义是，使用一条规则，代替 左边的某个符号，产生 右端的符号串。 显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生” ， “王 明学习英语” ， “我学习英语” ， “他学习英语” ， “你是工人” ， “你学习王明”等几十个句子。事实上， 使用文法作为工具，不仅为了严格地定义句子的结构，也是为了用适当条数的规则把语言的全部句 子描述出来，是以有穷的集合刻划无穷的集合的工具。

编译原理课件第二章

编译原理课件第二章

递归子程序法
递归子程序法：对应每个非终结符语法单元，，编一个独 立的处理过程（或子程序）。语法分析从读入第一个单词 开始，由非终结符<程序>（即开始符）出发，沿语法描述 图箭头所指出的方向进行分析。当遇到非终结符时，则调 用相应的处理过程，从语法描述图看，也就进入了一个语 法单元，再沿当前所进入的语法单元所指箭头方向继续进 行分析。当遇到描述图中是终结符时，则判断当前读入的 单词是否与图中的终结符相匹配，若匹配，再读取下一个 单词继续分析。遇到分支点时，将当前的单词与分支点上 多个终结符逐个相比较，若都不匹配时可能是进入下一个 非终结符语法单位或是出错。
N ö í ³ ´
ò ¡ í ó ´ Ó ´ Î
á ÷ ½ Ê
PL/0编译程序语义分析的设计与实现
PL/0编译程序语法、语义分析的的核心程序是BLOCK过程 ， 说明部分的分析与处理 表格管理 过程体(语句）的分析与处理
jmp jmp int lod lit opr sto opr int opr sto lod lit opr jpc cal lit lod opr opr opr opr sto jmp opr
0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 2 3 3 10 2 4 0 5 16 3 3 0 9 24 2 2 4 4 14 15 16 3 11 0
3 5 7 9 10 12 13 14
£ ¹ <
= =
Ç = ²
>
11
=
Ç = ²
, + - ( ¡ ¡ ­ ­
PL/0编译程序语法语义分析
PL/0编译程序语法分析的设计与实现

编译原理第二章课件

编译原理第二章课件
例1：文法G: S aSb | ab
L(G)={anbn|n≥1}
28
2.2.2 文法的分类
3型文法（又称线性文法、正则文法、正 规文法）
➢ 如果对文法G中的任一产生式均限制为形如： AB 或 A
其中： A，B∈VN , ∈VT 则称文法G为3型文 法。 ➢ 上述形式的3型文法也称为右线性文法。 ➢ 如果对文法G中的任一产生式均限制为形如：
Ａ0 ＝ { } Ａ1 ＝ { a,b } Ａ2 ＝ AA ＝{ aa,ab,ba,bb } Ａ3 ＝ A2A ＝{ aaa,aab,aba,abb,baa,bab,bba,bbb }
……
Ａn ＝Ａn-1A ＝ AAA……A
12
2.1 基本概念
10.符号串集合的正闭包
设A为符号串的集合，则称Ａ＋为符号串集Ａ的 正闭包．具体定义如下：
文法
字符串集合
16
2.2 .1 文法的定义
2.2.1 文法（Grammar）的定义 文法的定义
一个文法G是一个四元组: G = ( VN, VT, S, P )
其中：
➢ VT (Terminal Vocabulary)是一个非空的有限集合，
它的每个元素称为终极符号或终极符，一般用小 写字母表示。 从语法分析的角度看，终极符号是 一个语言不可再分的基本符号。
可合并为一个，缩写为:
P 1 | 2 | … | n
其中，每个i 称为 P 的一个候选式，符号“|” 读作“或” 。
21
⑥一个文法的核心是产生式。 一般约定:
用< >括起来或 大写字母：非终结符 不用< >括起来或小写字母：终结符
22
例1
G =（VN,VT, S, P） 其中：VN={ S , A}

编译原理―第2章 前后文无关文法和语言课件

编译原理―第2章 前后文无关文法和语言课件
?一组终结符号不能被替换的符号单词符号?一组非终结符号能够被替换为终结符号或非终结符号语法单位?一个开始符号从这个符号开始替换最大语法单位程序?一组产生式替换规则把左边的字符串替换为右边的字符串222文法和语言的形式定义19?关键思路?从文法的开始符号出发?反复使用产生式对非终结符进行替换展开?直到整个字符串中不再包含非终结符?这时得到了这个文法的一个句子一个程序?这个过程称为推导222文法和语言的形式定义20?文法的形式定义?产生式规则?产生式是一个有序对通常写作或
符号串集合的方幂： 设A是符号串的集合，则称Ai为符号串集A的 方幂，其中i是非负整数。具体定义如下：
A0 ={ε} A1 =A, A2=AA Ak= AA......A(k个)
11
2.2.1 基本概念和术语
集合的闭包
闭包
集合Σ的闭包Σ*定义如下：Σ*=Σ0∪Σ1∪Σ2∪Σ3∪… 例：设有字母表Σ={0,1}，则
从文法的开始符号出发 反复使用产生式，对非终结符进行替换（展开） 直到整个字符串中不再包含非终结符 这时，得到了这个文法的一个句子（一个程序） 这个过程称为推导
19
2.2.2 文法和语言的形式定义
文法的形式定义
产生式（规则）
产生式是一个有序对(α, β)，通常写作α→β（或α::=β）
Σ*=Σ0∪Σ1∪Σ2∪…={ε,0,1,00,01,10,11,000,…}，即Σ*表示Σ上所有有穷长 的串的集合。
正闭包
Σ+ = Σ1∪Σ2∪Σ3∪…称为Σ的正闭包。 +表示上的除ε外的所有用穷长串的集合。
Σ*= Σ0∪Σ+ Σ+=ΣΣ*=Σ*Σ
12
2.2.1 基本概念和术语
例题 定义标识符是由字母开头、后跟字母或数字的任意组合构成， 设A={a,b,…,z}，B={0,1,…,9}，将所有标识符的集合用A和B的运算 来表示。

《编译原理》第2章 编译基础-形式语言与有穷自动机

整理课件
句型、推导
G[E]： E→E+T|T T→T*F|F F→(E)|a
对于句子a+a*a 有不同 的推导
EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a
EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a
整理课件
例：奇偶测试器
0
0
1
q0
q1
∈
1
自动机：Ｍ＝（Q，∑ ，δ ，q0，Z）
Q＝｛ q0, q1}
∑ ={0,1}
q0=q0 Z={q1}
整理课件
映射函数：
δ（ q０,０)= q０ 0
0
δ（ q０,１)= q１
1
δ（ q1,０)= q１ q0
q1
δ（ q1,１)= q０
1
例：０００１１０００１
整理课件
第四节 正规文法与有穷自动机 1、正规文法 产生的语言的推导 例：文法 G=（VN，VT，P，S） 其中： VN={A，B，C}
VT={a,b,c} S=A P:A →aB A →aA
B →bB B →bC C →cC C →c
整理课件
A=>aA=>aaA=>…..=>aa…aB =>aa…abB=>aa…abb…bC =>aa…abb…bcC=> aa…abb…bccC => aa…abb…bcc…c
D→ε
Aa→bD
自然语言属于上下文有关文法
整理课件
文法的类型

编译原理chapter2


•12
{ A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 }
L D, LD, L6, L*, L(L D )*, D+
2.2 词法记号的描述与识别
2.2.2 正规式 正规式用来表示简单的语言，叫做正规集 正规式 定义的语言 {} {a} 备注
•13
2.1 词法记号及属性
2.1.3 词法错误
词法分析器对源程序采取非常局部的观点 难以发现下面的错误 fi (a == f (x) ) … 在实数是a.b格式下，可以发现下面的错误 123. 紧急方式的错误恢复 错误修补
•9
回顾
源程序 词法分析器 记号 (token) 取下一个记号 符号表
•25
delim
开始 delim other 22 *
20
21
2.3
有 限 自 动 机
•26
语言的识别是一个程序，它取串x作为输入，当x是语言句子 的时候，它回答“是”，否则回答“不是”。可以通过构造 称为有限自动机的更一般的转换图，把正规式翻译成识别器 。 有限自动机分为确定和不确定两种情况。“不确定”的含义 是，存在这样的状态，对于某个输入符号，它存在不止一种 转换。 确定和不确定的有限自动机能识别的语言正好是正规式所能 a 表达的语言。
•6
for
relation id
for
< , < = , = , … sum, count, D5 “seg. error”
字符f,o,r
< 或 <= 或 = 或 … 由字母开头的字母数字串
number
literal
3.1, 10, 2.8 E12
任何数值常数

编译原理chapter2 语言的基本知识

10
2.2 文法和语言的定义
2 . 2 . 1 引子 2 . 2 . 2 文法和语言的定义 一. 文法和语言的定义 二. 推导 三. 语言 四. 最左推导和最右推导 五。短语，直接短语，句柄
11
引子 分析：The grey wolf will eat the goat
〈句子〉
〈主语〉
〈谓语〉
〈冠词〉〈形容词〉〈名词〉 〈动词〉 〈直接宾语〉
7
三.符号串的运算 1.连接：设x和y是符号串，它们的连接 xy 是把y的符号写在x的符号之后得到的符号 串。例如，x=ba,y=nana,xy=banana.
2.方幂：x0= ; x1=x; x2=xx;
……;xn=xn-1x;
例如, x=ba,
x1= ba, x2=baba, x3=bababa,…...
3
2.1.1 字母表
字母表是符号的非空有穷集合。任何程序
语言都有自己的字母表，例如:
1.计算机语言：由符号“0”和“1”组成
的字
母表,∑={0，1}
2. ASCII字符集；
3. Pascal字母表为： ∑=
{AZ, az, 09, +, -, *, /, <, =, >,
:, ',', ; ，.， , (, ), {, }, [, ] }
直接宾语 ， 助动词 ，动词原形 } 语法规则集P={句子 主语谓语，……} 开始符号S= 句子
14
句子根据规则推导出来
句子主语 谓语
冠词 形容词 名词 谓语
the 形容词 名词 谓语
the grey名词 谓语
the grey wolf 谓语
the grey wolf 动词 直接宾语

编译原理 第二章


词法分析程序GETSYM将完成下列任务：
(1) 滤空格：空格在词法分析时是一种不可缺少的界符，而在语法分析时则是 无用的，所以必须滤掉。 (2) 识别保留字：设有一张保留字表。对每个字母打头的字母、数字字符串要 查此表。若查着则为保留字，将对应的类别放在SYM中。如IF对应值IFSYM，THEN 对应值为THENSYM。若查不着，则认为是用户定义的标识符。 (3) 识别标识符：对用户定义的标识符将IDENT放在SYM中，标识符本身的值放 在ID中。 (4) 拼数：当所取单词是数字时，将数的类别NUMBER放在SYM中，数值本身的值 存放在NUM中。 (5) 拼复合词：对两个字符组成的算符如：＞=、∶=、＜= 等单词，识别后将 类别送SYM中。 (6) 输出源程序：为边读入字符边输出(可输出在文件中)。
(1) 说明部分的分析
对每个过程（包括主程序，看成一个主过程）的说明对象造名字表TABLE，填写登录 所在的层次、标识符的属性和分配的相对位置。登录信息是调用ENTER过程完成的。 说明部分的处理对主程序看成是第0层过程，主程序定义的过程为第1层，随着嵌套 的深度增加而层次数加大。PL/0允许最大层次为3。 所造名字表放在全程量一维数组TABLE表中。TX为索引表的指针，表中的每个元素 为记录型数据。LEV给出层次，DX给出每层局部量当前已分配到的相对位置，可称地址 指示器，每说明完一个变量后DX指示器加1。 例如：
2.5 PL/0编译程序的目标代码结构和代码生成
编译程序的目标代码是在分析程序体时生成的，在处理说明部分时并不 生成目标代码，而当分析程序体中的每个语句时，当语法正确则调用目标代 码生成过程以生成与PL/0语句等价功能的目标代码，直到编译正常结束。 PL/0编译程序所产生的目标代码是一个假想栈式计算机的汇编语言，可 称为类PCODE指令代码，它不依赖任何具体计算机，其指令集极为简单，指令 格式也很单纯，其格式如下：
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2014年6月12日12时3分
2.2 高级语言的一般特性
高级语言的分类： (1)强制式的高级语言（也称过程式语言） 其特点是命令驱动，面向语句。一个强制式语言程序由一 系列的语名组成，每个语句的执行引起若干存储单元中的 值的改变。许多广为使用的语言，如FORTRAN、C、 PASCAL，ADA等等，属于这类语言。
2014年6月12日12时3分
语法分析树与二义性
用一张图表示一个句型的推导，这种表示称为语法分析树， 或简称语法树。语法树有助于理解一个句子语法结构的层 次。语法树的根结由开始符号所标记。随着推导的展开， 当某个非终结符被它的某个候选式所替换时，这个非终结 符的相应结就产生出下一代新结，候选式中自左至右的每 个符号对应一个新结，并用这些符号标记其相应的新结。 每个新结和其你结间都有一条连线。在一棵语法树生长过 程中的任何时刻，所有那些没有后代的端末结自左至右排 列起来就是一个句型。
人们已经证明，二义性问题是不可判定的。即，不存在一 个算法，它能在有限步骤内，确切地判定一个文法是否为 二义的。我们所能做的事是为无二义性寻找一组充分条件。
2014年6月12日12时3分
例如对于算术表达式文法G[E]关于(i*i+i)的语法树如下图 所示。 E
(
E E i * E i
E
+ E i
)
2014年6月12日12时3分
例如，字符串 0.5*X1+C 是一个表达式，其中常数0.5,标 识符X1和C，以及算符*和+称为语言的单词符号，而表达 式0.5*X1+C称为语言的一个语法单位，或语法范畴。 词法规则是指单词符号的形成规则。在现今多数程序语言 中，单词符号一般包括：关键字、标识符、运算符、界符 和常量等等。正规式和有限自动机理论是描述词法结构和 进行词法分析的有效工具。
2014年6月12日12时3分
例2.7写一个文法G, 使其语言为 不以0开头的奇数集。
不以0开头的奇数集数字的结构分为三种：一位数、两位 数和多位数。
A B A 一位数 两位数
B
C
„
C
A
多位数
2014年6月12日12时3分
其中，A代表可以出现在个位上的数字，可以是1，3，5， 7，9； B代表可以出现在开始位上的数字，除了0以外，其他数字 都可以；
2014年6月12日12时3分
E => E*E =>E+E*E =>i+E*E =>i+i*E =>i+i*i
对于算术表达式文法G[E]，若规定运算符号的优先级，并 服从左结合性，可以构造无二义性文法G’[E]： E→E+T E→T T→T*F T→F F→(E) F→i
2014年6月12日12时3分
2014年6月12日12时3分
2.3 程序语言的语法描述
•设是一个有穷字母表，它的每个元素称为一个符号。 上的一个字符串是指中的符号所构成的一个有穷序列。 不包含任何符号的序列称为空字，记为。 •用*表示上的所有符号串的全体，空字也包括在内。
•*的子集U和V的（连接）积定义为 UV={ | U & V}。注意： UV≠VU 但 (UV)W=U(VW)
2014年6月12日12时3分
语法规则是指语法单位的形成规则。下文无关文法用来描 述一个程序语言的语法规则。 语言的词法规则和语法 规则定义了程序的形式结构，是判断输入字符串是否构成 一个形式上正确（即合式）程序的依据。 对一个语言来说，不仅要给出它的词法、语法规则，而且 要定义它的单词符号和语法单位的意义。离开语义，语言 只不过是一堆符号的集合。所谓一个语言的语义是这样的 一组规则，使用它可以定义一个程序的意义。这些规则称 为语义规则。阐明语义要比阐明语法难的多，现在还没有 一种形式系统描述语义。
L(G)={α|S α & α ∈VT* } 例如对于文法G[E]，字符串(i+i*i)是句子。因为 E (E) (E+E) (E+E*E) (i+E*E) (i+i*E) (i+i*i) 是从开始符E至(i+i*i)的一个推导。而E ，(E)，(E+E)， (E+E*E)，(i+E*E) ，(i+i*E)，(i+i*i)是句型。
一个上下文无关文法G包括四个组成部分：一组终结符集， 一组非终结符集，一个开始符，以及一组产生式。 G=(VT, VN, S, P) VT：终结符集，即程序语言中的单词符号。 VN：非终结符集, 用来代表语法范畴。 VN∩VT= φ S：开始符号，一个特殊的非终结符，代表程序。
2014年6月12日12时3分
编译原理
主讲教师:雷向东
2014年6月12日12时3分
第二章 高级语言及其语法描述
2.1程序语言的定义
一个程序语言是一个记号系统，包括语法和语义两个方面 定义。
任何语言程序都可看成是一定字符集（称字母表）上的一 字符串（有限序列）。所谓一个语言的语法是在指这样一 组规则，用它可以形成和产生一个合式的程序。这些规则 的一部分称为词法规则，另一部分称为语法规则。
基于规则的语言程序的执行过程是：检查一定的条件，当 它满足时，则执行适当的运作。最有代表性的基于规则语 言是PROLOG，它也称逻辑程序设计语言。
2014年6月12日12时3分
(4)面向对象的高级语言 面向对象语言的主要特征是支持封装性、继承性和多态性 等。把复杂的数据和用于这些数据的操作封装在一起，构 成对象；对简单对象进行扩充、继承简单对象的特性，从 而设计出复杂的对象。通过对象的构造可以使面向对象程 序获得强制式语言的有效性，通过作用于规定数据的函数 的构造可以获得应用式语言的灵活性和可靠性。
P:一组产生式。一个产生式的形式是 A→α A是非终结符，称为产生式的左部。 α是由终结符和非终结符组成的符号串，称为产生式的右 部。 为了书写方便，有如下约定： 第一条产生式的左部是开始符号。用尖括号括起的是非终 结符，否则为终结符。或者大写字母表示非终结符，小 写字母表示终结符。用 α ， β ， γ 等代表由终结符和非 终结符组成的符号串。G可写成G[S]，S是开始符号。
2014年6月12日12时3分
若干个左部相同的产生式， 例如 A→α1 A→α2 … A→αn
可合并为一个，简写为 A→α1|α2|… |αn
2014年6月12日12时3分
假设要定义一类含+、* 的算术表达式，表达式的递归定 义为 表达式+表达式是表达式 表达式*表达式是表达式 (表达式)是表达式 函数、变量、常量是表达式
2014年6月12日12时3分
文法的二义性和语言的二义性是两个不同的概念。我们可 能有两个不同的文法G和G’，其中一个是二义的，而另一 个是无二义的，但是却有L(G)=L(G’)，也就是说，这两个 文法所产生的语言是相同的。对于一个程序语言来说，常 常希望它的文法是无二义的。因为，我们希望对它的每个 语句的分析是唯一的。
•V自身的n次积记为：Vn=VV…V (n次重复），规定 V0={} 。 令 V*=V0 V1 V2 … ， 称V*为V的闭包。 记V+=V V*，称V+为V的正则闭包。
2014年6月12日12时3分
上下文无关文法 文法是描述语言的的语法结构的形式规则 (即语法规则)。
所谓上下文无关文法是这样一种文法，它所定义的语法范 畴(语法单位)是完全独立于这种范畴可能出现的环境的。
2014年6月12日12时3分
(2)应用式的高级语言 应用式语言更注重程序所表示的功能，而不是一个语句接 一个语句地执行。程序的开发过程是从前面已有的函数出 发构造出更复杂的函数，对初始数据集进行操作直至最终 的函数可以用于从初始数据计算出最终的结果。这种语言 也称函数式语言。LISP和ML属于这种语言。 (3)基于规则的高级语言
与文法G2[S]： S→0S1|01 等价。
2014年6月12日12时3分
最左推导
所谓最左推导是指：任何一α β都是对α中的最左非终 结符进行替换。
最右推导 所谓最右推导是指：任何一步α β都是对α中的最右非终 结符进行替换。
例如对于算术表达式文法G[E]句子(i*i+i)的最右推导
E (E) (E+E) (E+i) (E*E+i) (E*i+i) (i*i+i)
L(G2)={ambn|m,n≥1} 例2.3 构造一个文法G3，使得 L(G3)={anbn|n≥1} 文法G3[S]: S→aSb | ab
2014年6月12日12时3分
例2.6 写一文法G6，使其语言为 L(G6)={ωcωR|ω ∈ (a|b)* & ωR 代表ω的逆} 文法G6[S]: S→aSa|bSb|c
2014年6月12日12时3分
一步或多步推导“”
+
+
用“”表示：从α1出发，经过一步或多步，可推导出αn。 零步或多步推导“”
* 用“ ”表示：从α1出发，经过零步或多步，可推导出 * αn。 *
2014年6月12日12时3分
文法的句型、句子的定义
+ 假设G 是一个文法，S是它的开始符。如果S α，则称α 是一个句型。仅含终结符的句型是句子。文法G 所产生 句子的全体是一个语言，将它记为L(G)。
2014年6月12日12时3分
用E代表表达式，i代表函数、变量、常量，因此，文法定 义为G[E] E→E+E E→E*E
E→(E)
E→ i
可简写为：
E→E+E|E*E|(E)|i
2014年6月12日12时3分
推导的定义
直接推导“”
αAβ αγβ 仅当A→γ是文法G的产生式，且α、β∈（VT∪VN）* 例如对于文法G[E]的字符串(i+i*i)的推导： E (E) (E+E) (E+E*E) (i+E*E) (i+i*E) (i+i*i)