编译原理例题讲解

《编译原理》LR分析法与构造LR（1）分析表的步骤-例题解析《编译原理》LR 分析法与构造 LR(1) 分析表的步骤 - 例题解析笔记直接做题是有⼀些特定步骤，有技巧。

但也必须先了解⼀些基本概念，本篇会通过例题形式解释概念，会容易理解和记忆，以及解决类似问题。

如果只想做题可以直接下拉⾄习题部分。

（⼀）关于状态对于产⽣式 A→aBcD，就可以分解为下⾯⼏个不同的识别状态：（1）A→.aBcD（2）A→a.BcD（3）A→aB.cD（4）A→aBc.D（5）A→aBcD.“.” 的左部符号表⽰已被识别出来的那部分句柄符号状态（1）表⽰：处于句柄的头状态（2）表⽰：已经识别出字符 a，等待形成以 B 为产⽣式左部的右部状态（3）表⽰：刚刚进⾏了⼀次规约，即把关于 B 的产⽣式右部规约成 B状态（4）表⽰：已经识别出字符 c，等待形成以 D 为产⽣式左部的右部状态（5）表⽰：已经到达句柄的尾巴，可以把 aBcD 规约为产⽣式左部的符号 A（⼆）什么是 LR(k) 分析法？字⾯意思理解：字符含义L表⽰从左到右扫描输⼊串R表⽰利⽤最右分析⽅法来识别句⼦，即构造⼀个最右推导的逆过程k表⽰向右查看输⼊串符号的个数LR 分析过程是规范归约的过程规范规约是最右推导的逆过程，最右推导是规范推导，所以最左规约是规范规约。

LR 分析法根据当前分析栈中的符号串和向右顺序查看输⼊串的 k 个符号就可以唯⼀确定分析器的动作是移进还是归约、利⽤那个产⽣式进⾏归约。

当没有指明 k 是⼏的时候，默认为 1（三）⽂法的拓⼴？⽂法的拓⼴是对现有⽂法，添加⼀个 S'，并对⽂法进⾏展开。

例如：对于⽂法 G[E]:E → E+T|TT → T*F|FF → i|(E)可以把它拓⼴为⽂法 G[E']:E' → EE → E+T|TT → T*F|FF → i|(E)此时可能会有疑问，不就是加了个开始符号，有什么意义呢？为什么要再加个开始符号呢？加开始符号是为了状态的表⽰，这样原来的 S 会成为右部，可以表⽰ .S 和 S.那同⼀⾮终结符的右部有多种情况为什么不展开呢？这⾥是说拓⼴⽂法，是添加开始符号，可以展开可以不展开，但是⼀般默认要展开，⼀般⼀道题不会只让求拓⼴⽂法，⽽是为了后⾯。

《编译原理》构造LL（1）分析表的步骤-例题解析《编译原理》构造 LL(1) 分析表的步骤 - 例题解析易错点及扩展：1、求每个产⽣式的 SELECT 集2、注意区分是对谁 FIRST 集 FOLLOW 集3、开始符号的 FOLLOW 集包含 #4、各集合对对应的对象以及含义集对象含义FIRST 集是对产⽣式右部右部内部的所有终结符集，可能为εFOLLOW 集是对产⽣式左部（⾮终结符）⾮终结符后⾯紧跟的终结符，可能为 #，和该⾮终结符推导出的右部⽆关（因为LL(1)⽂法不包含递归，所以右部不会再有该⾮终结符，所以不能通过该右部判断该⾮终结符后跟集合）SELECT集是对产⽣式需要考虑产⽣式右部的不同情况，进⼀步确定是根据 FIRST 集还是 FOLLOW 集5、SELECT 集的定义注：注意区分 FIRST 集 FOLLOW 时是对α还是 A给定⽂法 G，对于产⽣式 A→α，α∈ V*，则可选集 SELECT(A→α) 有：（1）若α ≠ ε，且α ≠+> ε，则 SELECT(A→α) = FIRST(α)（2）若α ≠ ε，但α =+> ε，则 SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)（3）若α = ε，则 SELECT(A→α) = FOLLOW(A)描述：第 1 条是，当α ≠ ε，且通过1次或多次推不出ε，SELECT(A→α) = FIRST(α)第 2 条是，当α ≠ ε，但α经有限步可推出ε，SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)（注意是⼀个α，⼀个 A）第 3 条是，当α = ε，SELECT 集就等于左部 A 的 FOLLOW 集解题时，先判断是否为ε，是则⽤第（3）条，否则再判断能否通过1次或多次推出ε，是则⽤第（2）条，否则⽤第（1）条求 FIRST，FOLLOW，SELECT 集详细例题可参考：6、LL(1) 分析表的结构分析表是⼀个⼆维数组 M[A，a]，其中 A 表⽰⾏，是⾮终结符，a 表式列是终结符或 #。

在此深情而热烈的感谢沈仲秋同学的大力支持和帮助，同时希望本文档对各位有些帮助。

一1、画出编译程序的总体结构图，简述其部分的主要功能。

[答案]编译程序的总框图见下图。

图编译程序的总体结构图其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。

语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间优化器对中间代码进行优化处理。

一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码目标代码生成器把中间代码翻译成目标程序。

中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。

编译程序各个阶段所产生的中间结果都记录在表格出错处理程序对出现在源程序中的错误进行处理。

如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。

编译程2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?[答案]计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。

像Basic之类的语言，属于解释型的高级语言。

它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读总而言之，是边翻译边执行。

像C，Pascal之类的语言，属于编译型的高级语言。

它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统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+。

1. 计算以下文法的FIRST集和FOLLOW集：
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
解：首先，我们需要确定每个非终结符的FIRST集。

对于E来说，它的FIRST集是{(, E}, {+, T}；对于T来说，它的FIRST集是{*, F}, {(, E}；对于F来说，它的FIRST集是{), id}。

接下来，我们需要确定每个非终结符的FOLLOW集。

对于E来说，它的FOLLOW集是{+, $}；对于T来说，它的FOLLOW集是{$}；对于F来说，它的FOLLOW集是{$}。

2. 判断以下文法是否为LL(1)文法：
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
解：根据LL(1)文法的定义，如果一个文法是LL(1)文法，那么它必须满足以下条件：
1. 每个非终结符的FIRST集包含终结符ε。

2. 每个产生式的右部的第一个终结符α在对应的非终结符的FIRST集中。

3. 如果α是一个终结符，那么它的FOLLOW集包含ε。

4. 如果α是一个非终结符A->β，并且存在一个终结符a∈β，使得A->a是产生式，那么a不能出现在A->β中的其他符号前面。

根据以上条件，我们可以判断该文法不是LL(1)文法。

因为对于产生式E->E+T和T->T*F，它们的右部的第一个终结符+和*都不在对应的非终结符的FIRST集中。

因此，该文法不是LL(1)文法。

编译原理消除左递归例题
编译原理中消除左递归是一个重要的概念，它在文法的转换过程中起着关键作用。

让我们以一个简单的例题来说明消除左递归的过程。

假设我们有以下的文法：
A -> Aα₁ | Aα₂ | β₁ | β₂。

其中A是非终结符号，α₁、α₂、β₁、β₂是符号串。

这个文法存在左递归，因为A可以推导出A开头的符号串。

为了消除左递归，我们可以进行以下的步骤：
1. 将文法分成两部分，一部分是不含左递归的产生式，另一部分是含有左递归的产生式。

在这个例子中，我们可以将文法分成两部分：
A -> β₁ | β₂。

A -> Aα₁ | Aα₂。

2. 引入新的非终结符号。

我们为每个含有左递归的产生式引入
一个新的非终结符号，然后重写产生式。

在这个例子中，我们引入一个新的非终结符号A'，然后重写产生式：
A -> β₁A' | β₂A'。

A' -> α₁A' | α₂A' | ε。

3. 重写产生式。

我们将原来的产生式中的左递归部分替换为新引入的非终结符号。

在这个例子中，我们重写产生式为：
A -> β₁A' | β₂A'。

A' -> α₁A' | α₂A' | ε。

这样，我们就成功地消除了原文法中的左递归。

这个过程可以确保文法不会陷入无限递归的推导过程中，从而使得编译器能够准确地理解和处理文法。

消除左递归是编译原理中非常重要的一环，对于理解和设计语法分析器有着重要的意义。

编译原理典型案例1.对于文法G[S]S →(L)S→aSS→aL →L,SL→S(1) 画出句型(S,(a)) 的语法树；(2) 写出上述句型的所有短语、直接短语、句柄和素短语。

解答这类题目重点考查语法树、推导、短语、直接短语、句柄和素短语等基本概念。

在句型中寻找短语、直接短语、句柄的方法：(1) 画出句型对应的语法树。

句型(S,(a)) 的语法树如下图所示(2) 在该语法树中寻找短语、直接短语、句柄。

首先我们看短语的定义：令G是一个文法，S是文法的开始符，假设α,β,δ是文法G的句型，如果有S*⇒αAδ且 A +⇒β则称β是句型αβδ相对于非终结符A的短语。

如果有A⇒β，则称β是句型αβδ相对于规则A→β的直接短语。

一个句型的最左直接短语称为该句型的句柄。

根据短语的定义可知，以非终结符A为根的子树的叶结点从左到右排列就是相对于非终结符A的短语；如果子树只有两代，则短语就是直接短语；最左边的两代子树的所有叶结点从左到右排列，就是该句型的句柄。

素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。

处于句型最左边的素短语为最左素短语。

从语法树中我们可以找到：短语：a，S，(a)，S, (a)，(S, (a))直接短语：a，S句柄：S素短语：a2. 写一个上下文无关文法，使其语言能被5整除且不以0开头的无符号整数集合（如{5，10，15}） 解答能被5整除的数从形式上看，是以0，5结尾的数字串。

题目要求不以0开头，注意0不是该语言的句子。

句子的结构分为三种：其中，A 代表可以出现在个位上的数字，只能是0或5；B 代表可以出现在开始位上的数字，除了0以外，其他数字都可以；C 代表可以出现在中间位上的数字。

0-9所有数字都可以。

于是，A →0 | 5B →1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9C →0 | B写文法时，先描述一位数结构，于是有产生式S →5。

对于两位数和多位数，都是以B 开头和以A 结尾，于是有产生式S →DA 。

编译原理习题集与答案解析（整理后）第⼀章1、将编译程序分成若⼲个“遍”是为了。

a．提⾼程序的执⾏效率b．使程序的结构更加清晰c．利⽤有限的机器内存并提⾼机器的执⾏效率d．利⽤有限的机器内存但降低了机器的执⾏效率2、构造编译程序应掌握。

a．源程序b．⽬标语⾔c．编译⽅法d．以上三项都是3、变量应当。

a．持有左值b．持有右值c．既持有左值⼜持有右值d．既不持有左值也不持有右值4、编译程序绝⼤多数时间花在上。

a．出错处理b．词法分析c．⽬标代码⽣成d．管理表格5、不可能是⽬标代码。

a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使⽤可以定义⼀个程序的意义。

a．语义规则b．语法规则c．产⽣规则d．词法规则7、词法分析器的输⼊是。

a．单词符号串b．源程序c．语法单位d．⽬标程序8、中间代码⽣成时所遵循的是- 。

a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序是对。

a．汇编程序的翻译b．⾼级语⾔程序的解释执⾏c．机器语⾔的执⾏d．⾼级语⾔的翻译10、语法分析应遵循。

a．语义规则b．语法规则c．构词规则d．等价变换规则⼆、多项选择题1、编译程序各阶段的⼯作都涉及到。

a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析2、编译程序⼯作时，通常有阶段。

a．词法分析b．语法分析c．中间代码⽣成d．语义检查e．⽬标代码⽣成三、填空题1、解释程序和编译程序的区别在于。

2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和⽬标代码⽣成。

3、编译程序⼯作过程中，第⼀段输⼊是，最后阶段的输出为程序。

4、编译程序是指将程序翻译成程序的程序。

单选解答1、将编译程序分成若⼲个“遍”是为了使编译程序的结构更加清晰，故选b。

2、构造编译程序应掌握源程序、⽬标语⾔及编译⽅法等三⽅⾯的知识，故选d。

3、对编译⽽⾔，变量既持有左值⼜持有右值，故选c。

4、编译程序打交道最多的就是各种表格，因此选d。

编译原理习题精选与解析要理解编译原理，不可避免地需要接触许多习题。

本文将深入探讨一些精选习题，并提供解析。

1. LL(1)文法的定义和性质LL(1)文法的定义是：对于一个非左递归的文法，如果对于每个非终结符A和每个输入符号a，存在唯一的产生式A→α，使得FIRST(α)∩FIRST(β)=∅，有如下性质：a. 任何一个右端的文法符号串均有唯一的非终结符能够推导出该符号串。

b. 任何文法符号串均至少有一种左推导。

c. LL(1)文法是一种没有左递归或间接左递归的上下文无关文法，它确定了一个自顶向下的分析方法。

2. LL(1)文法求解对于给定的一台LL(1)文法，求解FIRST(A)、FOLLOW(A)和SELECT(A→α)是非常关键的。

其中：a. FIRST(A)是由A能直接推导出的最左符号串的所有首终结符组成的集合。

b. FOLLOW(A)是在左面的文法符号串中跟随出现A而随之出现的所有终结符的集合。

c. SELECT(A→α)是将FIRST(α)中每一个非空成分和FOLLOW(A)中每一个非空成分组合而成的集合。

3. LR(1)文法的定义和性质LR(1)文法是在LL文法的基础上发展而来的，它的定义是：对于一个文法G=(Σ,Vn,P,S)，如果存在某个项目集I，和一个LR(1)自动机M，使得M可以根据I和输入字符S不断进行状态转移，最终确定一个合法的LR(1)语法树，则称G是LR(1)文法。

LR(1)文法的性质是：a. LR(1)文法是上下文无关文法的一种，可以用于生成翻译程序。

b. LR(1)文法可以通过LR分析法实现自动机的状态转移。

4. LR(1)分析法的实现LR(1)分析法的实现是非常简单的，只需要按照下列步骤进行即可。

a. 根据LR(1)自动机的规则，对于每个产生式A→α，计算对应的项目集，即{A→.α, b}。

b. 构建一个I0初始项目集，它包含S→.E,＄}，其中E是文法的开始符号。