编译原理第2章(刘磊 机械工业出版社)
- 格式：ppt
- 大小：763.00 KB
- 文档页数：6
下载文档原格式
合集下载
编译原理第2章(刘磊 机械工业出版社)
={a,b, aa,ab,ba,bb, aaa,aab,aba,abb,baa,bab,bba,bbb, ……}
定义２．11 符号串集合的星闭包
设A是符号串集合，则称 A*是符号串集合A的 星闭包。具体定义为： A*= A0 A1A2 A3 …… 例如:设A={a,b} A*= A0 A1A2 A3 ……
定义２．8 符号串集合的乘积
设A、B是两个符号串的集合， AB表示A与B 的乘积，定义为:
AB={xy|xA yB} 例如 A={a,bc}, B={de,f} AB={ade,af,bcde,bcf} 注意：{}A=A{}=A
A=A =
定义２．9 符号串集合的方幂
设A是符号串集合，则称 Ai是符号串集合A 的方幂，其中i〉=0。具体定义为： A0={} A1=A A2=AA …… An=AAA……A（n 个A）
例文法G= （VN，VT，P，S） 其中： VN ={S,A,B}, VT ={0，1} P为: S—>0A ,S1B ,S—>0 ,
A—>0A ,A1B ,A—>0S ,
B—>1B , B—>0 ,B—>1 为3型文法。
设文法G=（VN，VT，P，S），如果它的每一 个产生式的形式都是A—>B或A —> , 其中A、B VN , VT ， 则G是一个3型文法。（左线性） 3型文法对应有限自动机.
文法间关系
0型文法 1型文法 2型文法 3型文法
２．１．３ 推导和归约
文法的语言：从文法的开始符号出发，对当前产 生式右部符号串中的非终极符替换为相应产生式 右部的符号，如此反复，直至最终符号串全由终 极符号组成。如此得到的终极符号串的全体，就 是文法所产生的语言。
定义２．11 符号串集合的星闭包
设A是符号串集合，则称 A*是符号串集合A的 星闭包。具体定义为： A*= A0 A1A2 A3 …… 例如:设A={a,b} A*= A0 A1A2 A3 ……
定义２．8 符号串集合的乘积
设A、B是两个符号串的集合， AB表示A与B 的乘积，定义为:
AB={xy|xA yB} 例如 A={a,bc}, B={de,f} AB={ade,af,bcde,bcf} 注意：{}A=A{}=A
A=A =
定义２．9 符号串集合的方幂
设A是符号串集合，则称 Ai是符号串集合A 的方幂，其中i〉=0。具体定义为： A0={} A1=A A2=AA …… An=AAA……A（n 个A）
例文法G= （VN，VT，P，S） 其中： VN ={S,A,B}, VT ={0，1} P为: S—>0A ,S1B ,S—>0 ,
A—>0A ,A1B ,A—>0S ,
B—>1B , B—>0 ,B—>1 为3型文法。
设文法G=（VN，VT，P，S），如果它的每一 个产生式的形式都是A—>B或A —> , 其中A、B VN , VT ， 则G是一个3型文法。（左线性） 3型文法对应有限自动机.
文法间关系
0型文法 1型文法 2型文法 3型文法
２．１．３ 推导和归约
文法的语言：从文法的开始符号出发，对当前产 生式右部符号串中的非终极符替换为相应产生式 右部的符号，如此反复，直至最终符号串全由终 极符号组成。如此得到的终极符号串的全体，就 是文法所产生的语言。
编译原理 课后答案 机械工业出版社
第二章练习2.1解答：(a) 终结符号为：{(,),a,,,}非终结符号为：{S,L}开始符号为：S(b)① (a,a) ②(a,(a,a)) ③ (a,((a,a),(a,a)))(c) ① (a,a)S (L) (L,S) (S,S) (a,S) (a,a)② (a,(a,a))S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S))(a,(S,S)) (a,(a,S)) (a,(a,a))③ (a,((a,a),(a,a)))S (L) (L,S) (S,S) (a,S) (a,(L)) (a,(L,S))(a,(S,S)) (a,((L),S)) (a,((L,S),S)) (a,((S,S),S))(a,((a,S),S)) (a,((a,a),S)) (a,((a,a),(L)))(a,((a,a),(L,S))) (a,((a,a),(S,S))) (a,((a,a),(a,S)))(a,((a,a),(a,a)))(d) ① (a,a)S (L) (L,S) (L,a) (S,a) (a,a)②(a,(a，a))S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,a))(L,(S,a)) (L,(a,a)) (S,(a,a)) (a,(a,a))③(a，((a，a)，(a，a)))S (L) (L,S) (L,(L)) (L,(L,S)) (L,(L,(L)))(L,(L,(L,S))) (L,(L,(L,a))) (L,(L,(S,a)))(L,(L,(a,a))) (L,(S,(a,a))) (L,((L),(a,a)))(L,((L,S),(a,a))) (L,((L,a),(a,a))) (L,((S,a),(a,a)))(L,((a,a),(a,a))) (S,((a,a),(a,a))) (a,((a,a),(a,a)))(e) L(G[S]) = (α1,α2,...,αn)或a其中αi(1≤i≤n)是L(G[S])。
[高等教育]编译原理与技术讲义-第2章_OK
![[高等教育]编译原理与技术讲义-第2章_OK](https://img.taocdn.com/s1/m/20305b646bec0975f565e261.png)
在终结状态加了星号*，表示 在状态1、2和3都还不能确定 它们是否是符合最长匹配准则 的单词记号，还需要在读入一 个字符才能确定。
而为实现最长匹配的一个超前 搜索符号“其它”则不属于这 个单词，应该推给扫描缓冲区。
other
< =
0 >
1> = other
2 =
= 3
other
* 4 5 6
* 7 8 9
2021/8/18
6
2.1 词法分析器的设计
<1，’for’>
<3，’<=’>
例2.1：假如保留字的编码是1， 标识符的为2，运算符为3，分 界符为4，整型常量为10，实型 常量为11。那么，对于源程序 代码：
<4，’(’>
<10，’100’>
<2，指向i的符号表入口> <4，’;’>
<3，’=’>
编译原理与技术
第2章 词法分析
2021/8/18
1
主要内容
• 词法分析器的设计 • 词法分析器的一种手工实现 • 正规表达式 • 有限自动机 • 词法分析的自动生成器Lex
2021/8/18
2
词法分析器在编译中的位置
源程序
词法分 析器
单词 取下一个单词
语法分 析器 单词记号
符号表
2021/8/18
digit
1 digit
． 3
+, －
other
2
digit
E
digit
digit 4
E 5
6 +,
7
8
digit
digit
而为实现最长匹配的一个超前 搜索符号“其它”则不属于这 个单词，应该推给扫描缓冲区。
other
< =
0 >
1> = other
2 =
= 3
other
* 4 5 6
* 7 8 9
2021/8/18
6
2.1 词法分析器的设计
<1，’for’>
<3，’<=’>
例2.1：假如保留字的编码是1， 标识符的为2，运算符为3，分 界符为4，整型常量为10，实型 常量为11。那么，对于源程序 代码：
<4，’(’>
<10，’100’>
<2，指向i的符号表入口> <4，’;’>
<3，’=’>
编译原理与技术
第2章 词法分析
2021/8/18
1
主要内容
• 词法分析器的设计 • 词法分析器的一种手工实现 • 正规表达式 • 有限自动机 • 词法分析的自动生成器Lex
2021/8/18
2
词法分析器在编译中的位置
源程序
词法分 析器
单词 取下一个单词
语法分 析器 单词记号
符号表
2021/8/18
digit
1 digit
． 3
+, －
other
2
digit
E
digit
digit 4
E 5
6 +,
7
8
digit
digit
计算机语言的实现-编译原理-01-(二)
1.4 编译程序的生成方法
设计目标 目标程序小，执行速度快。 编译程序小，执行速度快。 诊断能力强，可靠性强。 可移植性，可扩充性。
表示翻译程序的 T 型图
S I
源语言
T
目标语言 翻译用 语言
1）交叉编译
条件：
Ａ
机有 Ｃ 语言的编译程序 Ｂ 机的 Ｃ 语言的编译
目的：
实现
编译后端
1. 2.
多遍扫描
程序设计环境
集成化的程序设计环境
编辑程序 编译程序 连接程序
----- 将目标程序连接成可执行程序 调试工具 ----- 跟踪、分析
常见：
Turbo
C/C++ Visual Studio for C/C++, Basic 等 JBuilder, BlueJ
1. 用 Ｃ语言编制Ｃ编译程序（CP1.C） 2. Ａ机器上编译该程序，得到（CP1.EXE) 3. 在A机器上，运行CP1.EXE编译CP1.C， 得到B机的C编译程序（CP2.EXE）。
C 语言 CP1.C C语言
B 代码 C语言 C编译 （A机）
C 语言 CP1.C A目标 CP1.EXE
B 代码
1.3 编译技术的通用性
把复杂数据看作一条语句 数据格式的分析
利用词法分析、语法分析方法
数据处理的框架
基于语法制导的语义处理框架 编译技术可以用于各种复杂数据的分 析处理
例1-1（1/2）
DOS 命令 date 的输出格式
例：9-2-1993、09-03-1993、9-03-93
语法
date → month - day - year
编译原理―第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的运算 来表示。
符号串集合的方幂： 设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章习题解答1.文法G[S]为：S->Ac|aBA->abB->bc写出L(G[S])的全部元素。
[答案]S=>Ac=>abc或S=>aB=>abc所以L(G[S])={abc}==============================================2. 文法G[N]为：N->D|NDD->0|1|2|3|4|5|6|7|8|9G[N]的语言是什么？[答案]G[N]的语言是V+。
V={0,1,2,3,4,5,6,7,8,9}N=>ND=>NDD.... =>NDDDD...D=>D......D===============================================3.已知文法G[S]：S→dAB A→aA|a B→ε|bB问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案]正规式是daa*b*；相应的正规文法为(由自动机化简来)：G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε===================================================================== ==========4.已知文法G[Z]：Z->aZb|ab写出L(G[Z])的全部元素。
[答案]Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbbL(G[Z])={a n b n|n>=1}===================================================================== =========5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。
编译原理第2章
湖南农业大学信息科学技术学院 王 奕
E →E + E E →E*E E →i E → (E)
表示一个文法时, 表示一个文法时,通常只给出开始符号和 产生式,如上例,可表示为: 产生式,如上例,可表示为: G(E): G(E): E → i | E+E | E*E | (E)
湖南农业大学信息科学技术学院 王 奕
湖南农业大学信息科学技术学院 王 奕
例如,一组产生式 A→0 A→1 A→A 0 A→A 1 描述的语言序列只可能是由0和1组成的符号串,即 ∑+ ={0,1,00,01,10,000,100,…}.
湖南农业大学信息科学技术学院 王 奕
2. 文法
定义2.1:一个前后文无关文法G 定义2.1:一个前后文无关文法G是一个四元式 2.1
湖南农业大学信息科学技术学院 王 奕
文法的形式定义
1. 规则 规则也称产生式,它是一个符号与一个符号串的 有序对(A,β),通常写做 A→β(或A::=β) 其中,A是规则左部,它是一个符号;β是规则 右部,它是一个符号串;"→"和"::="表示"定义 为"或"生成",意思是左部符号用右部的符号串定 义或左部符号生成右部符号串.
湖南农业大学信息科学技术学院 王 奕
对形式语言的描述有两种方法 : ⑴ 当语言为有穷集合时,用枚举方法来表示语言: 例如:设有字母表A={a,b,c},则 L1={a,b,c} L2={a,aa,ab,ac} L3={c,cc} 均表示字母表A上的一个形式语言. ⑵ 对无穷集合的语言,需要设计文法来描述:
一个上下文无关文法如何定义一个语言集合呢?其中心思 一个上下文无关文法如何定义一个语言集合呢? 想是:从文法的开始符号出发,反复连续使用产生式, 想是:从文法的开始符号出发,反复连续使用产生式,对 非终结符实行替换和展开. 非终结符实行替换和展开.
编译原理编译原理02-授课文档PDF_2_2
视频区域
标识符与名字
标识符
以字母开头的，由字母数字组成的字符串
名字
标识程序中的对象
视频区域
Jordan
binding
标识符
名字
绑定
视频区域
标识符与名字
名字的意义和属性
值：单元中的内容
属性：类型和作用域
名字的说明方式
视频区域
由说明语句来明确规定的
int score
描述数据和对数据的运算
视频区域
程序的层次结构
程序 |
子程序或分程序、过程、函数 |
语句 |
表达式 |
数据引用 运算符 函数调用
视频区域
程序语言成分的逻辑和实现意义
抽象的逻辑的意义
数学意义
计算机实现的意义
具体实现
计算思维与数学思维 视频区域 的不同
编译原理
高级程序设计语言概述 ——高级程序设计语言的一般特性
视频区域
测试
下面哪些属于程序语言的语义定义？ ( A. 表达式中圆括号必须匹配 B. 类的声明必须以class开头 C. 关于函数调用时参数传递方法的描述 D. 函数体必须用return语句结尾
)
视频区域
程序语言的基本功能和层次结构
程序，本质上说是描述一定数据的处理过程
程序语言的基本功能
K.Nygaard 视频区域O. Dahl
John Cocke (1987) -- RISC & 编译优化
O. Dahl，K.Nygaard (2001) -- Simula语言和OO概念
Alan Kay(2003) -- SmallTalk语言和面向对象程序设计
编译原理第二章
二义文法： G(E)： E i|E+E|E*E|(E)
无二义文法：
G(E)：E T | E+T T F | T*F F (E) | i
表达式 项|表达式+项 项 因子 | 项*因子 因子 (表达式) | i
2.3.2 语法分析树与二义性
消除二义性：
E
E
E*E
E +E
i
E
+
E
E
*
E i
G(E)： E i|E+E|E*E|(E) 是二义文法。
语言的二义性：一个语言是二义性的，如果对它 不存在无二义性的文法。
可能存在G和G’，一个为二义的，一个为无二义的。 但L(G)=L(G’)
二义性问题是不可判定问题，即不存在一个算法， 它能在有限步骤内，确切地判定一个文法是否是 二义的。
可以找到一组二义文法的充分条件。
i
i
i
i
用一种层次观点看待表达式
按照优先集和结合性
2021/3/30
29
2.3.2 语法分析树与二义性
E
用一种层次观点看待表达式
i*i+i
i * (i + i)
i * (i * i + i)
T
i * i * (i + i) + i * i + i
F
取消二义性的文法
i
E T | E + T
T F | T * F
程序设计语言不是上下文无关语言，甚至 不是上下文有关语言。
L7={c| (a|b)*}不能由上下文无关文 法产生，甚至连上下文有关文法也不能产 生，只能由0型文法产生。
现今程序设计语言的语言结构，用上下文 无关文法描述就足够了。
编译原理 第二章 机械工业出版社
第二章部分习题答案2.1 考虑文法S→S S + | S S * | aa)证明文法可生成符号串 a a + a *解：S→S S * →S S + S * →a S + S * → a a + S *→ a a + a *b)为此符号串构造语法树解：c)文法生成什么样的语言？证明结论解：将a看作运算数，文法生成语言L={支持加法、乘法的表达式的后缀表示形式} 证明类似2.2题b)＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝2.2 下列文法生成什么样的语言？证明你的结论。
是否有二义性？a)S →0 S 1 | 0 1解：生成语言L={0n1n | n>=1}证明：1) 证文法推导出的符号串都在L中i)考虑最小语法树，推导出的符号串01显然∈Lii)假定结点数<n的语法树对应的符号串都∈L，考虑结点数=n的语法树S，其结构必为，子树S1结点数<n，因此对应符号串t1∈L，S对应符号串为t=0 t1 1，因此t∈L综合i)、ii)，1)得证2) 证L中符号串都可由文法推导出i)L中最短符号串01，显然可由文法推导出ii)假定L中长度<2n的符号串都可由文法推导出，考虑长度=2n的符号串t＝0n1n，它可表示为0 t1 1，t1∈L且长度<2n ，因此它可被文法推导出，对应语法树，构造语法树，显然，它的输出为t，即t可被文法推导出综合i)、ii)，2)得证综合1)、2)，文法生成的语言即为L另外，文法没有二义性＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝b)S →+ S S | - S S | a解：生成语言L={支持加法、减法的表达式的前缀表示形式}证明：1) 证文法推导出的符号串都在L中i)考虑最小语法树，推导出的符号串a显然∈Lii)假定结点数<n的语法树对应的符号串都∈L，考虑结点数=n的语法树S ，其结构必为，子树S1、S2结点数<n，因此对应符号串E1、E2∈L（前缀表达式），S对应符号串为E=+/- E1 E2，E也是前缀表达式。
编译原理(第四版)第2章词法分析
词法分析器 / 扫描器 ：执行词法分析的程序
词法分析可以采用如下两种处理结构： (1) 把词法分析程序作为主程序。将词法分析工作作为独立 的一遍来完成，即把词法分析与语法分析明显分开，由词法分析 程序将字符串形式的源程序改造成单词符号串形式的中间程序， 以这个中间程序作为语法分析程序的输入。在这种处理结构中， 词法分析和语法分析是分别实现的，如图2–1(a)所示。 (2) 把词法分析程序作为语法分析程序调用的子程序。在进 行语法分析时，每当语法分析程序需要一个单词时便调用词法分 析程序，词法分析程序每一次调用便从字符串源程序中识别出一 个单词交给语法分析程序。在这种处理结构中，词法分析和语法 分析实际上是交替进行的，如图2–1(b)所示。 由于把词法分析器安排成一个子程序比较自然，因此，词法 分析程序通常采用第二种处理结构。
2.1 词法分析器设计方法
状态（即结点）数是有限的，其中必有一初始状态以及若 干终止状态，终止状态（终态）的结点用双圈表示以区别于其 它状态。
标识符
无符号整数
无符号数
2.1 词法分析器设计方法
某些终止状态是在读入了一个其它不属于 该单词的符号后才得到相应的单词编码的，这 表明在识别单词的过程中多读入了一个符号， 所以识别出单词后应将最后多读入的这个符号 予以回退；我们对此类情况的处理是在终态上 以“*”作为标识。
2.2.2 C语言子集对应的状态转换图
在设计的状态转换图中，首先对输入串做预处理，即剔除多 余的空白符(在实际的词法分析中，预处理还包括剔除注释和制表 换行符等编辑性字符的工作)，使词法分析工作既简单又清晰。其 次，将保留字作为一类特殊的标识符来处理，也即对保留字不专 设对应的状态转换图，当转换图识别出一个标识符时就去查对表 2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个 保留字表来进行处理。
词法分析可以采用如下两种处理结构： (1) 把词法分析程序作为主程序。将词法分析工作作为独立 的一遍来完成，即把词法分析与语法分析明显分开，由词法分析 程序将字符串形式的源程序改造成单词符号串形式的中间程序， 以这个中间程序作为语法分析程序的输入。在这种处理结构中， 词法分析和语法分析是分别实现的，如图2–1(a)所示。 (2) 把词法分析程序作为语法分析程序调用的子程序。在进 行语法分析时，每当语法分析程序需要一个单词时便调用词法分 析程序，词法分析程序每一次调用便从字符串源程序中识别出一 个单词交给语法分析程序。在这种处理结构中，词法分析和语法 分析实际上是交替进行的，如图2–1(b)所示。 由于把词法分析器安排成一个子程序比较自然，因此，词法 分析程序通常采用第二种处理结构。
2.1 词法分析器设计方法
状态（即结点）数是有限的，其中必有一初始状态以及若 干终止状态，终止状态（终态）的结点用双圈表示以区别于其 它状态。
标识符
无符号整数
无符号数
2.1 词法分析器设计方法
某些终止状态是在读入了一个其它不属于 该单词的符号后才得到相应的单词编码的，这 表明在识别单词的过程中多读入了一个符号， 所以识别出单词后应将最后多读入的这个符号 予以回退；我们对此类情况的处理是在终态上 以“*”作为标识。
2.2.2 C语言子集对应的状态转换图
在设计的状态转换图中，首先对输入串做预处理，即剔除多 余的空白符(在实际的词法分析中，预处理还包括剔除注释和制表 换行符等编辑性字符的工作)，使词法分析工作既简单又清晰。其 次，将保留字作为一类特殊的标识符来处理，也即对保留字不专 设对应的状态转换图，当转换图识别出一个标识符时就去查对表 2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个 保留字表来进行处理。
廖力编译原理课件第2章
1、文法 • 其语法规则如下： – <句子>→<主语><谓语> – <主语> →<形容词><名词> – <谓语> →<动词><宾语> – <宾语> → <形容词><名词> – <形容词> →Young | pop – <名词> →men | music – <动词> →like
第二章 基础知识 16
第二章 基础知识 3
2.0 编译基础知识（续）
二、语法 1、单词符号 – 语言中具有独立意义的最基本结构。 • 词法规则 – 词法规则规定了字母表中那些字符串是单词符号。 – 单词符号一般包括：常数、标识符、基本字、算 符、界限符等。 – 我们用正规式和有限自动机理论来描述词法结构 和进行词法分析。
第二章 基础知识 13
2.2
文法与语言的关系
第二章 基础知ቤተ መጻሕፍቲ ባይዱ 14
2.2 文法与语言的关系 一、文法的概念
1、文法 文法是描述语言的语法结构的形式规则。 • 例如：我们写这样一个句子： – Young men like pop music.
第二章 基础知识 15
2.2 文法与语言的关系 一、文法的概念
第二章 基础知识 17
2.2 文法与语言的关系 一、文法的概念
2、相关概念 • (3)开始符号 – 表示所定义的语法范畴的非终结符。 – 注：开始符号又称为识别符号。 • (4)产生式 – 是用来定义符号串之间关系的一组(语法)规则。 – 形式：A → α （A产生α ）
第二章 基础知识 18
2.2 文法与语言的关系 一、文法的概念
第二章 基础知识 16
第二章 基础知识 3
2.0 编译基础知识（续）
二、语法 1、单词符号 – 语言中具有独立意义的最基本结构。 • 词法规则 – 词法规则规定了字母表中那些字符串是单词符号。 – 单词符号一般包括：常数、标识符、基本字、算 符、界限符等。 – 我们用正规式和有限自动机理论来描述词法结构 和进行词法分析。
第二章 基础知识 13
2.2
文法与语言的关系
第二章 基础知ቤተ መጻሕፍቲ ባይዱ 14
2.2 文法与语言的关系 一、文法的概念
1、文法 文法是描述语言的语法结构的形式规则。 • 例如：我们写这样一个句子： – Young men like pop music.
第二章 基础知识 15
2.2 文法与语言的关系 一、文法的概念
第二章 基础知识 17
2.2 文法与语言的关系 一、文法的概念
2、相关概念 • (3)开始符号 – 表示所定义的语法范畴的非终结符。 – 注：开始符号又称为识别符号。 • (4)产生式 – 是用来定义符号串之间关系的一组(语法)规则。 – 形式：A → α （A产生α ）
第二章 基础知识 18
2.2 文法与语言的关系 一、文法的概念
编译原理 chapter2
（4）简单句和复合句
作业： P35 3，4
Copyright：张捷
以上内容是对高级语言中为编译原理 课程所关心特性的总结
Copyright：张捷
2.3
几个概念：
程序语言的语法描述
设是一个有穷字母表；
符号：中每个元素称为一个符号。 符号串：是指由中的符号所构成的有穷序列。 空字：不包含任何符号的序列称为空字，记为。 *：表示上的所有符号串的全体，也包括在其中。
2. 标识符和名字
标识符 由字母或数字组成的以字母开头的一个字符串， 是一个没有意义的字符序列。 名字 有明确的意义和属性的字符串。 值、属性 一个名字的属性包括类型和作用域
名字的类型决定它能具有什么样的值，值在计算机内的表示 形式，以及对它能施加什么运算。 作用域表示值的存在范围。
Copyright：张捷
Copyright：张捷
注意这里提到三个概念： a.字母表构成程序语言的有限字符集 b.词法规则是指单词符号的形成规则。单词符号 一般包括：各类型的常数、标识符、基本字、算 符和界符等。单词符号是语言中具有独立意义的 最基本结构。 c.语法规则规定了如何从单词符号形成更大的结 构（即语法单位），换言之，语法规则是语法单 位的形成规则。一般程序语言的语法单位有：表 达式、语句、分程序、函数、过程和程序等。
Copyright：张捷
2.2.2、程序结构 一、FORTRAN 语言 由一个主程序段和若 干个辅程序段组成 PROGRAM MAIN … END SUBROUTINE SUB1 … END … SUBROUTINE SUBn … END 辅程序段可以是子程序、函数段或数据块
Copyright：张捷
第二章
高级语言及其语法描述
作业： P35 3，4
Copyright：张捷
以上内容是对高级语言中为编译原理 课程所关心特性的总结
Copyright：张捷
2.3
几个概念：
程序语言的语法描述
设是一个有穷字母表；
符号：中每个元素称为一个符号。 符号串：是指由中的符号所构成的有穷序列。 空字：不包含任何符号的序列称为空字，记为。 *：表示上的所有符号串的全体，也包括在其中。
2. 标识符和名字
标识符 由字母或数字组成的以字母开头的一个字符串， 是一个没有意义的字符序列。 名字 有明确的意义和属性的字符串。 值、属性 一个名字的属性包括类型和作用域
名字的类型决定它能具有什么样的值，值在计算机内的表示 形式，以及对它能施加什么运算。 作用域表示值的存在范围。
Copyright：张捷
Copyright：张捷
注意这里提到三个概念： a.字母表构成程序语言的有限字符集 b.词法规则是指单词符号的形成规则。单词符号 一般包括：各类型的常数、标识符、基本字、算 符和界符等。单词符号是语言中具有独立意义的 最基本结构。 c.语法规则规定了如何从单词符号形成更大的结 构（即语法单位），换言之，语法规则是语法单 位的形成规则。一般程序语言的语法单位有：表 达式、语句、分程序、函数、过程和程序等。
Copyright：张捷
2.2.2、程序结构 一、FORTRAN 语言 由一个主程序段和若 干个辅程序段组成 PROGRAM MAIN … END SUBROUTINE SUB1 … END … SUBROUTINE SUBn … END 辅程序段可以是子程序、函数段或数据块
Copyright：张捷
第二章
高级语言及其语法描述
编译原理课后习题解答(2)
1／7
西北大学 Gong Xq
龙书本科教学版习题解答
仅供教学参考
解答： 1）L={0n1n | n>=1} 证明：①考虑，推导 1 步时，有 S 01 推导 2 步时， S 0S1 0011 以此类推，推导 n 步时，S 0S1 00S11 ... 0...0S1...1 0...01...1 可以得到 n 个 0 和 n 个 1 ②对任意串 0n1n 都存在一个推导 S ... 0...01...1
1）证明：对语法分析树的结点数目使用数学归纳法。 ①归纳基础：当语法分析树有两个结点时，形如
num
num
11
1001
生成的串分别为 11 和 1001，表示的值为 3 和 9，能被 3 整除。 ②归纳步骤：假设语法分析树的结点数目少于 n 时生成的二进制串的值能被 3 整除，那么当 结点数目等于 n 时，语法分析树的根有下面两种可能的形式：
3／7
西北大学 Gong Xq
龙书本科教学版习题解答
仅供教学参考
解答： 1）S → SS+ | SS* | SS- | SS/ | id | num 2）list → list, id | id 3）list → id, list | id 4）E → E + T | E – T | T
T→T*F|T/F|F F → id | num | (E) 5）E → E + T | E – T | T T→T*F|T/F|F F → -E | +E | id | num | (E)
2）文法生成以 a 为基本运算分量的+和-运算的前缀表达式。证明略。
3）文法生成具有对称括号对的串。证明略。
4）文法生成 a 和 b 的个数相等的串。 证明：用关于 a 和 b 个数的归纳法证明。 ①归纳基础：一步推导时，S ϵ，其中 a 和 b 的个数都为 0。 ②归纳步骤：设 S 经过少于 n 步推导得到的串 α 中 a 和 b 的个数相等； 则>=n 步的推导形如 S aSbS … x 或 S bSaS … y aSbS 和 bSaS 中的 S 经过少于 n 步能推出终结符号串，且其中 a 和 b 的个数都相等； 所以经过 aSbS 和 bSaS 推导出的 x 和 y 中的 a 和 b 个数也相等。证毕。
编译原理课件PPT 第2章
Chapter 2 Language & Syntax Description Section 2 Grammar & Language 1、Basic concepts a、Grammar Grammar is the formal production rules describing the construction of syntax elements. Notes：1) Syntax elements include sentences and words in sentences, a language is composed of sentences. 2) The form of a production rule is as following: left-sideright-side (that can be read as ―leftside is defined as right-side‖, ―left-side derives right-side‖,or ―left-side produces right-side‖, it expresses the relation between the two sides)
Chapter 2 Language & Syntax Description Section 2 Grammar & Language 1、Basic concepts j、Extended notations of grammar rules Use extended BNF(Backus Naur Form) notations
Chapter 2 Language & Syntax Description Section 2 Grammar & Language 1、Basic concepts b、Non-terminal symbol – A symbol that appears in the left of a rule , is bracketed in <> and expresses a syntax concept. – A set of non-terminal symbols is expressed in VN c、Terminal symbol – Strings in a language that cannot be decomposed (including strings of single characters), expressed in VT. Notes：Terminal symbols are basic elements of a sentence.
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
A VN ， （ VN∪ VT）* ，则G是 一个2型文法。 2型文法对应非确定的下推自动机（PDA）.
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 为1型文法或上下文有关文法。
２．3型文法（线型文法、正则文法、正规文法
设文法G=（VN，VT，P，S），如果它的 每一个产生式的形式都是A—> B或A —> , 其中A、B VN , VT ， 则G是一个3型文法。（右线性） 3型文法对应有限自动机.
定义２．5 前缀和后缀
设z=xy是字符串. x是z的前缀.y是z的后缀. 如果 y <> , x是z的真前缀. 如果 x<>, y是z的真后缀 例如： z =101 z的前缀有: ,1,10,101, z的真前缀有: ,1,10, z的后缀有: ,1, 01,101, z的真后缀有,1, 01,
定义２．6 子字符串
V=S,W=0011, 直接推导序列 V=S=〉 0S1=〉0011=W，即V=>*W
定义2．15 最左推导
如果在推导的过程中，总是对当前符号串中的最 左边的非终结符进行替换，则称最左推导。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个最左推导序列：
１．０型文法（短语文法）
设G=（VN，VT，P，S），如果对它的每 一个产生式 —> 不加任何限制， 则G是一 个0型文法（短语文法）。 0型文法对应图灵机.（TM ）
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1}
P={S—>0S1,S01} 为0型文法。
２．１型文法(上下文有关文法)
定义2．13 直接推导
如 —> 是文法G=（VN，VT，P，S）的一条 产生式，
、（ VN VT ）＊, 若有符号串v,w满足:
v= , w= , 则说v(应用规则α —>β )直接推导出w, 或说,w是v的直接推导, 或说,w直接归约到v, 记作v=>w.
定义2．14 直接推导序列
例如 文法G= （VN，VT，P，S）， 其中VN={S}，
VT={0，1}， P={S0S1, S01}.
２．１．２ 文法的分类
乔姆斯基于1956年建立形式语言的描述， 对程序设计语言的设计、编译方法和计算复杂 性等方面有重大作用。
他把文法分为四类：0型、1型、2型和3型。 这几类文法的差别在于对产生式施加不同 的限制。
第二章 形式语言与自动机理论基础 2．１语言和文法
２．１．１ 基本概念
形式化语言：具有语法严格、结构正规、便于计算机处理
的特点。 一个程序设计语言是一种形式化语言。其核心是语法和
语义。
语法：一组规则，是语言的形式。 语义：是语言的内容。
静态语义：一系列规则，确定哪些合乎语法的程序
是合适的。
动态语义：表明程序要做什么，要计算什么。
定义 ２．１ 字母表
字母表:元素的非空有穷集合. 符号:字母表中的元素. 符号表:字母表. 字母表的表示符号：
定义２．２ 符号串
符号串:由字母表中的符号组成的任何有穷序列.其中符号 的顺序是很重要的. 例如:字母表∑={0,1},00,11,10,01,100 是它上的符号串. 注意:01和10是不同的两个符号串. 符号串的表示:可以使用字母表示符号串.如X=100 符号串的长度:符号串X中字符的个数m,用|X|=m表示. 空符号串:用ε 表示, | ε |=0.
定义２．8 符号串集合的乘积
设A、B是两个符号串的集合， AB表示A与B 的乘积，定义为:
AB={xy|xA yB} 例如 A={a,bc}, B={de,f} AB={ade,af,bcde,bcf} 注意：{}A=A{}=A
A=A =
定义２．9 符号串集合的方幂
设A是符号串集合，则称 Ai是符号串集合A 的方幂，其中i〉=0。具体定义为： A0={} A1=A A2=AA …… An=AAA……A（n 个A）
子字符串:一个非空字符串x,删去它的前缀和后 缀所得的字符串.简称子串. 如果删去的前缀和后缀不同时为,称该子串为 真子串. 例如：x=101 子串有:101,10,1,01,0, 真子串有: 10,1,01,0,
定义２．7 符号串集合
字符串集合:若集合A中的一切元素是某字母表 上的符号串. 例如:={1,0},A={0,1,10,00}
S=>S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa 故S、 aAS、aSbAS、aabAS、aabbaS、aabbaa都
是文法G的句型
定义2．18 句子
设G是一文法， S是文法的开始符号，如果有S=> * , VT * 则 是文法G的句子。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个推导序列： S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa VT *
2．1．４语法树与文法的二义性
定义 ２．２２语法树
设文法G是给定的文法，称满足下列条件的树为G的一棵 语法树。
（1）每个节点都标有G的一个文法符号，且根节点标有初 始符S，非叶节点标有非终结符．
（2）若一节点A有n的儿子节点B1，B2，…，Bn (从左到右 的次序),则A—> B1B2…，Bn 一定是G中的一个产生式。
文法间关系
0型文法 1型文法 2型文法 3型文法
２．１．３ 推导和归约
文法的语言：从文法的开始符号出发，对当前产 生式右部符号串中的非终极符替换为相应产生式 右部的符号，如此反复，直至最终符号串全由终 极符号组成。如此得到的终极符号串的全体，就 是文法所产生的语言。
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 该文法的语言是０n１ n
S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa
定义2．16 最右推导
如果在推导的过程中，总是对当前符号串中的最 右边的非终结符进行替换，则称最右推导。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个最右推导序列：
设文法G中的任一产生式A —> , 其中 A VN， 、 （ VNVT ）＊ ，
（ VNVT ）+ 则G是一个1型文法。 1型文法对应线性界限机（LBA).
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 为1型文法或上下文有关文法。
故aabbaa是文法G的句子。
定义2．19 短语
设G是一文法， S是文法的开始符号， 是文法G的一个
句型,如果有:
S=> * A
并且
A=>+ 则称 是句型 相对于A 的短语。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个推导序列： S=> aAS=>aSbAS => aabAS=>aabbaS abba是句型aSbAS相对于A的直接短语。
={ ,a,b, aa,ab,ba,bb, aaa,aab,aba,abb,baa,bab,bba,bbb, ……}
定义２．12 文法
文法G定义为四元组（VN，VT，P，S）。 其中VN为非终结符集, VN非空有穷集
VT为终结符集,VT非空有穷集 VN VT = , V= VN VT P为产生式， P为非空有穷集 S为开始符号或识别符号，是一个非终结符， 至少在一条规则中作为左部出现。
语法树的构造举例。
G= （{S，A}，{a,b},P，S）其中P为：
(1) S—>aAS (2) A—>SbA (3) A—>SS (4) S—>a
一棵语法树为： S
a
A
S
(5) A—>ba
S bA a
a
ba
句型aabbaa的语法树。
文法G:E->E+E|E*E|(E)|i 对句子i*i+i的推导过程如下： 推导1:E=>E+E=>E*E+E=>i*E+E=>i*i+E=>i*i+i 推导2:E=>E*E=>i*E=>i*E+E=>i*i+E=>i*i+ i
定义２．３符号串的连接
连接:符号串x和y,他们的连接是把y的字符写在 x的字符之后. 例如：x=101,y=010 他们的连接xy=101010 |xy|=|x|+|y|=3+3=6
定义２．4 符号串的方幂
方幂:符号串x,把自身连接n次得到的符号串z, z=xxxx…;记为xn
X0= X1=X 例如：X=101 X0= X1=101 X2=101101 X3=101101101
例文法G= （VN，VT，P，S） 其中： VN ={S,A,B}, VT ={0，1} P为: S—>0A ,S1B ,S—>0 ,
A—>0A ,A1B ,A—>0S ,
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 为1型文法或上下文有关文法。
２．3型文法（线型文法、正则文法、正规文法
设文法G=（VN，VT，P，S），如果它的 每一个产生式的形式都是A—> B或A —> , 其中A、B VN , VT ， 则G是一个3型文法。（右线性） 3型文法对应有限自动机.
定义２．5 前缀和后缀
设z=xy是字符串. x是z的前缀.y是z的后缀. 如果 y <> , x是z的真前缀. 如果 x<>, y是z的真后缀 例如： z =101 z的前缀有: ,1,10,101, z的真前缀有: ,1,10, z的后缀有: ,1, 01,101, z的真后缀有,1, 01,
定义２．6 子字符串
V=S,W=0011, 直接推导序列 V=S=〉 0S1=〉0011=W，即V=>*W
定义2．15 最左推导
如果在推导的过程中，总是对当前符号串中的最 左边的非终结符进行替换，则称最左推导。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个最左推导序列：
１．０型文法（短语文法）
设G=（VN，VT，P，S），如果对它的每 一个产生式 —> 不加任何限制， 则G是一 个0型文法（短语文法）。 0型文法对应图灵机.（TM ）
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1}
P={S—>0S1,S01} 为0型文法。
２．１型文法(上下文有关文法)
定义2．13 直接推导
如 —> 是文法G=（VN，VT，P，S）的一条 产生式，
、（ VN VT ）＊, 若有符号串v,w满足:
v= , w= , 则说v(应用规则α —>β )直接推导出w, 或说,w是v的直接推导, 或说,w直接归约到v, 记作v=>w.
定义2．14 直接推导序列
例如 文法G= （VN，VT，P，S）， 其中VN={S}，
VT={0，1}， P={S0S1, S01}.
２．１．２ 文法的分类
乔姆斯基于1956年建立形式语言的描述， 对程序设计语言的设计、编译方法和计算复杂 性等方面有重大作用。
他把文法分为四类：0型、1型、2型和3型。 这几类文法的差别在于对产生式施加不同 的限制。
第二章 形式语言与自动机理论基础 2．１语言和文法
２．１．１ 基本概念
形式化语言：具有语法严格、结构正规、便于计算机处理
的特点。 一个程序设计语言是一种形式化语言。其核心是语法和
语义。
语法：一组规则，是语言的形式。 语义：是语言的内容。
静态语义：一系列规则，确定哪些合乎语法的程序
是合适的。
动态语义：表明程序要做什么，要计算什么。
定义 ２．１ 字母表
字母表:元素的非空有穷集合. 符号:字母表中的元素. 符号表:字母表. 字母表的表示符号：
定义２．２ 符号串
符号串:由字母表中的符号组成的任何有穷序列.其中符号 的顺序是很重要的. 例如:字母表∑={0,1},00,11,10,01,100 是它上的符号串. 注意:01和10是不同的两个符号串. 符号串的表示:可以使用字母表示符号串.如X=100 符号串的长度:符号串X中字符的个数m,用|X|=m表示. 空符号串:用ε 表示, | ε |=0.
定义２．8 符号串集合的乘积
设A、B是两个符号串的集合， AB表示A与B 的乘积，定义为:
AB={xy|xA yB} 例如 A={a,bc}, B={de,f} AB={ade,af,bcde,bcf} 注意：{}A=A{}=A
A=A =
定义２．9 符号串集合的方幂
设A是符号串集合，则称 Ai是符号串集合A 的方幂，其中i〉=0。具体定义为： A0={} A1=A A2=AA …… An=AAA……A（n 个A）
子字符串:一个非空字符串x,删去它的前缀和后 缀所得的字符串.简称子串. 如果删去的前缀和后缀不同时为,称该子串为 真子串. 例如：x=101 子串有:101,10,1,01,0, 真子串有: 10,1,01,0,
定义２．7 符号串集合
字符串集合:若集合A中的一切元素是某字母表 上的符号串. 例如:={1,0},A={0,1,10,00}
S=>S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa 故S、 aAS、aSbAS、aabAS、aabbaS、aabbaa都
是文法G的句型
定义2．18 句子
设G是一文法， S是文法的开始符号，如果有S=> * , VT * 则 是文法G的句子。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个推导序列： S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa VT *
2．1．４语法树与文法的二义性
定义 ２．２２语法树
设文法G是给定的文法，称满足下列条件的树为G的一棵 语法树。
（1）每个节点都标有G的一个文法符号，且根节点标有初 始符S，非叶节点标有非终结符．
（2）若一节点A有n的儿子节点B1，B2，…，Bn (从左到右 的次序),则A—> B1B2…，Bn 一定是G中的一个产生式。
文法间关系
0型文法 1型文法 2型文法 3型文法
２．１．３ 推导和归约
文法的语言：从文法的开始符号出发，对当前产 生式右部符号串中的非终极符替换为相应产生式 右部的符号，如此反复，直至最终符号串全由终 极符号组成。如此得到的终极符号串的全体，就 是文法所产生的语言。
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 该文法的语言是０n１ n
S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa
定义2．16 最右推导
如果在推导的过程中，总是对当前符号串中的最 右边的非终结符进行替换，则称最右推导。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个最右推导序列：
设文法G中的任一产生式A —> , 其中 A VN， 、 （ VNVT ）＊ ，
（ VNVT ）+ 则G是一个1型文法。 1型文法对应线性界限机（LBA).
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 为1型文法或上下文有关文法。
故aabbaa是文法G的句子。
定义2．19 短语
设G是一文法， S是文法的开始符号， 是文法G的一个
句型,如果有:
S=> * A
并且
A=>+ 则称 是句型 相对于A 的短语。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个推导序列： S=> aAS=>aSbAS => aabAS=>aabbaS abba是句型aSbAS相对于A的直接短语。
={ ,a,b, aa,ab,ba,bb, aaa,aab,aba,abb,baa,bab,bba,bbb, ……}
定义２．12 文法
文法G定义为四元组（VN，VT，P，S）。 其中VN为非终结符集, VN非空有穷集
VT为终结符集,VT非空有穷集 VN VT = , V= VN VT P为产生式， P为非空有穷集 S为开始符号或识别符号，是一个非终结符， 至少在一条规则中作为左部出现。
语法树的构造举例。
G= （{S，A}，{a,b},P，S）其中P为：
(1) S—>aAS (2) A—>SbA (3) A—>SS (4) S—>a
一棵语法树为： S
a
A
S
(5) A—>ba
S bA a
a
ba
句型aabbaa的语法树。
文法G:E->E+E|E*E|(E)|i 对句子i*i+i的推导过程如下： 推导1:E=>E+E=>E*E+E=>i*E+E=>i*i+E=>i*i+i 推导2:E=>E*E=>i*E=>i*E+E=>i*i+E=>i*i+ i
定义２．３符号串的连接
连接:符号串x和y,他们的连接是把y的字符写在 x的字符之后. 例如：x=101,y=010 他们的连接xy=101010 |xy|=|x|+|y|=3+3=6
定义２．4 符号串的方幂
方幂:符号串x,把自身连接n次得到的符号串z, z=xxxx…;记为xn
X0= X1=X 例如：X=101 X0= X1=101 X2=101101 X3=101101101
例文法G= （VN，VT，P，S） 其中： VN ={S,A,B}, VT ={0，1} P为: S—>0A ,S1B ,S—>0 ,
A—>0A ,A1B ,A—>0S ,