【精选】编译原理2.3.1-2-符号与符号串4

编译原理及实现课后习题解答2.1设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5 以及A+和A*.x0=(aaa)0=ε| x0|=0xx=aaaaaa |xx|=6x5=aaaaaaaaaaaaaaa | x5|=15A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…}A* = A0 ∪A1 ∪A2 ∪…. ∪A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3xy=abcb |xy|=4xyz=abcbaab |xyz|=7(xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=122.3设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。

S => SS* => Sa* => SS+a* => Sa+a* => aa+a*SS S *S S + aa a2.4 已知文法G[Z]：Z∷=U0∣V1 、U∷=Z1∣1 、V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。

Z=>U0=>Z10=>U010=>1010Z=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5已知文法G[S]：S∷=AB A∷=aA︱εB∷=bBc︱bc , 写出该文法描述的语言。

A∷=aA︱ε描述的语言: {a n|n>=0}B∷=bBc︱bc 描述的语言：{b n c n|n>=1}L(G[S])={a n b m c m|n>=0,m>=1}2.6已知文法E∷=T∣E+T∣E-T 、T∷=F∣T*F∣T/F 、F∷=(E)∣i，写出该文法的开始符号、终结符号集合V T、非终结符号集合V N。

编译原理文法类型介绍辽宁师范大学 王 欣自1956年，乔姆斯基建立了形式语言的描述，使得形式语言的理论发展得十分迅速。

形式语言的理论不仅对计算机科学有着深远的影响，也对编译方法、程序设计语言的设计等方面有着更重大的作用。

乔姆斯基将文法分为0型，1型，2型，3型，本文重点介绍这四种文法的分类与判别条件。

1 文法说明文法G定义为一个四元组（V N，V T，P，S）（肖军模，程序设计语言编译方法：大连理工大学出版社，1991；何炎祥，伍春香，计算机专业不需要编译原理课程吗：计算机教育，2009）：V N表示非终结符集合，非终结符集合包括大写字母、语法实体、变量、小写的斜体字符串及用字母表示的开始符号等。

V T表示终结符集合，终极符包括小写英文字母、数字及不用尖括号括起来的是终极符。

P表示为产生式（α→β）的集合，满足条件且其中至少要包含一个非终结符，，其中（α→β）的意义为α定义为β。

S是一个终极符，作为文法的开始符号，又称作标识符，要求S至少要作为P其中一条产生式的左部出现。

要求V N，V T，P都为非空的有穷集合（冯博琴，编译原理辅助教程：西安交通大学出版社，1995）。

2 文法类型介绍2.1 0型文法2.1.1 0型文法定义设文法，若文法中的每一个产生式都满足条件并且其中至少要包含一个非终结符，同时满足，那么可判定G为一个0型文法（张志红，朱晨光，编译原理中的文法及二义性研究：河南科技，2009）。

例如：2.1.2 0型文法说明0型文法又可被称为短语文法，0型文法的充分必要条件为递归可枚举集必然是一个0型文法。

图灵机等价于0型文法。

图灵机是一个抽象的机器，将一个无限长的纸条分割成一块块小格，且每个小格所表示的颜色不同，机器头在纸带上来回移动，每次读入一个当前的方格信息，结合内部程序将结构输出到纸带方格上，然后移动到其他的方格，继续上述过程。

2.2 1型文法2.2.1 1型文法定义设文法，如果P产生式集合中的每一个产生式（α→β）都满足条件，仅除外，那么当前文法G为1型文法。

编译原理复习指南前四章占70分，后三章占30分。

【新复习范围如下】第二章：2.3, 2.13, 2.14第三章：3.2，3.3，3.10，3.16第四章：4.3，4.10，4.13第五章：5.4，5.6第六章：6.3， 6.10， 6.11第七章：7.1， 7.2第二章2.3 叙述由下列正规式描述的语言。

（1）0(0|1)*0（2）((ε|0)1*)*（3）(0|1)*0(0|1)(0|1)（4）0*10*10*10*（5）(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*解：其中一种表述(这里说的01串包括ε)（1）0(0|1)*0 以0开头和结尾的长度至少是2的01串（2）((ε|0)1*)* 所有的01串（3）(0|1)*0(0|1)(0|1) 倒数第三位是0的01串（4）0*10*10*10* 含有3个1的01串（5）(00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 含有偶数个0和偶数个1的01串2.13构造表示0，1个数都是偶数的01字符串的DFA。

2.14构造DFA，识别{0,1}上能被5整除的二进制数。

解：已读过尚未读已读部分的值某时刻 101 0111000 5读进0 1010 111000 5 ⨯ 2 = 10读进1 10101 11000 10 ⨯ 2 + 1= 21读进2 101011 1000 21 ⨯ 2 + 1= 43读进3 1010111 000 43 ⨯ 2 + 1= 875个状态即可，分别代表已读部分的值除以5的余数第三章3.2考虑文法S->aSbS|bSaS|ε(a) 为句子abab构造两个不同的最左推导，以说明此文法二义。

(b) 为abab构造对应的最右推导。

(c) 为abab构造对应的分析树。

(d) 这个文法产生的语言是什么？解：(a) 最左推导：(1) S=>aSbS=>abS=>abaSbS=>ababS=>abab(2) S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab(b)最右推导：(1) S=>aSbS=>aSbaSbS =>aSbaSb=>aSbab =>abab(2) S=>aSbS=>aSb=>abSaSb=>abSab =>abab(c) 描述的语言是：a,b数目相等的串3.3下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法。

编译原理⼀些习题答案第2章形式语⾔基础2.2 设有⽂法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语⾔是什么?(2)给出句⼦0123和268的最左推导和最右推导。

解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ? ND ? NDD ? NDDD ? DDDD ? 0DDD ? 01DD ? 012D ? 0123 0123的最右推导：N ? ND ? N3 ? ND3 N23 ND23 N123 D123 0123268的最左推导：N ? ND ? NDD ? DDD ? 2DDD ? 26D ? 268268的最右推导：N ? ND ? N8 ? ND8 ? N68 ? D68 ? 2682.4 写⼀个⽂法，使其语⾔是奇数的集合，且每个奇数不以0开头。

解答：⾸先分析题意，本题是希望构造⼀个⽂法，由它产⽣的句⼦是奇数，并且不以0开头，也就是说它的每个句⼦都是以1、3、5、7、9中的某个数结尾。

如果数字只有⼀位，则1、3、5、7、9就满⾜要求，如果有多位，则要求第1位不能是0，⽽中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个⽂法分3部分来完成。

分别⽤3个⾮终结符来产⽣句⼦的第1位、中间部分和最后⼀位。

引⼊⼏个⾮终结符，其中，⼀个⽤作产⽣句⼦的开头，可以是1－9之间的数，不包括0，⼀个⽤来产⽣句⼦的结尾，为奇数，另⼀个则⽤来产⽣以⾮0整数开头后⾯跟任意多个数字的数字串，进⾏分解之后，这个⽂法就很好写了。

N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下⾯⽂法⽣成的语⾔是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ? bcB ? bBc? bbccB ? bBc? bbBcc ? bbbccc……A ?εA ? aA ? aA ? aA ? aaA ? aa……∴S ? AB ? a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ? a S ? aA ? aaS ? aaaS ? aA ? aaS ? aaaA ?aaaaS ? aaaaa ……∴S ? a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知⽂法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。

编译原理第四章答案1. 介绍编译原理是计算机科学中一门重要的课程，它涵盖了编译器设计与实现的基本知识和技术。

本文将针对编译原理第四章的问题进行详细解答。

第四章主要讨论了词法分析的相关内容，包括正则表达式和有限自动机。

2. 正则表达式正则表达式是一种表示字符串模式的方法。

它由一些字符和操作符组成，用于描述一类字符序列的模式。

正则表达式通常用于文本搜索、匹配和替换操作中。

2.1 正则表达式的基本操作符正则表达式的基本操作符包括字符、连接、选择和重复。

•字符：可以是单个字符，例如a、b、c。

•连接：用于连接两个正则表达式，例如ab表示在字符串中同时出现a和b。

•选择：用于在多个正则表达式中选择一个，例如a|b表示字符串中可以是a或者b。

•重复：用于指定某个正则表达式的重复次数，例如a*表示a可以出现任意次数（包括 0 次）。

2.2 正则表达式的语法正则表达式的语法规则如下：•字符：表示一个字符。

•.：表示任意字符。

•[]：表示字符集合，匹配括号内的任意一个字符。

•[^]：表示字符集合的补集，匹配除了括号内的字符之外的任意字符。

•-：表示范围，例如[a-z]匹配任意小写字母。

•*：表示重复零次或多次。

•+：表示重复一次或多次。

•?：表示重复零次或一次。

•()：表示分组。

2.3 正则表达式的应用正则表达式在编译原理中的应用非常广泛。

在词法分析中，正则表达式可以用来描述编程语言中的单词（token）和它们的模式。

编译器可以使用正则表达式作为词法分析器的输入，用于将源代码分解为不同的单词。

3. 有限自动机有限自动机（Finite Automaton，FA）是一种用于描述正则语言的理论模型。

它是一种数学模型，包括有限个状态和状态之间的转移。

根据输入的字符，自动机会从一个状态转移到另一个状态。

3.1 有限自动机的组成有限自动机由以下几个部分组成：•有限个状态：每个状态表示自动机在某个时刻的状态。

•输入符号集合：表示自动机接受的输入字符集合。

编译原理符号表1. 引言编译原理是计算机科学领域中一个重要的研究方向，它研究的是将高级语言程序转化为机器语言的过程。

在编译器中，符号表是一种常用的数据结构，用于存储程序中的各种符号及其相关信息。

本文将深入探讨编译原理符号表的概念、作用、设计方法以及常见的符号表实现方式。

2. 符号表的概念和作用2.1 符号表的定义符号表是编译器中用于存储程序中各种符号信息的数据结构。

它一般由编译器自动生成和维护，用于支持语法分析、语义分析和代码生成等编译过程。

2.2 符号表的作用符号表在编译器的各个阶段都发挥着重要的作用：•语法分析阶段：符号表用于识别和存储各种变量、函数和类型的声明信息，以支持后续的语义分析过程。

•语义分析阶段：符号表用于检查变量和函数的引用是否合法，并记录其类型信息和作用域等属性，以支持类型检查和语义约束的验证。

•代码生成阶段：符号表用于存储中间代码和目标代码中的符号引用和符号定义的映射关系，以支持代码生成和目标代码优化等过程。

3. 符号表的设计方法3.1 符号表的数据结构符号表的数据结构通常由符号表项组成，每个符号表项用于存储一个符号及其相关信息。

常见的符号表项包括符号名称、符号类型、作用域、内存地址等。

3.2 符号表的组织方式符号表的组织方式可以有多种选择，常见的包括线性表、哈希表、树和图等。

选择合适的组织方式可以提高符号表的查询效率和插入删除的性能。

3.3 符号表的查询算法符号表的查询算法是指根据给定的符号名称，在符号表中进行查找并返回对应的符号表项。

常见的查询算法有线性搜索、二分搜索和哈希搜索等，选择合适的查询算法可以提高符号表的查询效率。

4. 常见的符号表实现方式4.1 线性表实现线性表实现是符号表最简单的一种实现方式，它可以使用数组或链表来存储符号表项。

线性表实现的优点是简单易懂，缺点是查询效率较低，随着符号表规模的增大，性能下降明显。

4.2 哈希表实现哈希表实现是一种常用的符号表实现方式，它通过哈希函数将符号名称映射到符号表项存储的位置。

编译原理实验⼆：LL（1）语法分析器⼀、实验要求 1. 提取左公因⼦或消除左递归（实现了消除左递归） 2. 递归求First集和Follow集 其它的只要按照课本上的步骤顺序写下来就好（但是代码量超多...），下⾯我贴出实验的⼀些关键代码和算法思想。

⼆、基于预测分析表法的语法分析 2.1 代码结构 2.1.1 Grammar类 功能：主要⽤来处理输⼊的⽂法，包括将⽂法中的终结符和⾮终结符分别存储，检测直接左递归和左公因⼦，消除直接左递归，获得所有⾮终结符的First集，Follow集以及产⽣式的Select集。

#ifndef GRAMMAR_H#define GRAMMAR_H#include <string>#include <cstring>#include <iostream>#include <vector>#include <set>#include <iomanip>#include <algorithm>using namespace std;const int maxn = 110;//产⽣式结构体struct EXP{char left; //左部string right; //右部};class Grammar{public:Grammar(); //构造函数bool isNotTer(char x); //判断是否是终结符int getTer(char x); //获取终结符下标int getNonTer(char x); //获取⾮终结符下标void getFirst(char x); //获取某个⾮终结符的First集void getFollow(char x); //获取某个⾮终结符的Follow集void getSelect(char x); //获取产⽣式的Select集void input(); //输⼊⽂法void scanExp(); //扫描输⼊的产⽣式，检测是否有左递归和左公因⼦void remove(); //消除左递归void solve(); //处理⽂法，获得所有First集，Follow集以及Select集void display(); //打印First集,Follow集,Select集void debug(); //⽤于debug的函数~Grammar(); //析构函数protected:int cnt; //产⽣式数⽬EXP exp[maxn]; //产⽣式集合set<char> First[maxn]; //First集set<char> Follow[maxn]; //Follow集set<char> Select[maxn]; //select集vector<char> ter_copy; //去掉$的终结符vector<char> ter; //终结符vector<char> not_ter; //⾮终结符};#endif 2.1.2 AnalyzTable类 功能：得到预测分析表，判断输⼊的⽂法是否是LL(1)⽂法，⽤预测分析表法判断输⼊的符号串是否符合刚才输⼊的⽂法，并打印出分析过程。

第二章2.3叙述由下列正规式描述的语言(a) 0(0|1)*0在字母表{0, 1}上,以0开头和结尾的长度至少是2的01串(b) ((ε|0)1*)*在字母表{0, 1}上,所有的01串,包括空串(c) (0|1)*0(0|1)(0|1)在字母表{0, 1}上,倒数第三位是0的01串(d) 0*10*10*10*在字母表{0, 1}上,含有3个1的01串(e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*在字母表{0, 1}上,含有偶数个0和偶数个1的01串2.4为下列语言写正规定义C语言的注释，即以 /* 开始和以 */ 结束的任意字符串，但它的任何前缀（本身除外）不以 */ 结尾。

［解答］ other → a | b | … other指除了*以外C语言中的其它字符other1 → a | b | …other1指除了*和/以外C语言中的其它字符 comment → /* other* (* ** other1 other*)* ** */(f) 由偶数个0和偶数个1构成的所有0和1的串。

［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：x 偶数个0和偶数个1（用状态0表示）； x 偶数个0和奇数个1（用状态1表示）； x 奇数个0和偶数个1（用状态2表示）； x 奇数个0和奇数个1（用状态3表示）；所以，x 状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：偶数个0和奇数个1（状态1）x 状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：奇数个0和偶数个1（状态2）x 状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：偶数个0和偶数个1（状态0）x 状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：奇数个0和奇数个1（状态3）x 状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：偶数个0和偶数个1（状态0）x 状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：奇数个0和偶数个1（状态2）x 状态3（奇数个0和奇数个1）读入0，则0和1的数目变为：偶数个0和奇数个1（状态1）因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图：由此可以写出其正规文法为：S0 → 1S1 | 0S2 | ε S1 → 1S0 | 0S3 | 1 S2 → 1S3 | 0S0 | 0 S3 → 1S2 | 0S1在不考虑S0 →ε产生式的情况下，可以将文法变形为： S0 = 1S1 + 0S2 S1 = 1S0 + 0S3 + 1 S2 = 1S3 + 0S0 + 0S3 = 1S2 + 0S1 所以： S0 = (00|11) S0 + (01|10) S3 + 11 + 00(1) S3 = (00|11) S3 + (01|10) S0 + 01 + 10(2) 解(2)式得： S3 = (00|11)* ((01|10) S0 + (01|10)) 代入(1)式得：S0 = (00|11) S0 + (01|10) (00|11)*((01|10) S0 + (01|10)) + (00|11) => S0 = ((00|11) + (01|10) (00|11)*(01|10))S0 + (01|10) (00|11)*(01|10) + (00|11) => S0 = ((00|11)|(01|10) (00|11)*(01|10))*((00|11) + (01|10) (00|11)* (01|10)) => S0 = ((00|1 1)|(01|10) (00|11)* (01|10))+因为S0→ε所以由偶数个0和偶数个1构成的所有0和1的串的正规定义为： S0 → ((00|11)|(01|10) (00|11)* (01|10))* (g) 由偶数个0和奇数个1构成的所有0和1的串。

可编辑修改精选全文完整版1.编译程序的工作过程一般可包括词法分析、语法分析、语义分析、中间代码产生与优化和目标代码生成等几个阶段，同时还有表格管理和出错处理。

2.LEX是用于词法分析的工具，Y ACC是用于语法分析的工具。

3.解释程序和编译程序的区别在于是否生成目标代码。

4.任一文法终结符集合和非终结符集合的交集是空集。

5.描述程序设计语言语法的BNF方法中，“：：=”表示定义为，“|”表示或，[W]表示W可出现0或1次，｛W｝表示W可出现n（n≥0）次。

6.已知文法G[G]: S→aSb|ab|ε，该文法描述的语言L(G)=｛a n b n|n≥0｝。

7.单词的描述工具有正规文法、正规式和有穷自动机，他们之间存在等价性。

8.高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符和界符。

9.正则式中的“|“表示或，“*”表示闭包。

10.自顶向下语法分析方法会遇到的主要问题有回溯，以及左递归带来的无限循环。

11.算符优先分析法每次归约当前句型的最左素短语，规范归约中每次归约的是当前句型的句柄。

12.对文法G[G]: S→a|b|cTc，T→S|TdS而言，FIRSTVT(T)=｛a,b,c,d｝。

13.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。

14.对文法G[G]: E→E*T|T, T→T+i|i的句子1+2*8+6进行归约后的结果为42（23，42）。

15.在LR(0),SLR(1),LR(1),LALR(1),四种文法中，描述能力最强的是LR(1)。

1.0型文法中每条规则左部至少包含一非终结符（√）。

2.3型文法一定是2型、1型、0型文法（√）。

3.对无二义性文法而言，无论最左推导还是最右推导，同一个句子的语法树是一样的。

4.若一个文法是递归的，则其语言中句子的个数必定是无穷个。

（√）5.文法规则右部的符号一定是终结符。

（×）6.语法树描述的是一个文法。