第四章 自顶向下语法分析方法
语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。
在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。 本章重点：自顶向下分析、LL （1）分析
第一节 自顶向下分析方法
一、带回溯的自顶向下分析算法
这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。
下面用一个简单例子来说明这种过程：
假定有文法G[S]：
S→c Ａd
A →ab|a 以及输入串w=cad
为了自上而下地构造w 的语法树，我们首先按文法的识别符号产生根结点S ，并让指示器IP 指
c S 的规则仅有一条）把这棵树发展为
（ a ）
（b ） （c ）
图3-1-1
图3-1-1a 。我们希望用S 的子结从左至右匹配整个输入串w 。首先，此树的最左子结是终结符c 为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP 调整为指向下一输入符号a ，并让第二个子结A 去进行匹配，非终结符A 有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b 。子树A 的最左子结和IP 所指的符号相符，然后我们再把IP 调为指向下一符号d 并让A 的第二个子结进入工作。但A 的第二个子结为终结符号b ，与IP 当前指的符号d 不一致。因此，A 宣告失败。这意味着A 的第一个选择此刻不适用于构造w 的语法树。这时，我们应该回头（回溯）看A 是否还有别的选择。
为了实现回溯，我们一方面应把A 的第一个选择所生长的子树注销掉；另一方面，应把IP 恢复为进入A 时的原值，也就是让它重新指向第二输入符号a 。现在我们试探用A 的第二个选择，即考虑生成图3-1-1c 的语法树。
由于子树A 只有一个子结a ，而且，它和IP 所指的符号相一致，于是，A 完成了匹配任务。在A 获得匹配后，指示器指向下一个未被触及的符号d 。
在S 的第二子结A 完成匹配后，接着就轮到第三个子结d 进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了w 是文法G[ s]的一个句子。 上述自顶向下地为输入符号w 建立语法树的过程，实际上也是设法建立一个最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对于输入串w 可以通过如下的推导过程将其推导出来：S ?CAd ?cad
所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推出符号串w 的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。
根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存
在着一定的困难和缺点。困难表现在不能为左递归文法构造自顶向下的语法分析器（上述所举例子的文法G[s]是不具有在递归性的）。缺点主要表现在存在着回溯问题。当然，应用带回溯的自顶向下的分析算法还必须将文法规则存放于内存。下面将具体介绍这种分析算法所存在的问题及其解决办法。
二、存在问题及解决办法
（一）左递归问题
自顶向下分析法只有规则排列得合适时，才能正确工作。该法的一个基本缺点是不能处理具有左递归的文法。如下所示。
如：直接左递归和间接左递归
无法确定语法树的终止，
清除直接左递归的较好方法是改
为右递归
如：S→Sa|b 改为
S→bS′
S′→aS′|ε
一般情况下，直接左递归的形式可为：
A→Aα1|Aα2| …Aαm|β1|β2…βn
清除左递归后改写为：
A→β1A′|β2A′…|βn A′
A′→α1A′|α2A′…|αm A′|ε
对于间接左递归的消除，需先将间接左递归变为直接左递归，然后再接上述方法消除。
条件是文法中无A→A的有害规则和
A→ε的空产生式
（二）回溯问题
当产生式有多个选择时，选那个输入串去匹配
为了避免回溯，就必须保证：对文法的任何非终结符号特别是规则右部有多个选择的非终结符号，当用它去匹配输入串时，应是确定无疑的。即：
U→α1|α2|…|αn
该规则右部有n个选择,为了实现目的,我们对文法的要求是:
FIRST（αi）∩FIRST（αj）=ф（i≠j）
定义1：设G=（V T，V N，S，P）是上下文无关文法FIRST（α）={a| αaβ，a∈V T，α，β∈V*}
若α?ε，则规定α∈FIRST（α）
即对文法中的任意一个非终符号，其规则右部有多个选择时，那么，由各个选择所推出的终结符号串的头符号集合要两两不相交。这样，就可能根据当时读进的符号是属于哪个选择的FIRST（α），来唯一地确定应该选用哪个选择来匹配输入串。如当前的输入符号为b(b∈V T)，若b∈FIRST（αi），则用第i个选择；
若b不∈FIRST（αi），其中i=1~n，则语法错，转出错处理。这样就避免了分析过程的回溯。
若文法的任一非终结符号，其规则右部的各个选择所能推出的终结符号串的头符号集合不满足两两相交的条件时，那么，要构造一个不带回溯的自顶向下的语法分析程序，需要采取什么措施呢？一般可采取改写文法的办法来解决。
（三）改写文法当文法不满足，可改写文法
提因子
U→xv|xw U→x(v|w)
三、递归子程序法
此方法的主要做法是：对文法中每个非终结符号U,都编出一个子程序，以完成该非终结符号所对应的语法成分的分析和识别任务。某个非终结符号的语法分析子程序的功能是：用该非终结符号的规则的右部符号串去匹配输入串。分析过程是按文法规则自顶向下一级一级地分配任务，即调用有关的子程序来完成。当编译程序根据文法和当前输入符号预测到下一个语法成分为U时，即预测到待匹配的输入符号串可以为从U出发所推导出的符号串相匹配时，就确定U为目标，并调用分析和识别U的子程序。在分析和识别U的过程中，有可能还要确立其他子目标并调用相应的子程序，只有在被调用的分析和识别某语法成分的子程序匹配输入串成功并正确返回时，该语法成分才算真正的获得了识别，并确定输入串无语法错误。。
为什么针对某些非终结符号所编出的分析程序要编成递归子程序?因为文法具有递归性。前面已讲过，自顶向下分析不能处理左递归文法，若有左递归，则应改写文法予以消除。但是，消除了左递归不等于消除了文法的所有递归性质，此时，文法仍可以有右递归性或自嵌入性。如在文法中有规则
U→…U
或U→…U…
此仍为递归规则，故分析U的子程序要编成递归子程序。因为该子程序在用规则右部符号串去匹配输入串的过程中，又要调用U自己。即在通过该子程序正常出口返回调用程序以前，又要重新直接进入该子程序，这就是直接递归。此外，还有间接递归，如在文法中有规则：
U→…V
V→…UW
那么U…V…UW
即U+?…UW
在该情况下，在分析U的子程序中要调用分析V的子程序；而在分析U的子程序中又要调用分析V 的子程序。这样，对U的分析程序就要编成递归子程序，因在进入U的分析程序以后，在返回调用程序以前，又可能间接地进入自己。
第二节 LL(1)分析方法
本节，我们将介绍实现自顶向下分析的另一种方法，即所谓LL(1)分析方法。如此命名该分析方法的
原因在于相应的语法分析将按自左至右的顺序扫描输入符号串，并在此过程中产生一个句子的最左推
导。至于括号中的“1”，则表示在分析过程中，每进行一步推导，只要向前查看一个输入符号，便能确定当前所应选用的产生式（规则）。因此，我们通常把按上述方法执行语法分析任务的程序称为LL(1)分析程序或LL(1)分析器，使用这种方法进行语法分析，
可借助于一张分析表及一个语法分析栈，在一个总控程序控制下很方便地实现。 下面，我们将首先介绍LL(1)分析器的逻辑结构和工作过程，然后再介绍LL(1)分析器的构造方法。（一）LL(1)分析器的逻辑结构及工作过程 在逻辑上，一个LL(1)分析器由一个总控程序、
一张分析表和一个分析栈组成，如图4-2-1所示。其中：
1、“输入”即待分析的符号串（注意，#∈V T ，我们之所以在输入串的末尾放置一个#，仅为了分析算法格式的统一）。
2、分析表M 可用一个矩阵（或二维数组）来表示，它概括了相应文法的全部信息。矩阵的每一行与文法的一个非终结符号A 相关联，而每一列则与文法的一个终结符号或#相关联。
分析表元素M[A, a]或者指示了当前推导所应使用的产生式，或者指出了输入串中含有语法错误。
分析器对每一输入串的分析在总控程序控制下进行。其算法如下（为书写方便。在下面的叙述中，我们将分析栈按顺时钟旋转九十度）：
第一步 分析开始时，首先将符号#及文法的开始符号S 依次置于分析栈底部，并把各指示器调整至起始位置，即初始格局为
然后，反复执行第二步所列的工作。
第二步 设在分析的某一步，分析栈及余留的输入符号串处于如下的格局
其中，X 1，X 2，…X m 为分析过程中所得的文法符号，此时，可视栈顶符号X m 的不同情况，分别做如下的动作：
1、若X m ∈V N ，则以X m 及a i 组成符号对（X m , a i ）查分析表M ，设M[X m , a i ]为一产生式，譬如说X m →UVW ，此时将
，从而得到新的格局
但若M[X m , a i ]=“ERROR ”，则调用出错处理程序进行处理；
2、若X m =a i ≠#，则表明栈顶符号已与当前正扫视的输入符号得到匹配，此时应将X m （即ai ）从栈中退出，并将输入符号指示器向前推进一个位置；
3、若X m =a i =#，则表明输入串已完全得到匹配，此时即可宣告分析成功而结束分析工作。
例 考虑文法G[E]：
E →TE'
E'→+TE'|ε T '→*FT'|ε
F →(E)|i T →FT'
相应的分析表如图4-2-2所示（其构造方法，在后面叙述）。现以输入符号串i+i*i 为例，列出利用上述算法对此符号串的分析过程如图4-2-3所示。
步骤 分析栈 余留输入串 所用产生式 1 # E i+i*i# E→TE'
2 # E'T i+i*i# T→FT'
3 # E'T'F i+i*i# F→i
4 # E'T'i i+i*i#
5 # E'T' +i*i# T'→ε
6 # E' +i*i# E'→+TE'
7 # E'T+ +i*i#
8 # E'T i*i# T'→FT'
9 # E'T'F i*i# F→i
10 # E'T'i i*i#
11 # E'T' *i# T'→*FT'
12 # E'T'F* *i#
13 # E'T'F i# F→i
14 # E'T'i i#
15 # E'T' # T'→ε
16 # E' # E'→ε
17 # # 成功 图4-2-3
（二）LL(1)分析表的构造方法上述LL(1)分析算法对于不同的LL(1)文法都是相同的。也就是说，对不同的LL(1)分析器而言，它们的总控程序都是相同的，不同的仅仅是分析表。再者总控程序十分简单，非常容易实现，所以我们只着重讨论构造分析表的问题。为了构造分析表，我们需要预先定义和构造两个与文法有关的集合FIRST和FOLLOW。
假定α是文法G的任一符号串，或者说α∈(V T UT N)*，我们定义：
FIRST(α)={ a|α* ?aβ, a∈V T}
特别是，若α * ?ε，则规定ε∈FIRST(α)，换句话说，FIRST(α)是从α可能推导出的所有开头终结符号或可能的ε。
假定S是文法的开始符号，对于G的任何非终结符A，我们定义：
FOLLOW(A)={a|S* ?…A a…，a∈V T}
特别是，若S* ?…A，则规定#∈FOLLOW(A)。换句话说，FOLLOW(A)是所有句型中出现在紧接A之后的终结符或#。下面，我们将首先给出构造集合FIRST及FOLLOW的算法，然后再给出构造分析表的算法。
1、计算F1RST集
根据定义计算
由定义FIRST（α）={a| α* ?aβa∈V T α、β∈V*},若* ?ε，则规定ε∈FIRST(α)
对每一文法符号X∈V计算FIRST(X)。
（a）若X∈V T,则FIRST(X)={x}
（b）若X∈V N,且有产生式X→a…,a∈FIRST(X)。
（c）若X∈V N,X→ε,则ε∈FIRST(X)。
（d）若X∈V N,Y1,Y2,…，Y i都∈V N,而有产生式X→Y1Y2…Y n。当Y1,Y2,…，Y i-1都* ?ε时，（其中1≤i≤n），则FIRST(Y1)－{ε},FIRST(Y2)－{ε},…，FIRST(Y i-1)－{ε},FIRST(Y i)都包含在FIRST(X)中。
（e）当（d）中所有Y i* ?ε，(i=1,2,…n)
则FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Y n)∪{ε}。
反复使用上述(b)~(e)步直到每个符号的FIRST集合不再增大为止。
求出每个文法符号的FIRST集合后也就不难求出一个符号串的FIRST集合。
2、计算FOLLOW集
根据定义计算
对文法中每一A∈V N计算FOLLOW(A)
(a) 设S为文法中开始符号，把{#}加入FOLLOW (S)中(这里“#”为句子括号)。
(b) 若A→αBβ是一个产生式，则把FIRST(β)的非空元素加入FOLLOW（B）中。如果β* ?ε则把FOLLOW（A）也加入FOLLOW（B）中，因为当有形如：
D→α1Aβ1
A→αBβ
的产生式时,A, B, D∈V N, α, α1β1, β,∈V*,在推导过程中可能出现句型序列如：
S* ?…α1Aβ1…?…α1αBββ1…?…α1αBβ1…，由定义可知FIRST(β1)∈FOLLOW（A）和FIRST(β1)∈FOLLOW(B)。
所以也就有FOLLOW(A)?FOLLOW(B)
(c) 反复使用(b)直到每个非终结符的FOLLOW集不再增大为止。
使用上述两个算法为文法G[E]构造的全部非终结符号FIRST集及FOLLOW集如下：
FIRST（E）=FIRST（T）=FIRST（F）={(，i}，
FIRST（E′）={+，ε}，FIRST（T′）={*，ε}，
FOLLOW（E）=FOLLOW（E′）={)，#}，
FOLLOW（T）=FOLLOW（T′）={+，)，#}，
FOLLOW（F）={+，*，），#}。
3、构造LL(1)分析表算法
所谓构造相应的分析表M，其实也就是定义M的各个元素。对此，我们在前面介绍LL（1）分析器的逻辑结构时已初步涉及到了。
现在，我们假定G的每一非终结符的FOLLOW集与各候选式的FIRST集均已按上面的算法作出，为构造G的分析表M，则只需对G中的每一产生式A→a，依如下的规则确定M的各个元素：（1）对FIRST（α）中的每一终结符a，置M[A, a]=“A→α”。
（2）若ε∈FIRST（a），则对属于FOLLOW（A）的每一符号b（b为终结符或#），置M[A，b]=“A→α”。
（3）把M中所有不能按规则1、2定义的元素均置为ERROR（出错）。
例如，按上述算法为文法G[E]所构造的分析表如图4-2-2所示。
一个文法G，若它的分析表M不含多重元素，则称它是一个LL（1）文法。一个LL（1）文法是无二义的，它所定义的语言恰好就是它的分析表M所能识别的全部句子。可以证明，一个文法G 是LL（1）的，当且仅当对于G的每一个非终结符A的任何两条不同规则A∷=α|β，下面的条件成立：
（1）FIRST（α）∩F IRST（β）=ф，也就是由α和β推导不出以某个同一终结符a为首的符号串；它们不应该都能推出空字ε。
（2）假若β?ε，那么，FIRST（α）∩FOLLOW（A）=ф。也就是，若β?，则α所能推出的串的首符不应在FOLLOW（A）中。
很清楚，文法G[E]是LL（1）文法。
对每一个文法G，尽管都可按上述算法为它们构造一个分析表M。然而，在某些情况下，例如G存在左递归或二义性等等，则在相应的分析表中，必然会出现多重定义的元素。请看下面的文法：
G=（{S，A，B，C}，{a，b，c}，P，S），
其中，P由如下产生式组成：
S→a b B, A→SC,A→BAA，A→ε
B→A b A，C→B，C→c
因为
FIRST（S）={a}
FIRST（A）=FIRST（B）={ε,a,b}
FIRST（C）={a，b，c}
故由上述算法的规则1可知：M[A，a]中含有“A→SC”及“A→BAA”，M[A，b]中含有“A→BAA”。再由A中含有的产生式A→ε，且b∈FOLLOW（A），故由规则2可知，M[A，b]中也含有产生式“A→ε”。可见在此文法的分析表中，元素M[A，a]及M[A，b]都是多重定义的。出现上述情况的原因，在于G中存在如下的问题。
（1）G中含有左递归变量A和B；
（2）对于G中的三个A产生式，有：
FIRST（SC）∩FIRST（BAA）≠ф
FIRST（BAA）∩FOLLOW（a）≠ф。
也就是说，G不是一个LL（1）方法。实际上，可以证明，对于任何文法G，当且仅当它是一个LL （1）文法时，才能按上述算法为它构造一个无多重定义元素的分析表，而且此分析表能分析并且仅能分析G中的全部句子。对某些非LL（1）文法而言，通过消除左递归和提取左因子，有可能把它们改造为LL（1）文法。例如，对于非LL（1）文法
E→E+T|T，
T→（E）|a（E）|a，
经消除其中的左递归并对T-产生式提取左因子之后，我们就把它改造为如下的LL（1）文法：E→TE′E′→+TE′|ε
T→aT′|（E），
T→（E）|ε，
但是，并非所有的非LL（1）文法都能改造为LL（1）文法。例如，对于文法
S→AU|BR，
A→aAU|b，
B→aBR|b，
U→c，R→d，
因对于S-产生式，有FIRST（AU）∩FIRST（BR）≠ф，故它不是一个LL（1）文法。为了对S-产生式提取左因子，将其中的非终结符号A，B分别以其各候选式替入，我们得到：
S→aAUU|bU|aBRR|bR
经提取左因子后，得到了与原文法等价的新文法：
S→aS′|bS″，S″→U|R
S′→AUU|BRR，A→aAU|b，
B→aBR|b，U→c，R→d。
显然，它仍不是一个LL（1）文法。且不难看出，无论把上述手续重复多次，都不能把它改造为LL （1）文法。
编译原理课程设计Course Design of Compiling （课程代码3273526） 半期题目：词法和语法分析器 实验学期：大三第二学期 学生班级：2014级软件四班 学生学号：2014112218 学生姓名：何华均 任课教师：丁光耀 信息科学与技术学院 2017.6
课程设计1-C语言词法分析器 1.题目 C语言词法分析 2.内容 选一个能正常运行的c语言程序，以该程序出现的字符作为单词符号集，不用处理c语言的所有单词符号。 将解析到的单词符号对应的二元组输出到文件中保存 可以将扫描缓冲区与输入缓冲区合成一个缓冲区，一次性输入源程序后就可以进行预处理了 3.设计目的 掌握词法分析算法，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解 4.设计环境（电脑语言环境） 语言环境:C语言 CPU:i7HQ6700 内存：8G 5.概要设计（单词符号表，状态转换图） 5.1词法分析器的结构 词法分析程序的功能：
输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 词法分析程序可以单独为一个程序；也可以作为整个编译程序的一个子程序，当需要一个单词时，就调用此法分析子程序返回一个单词. 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序: 1) ch 存放最新读进的源程序字符 2) strToken 存放构成单词符号的字符串 3) Buffer 字符缓冲区 4）struct keyType 存放保留字的符号和种别 5.2待分析的简单词法 （1）保留字 break、case、char、const、int、do、while… （2）运算符和界符 = 、+、-、* 、/、%、，、；、（、）、？、# 5.3各种单词符号对应的种别码
编译原理语法分析实验报告 - 班级:XXX 学号:XXX 姓名:XXX 年月日 1、摘要: 用递归子程序法实现对pascal的子集程序设计语言的分析程序 2、实验目的: 通过完成语法分析程序，了解语法分析的过程和作用 3、任务概述 实验要求:对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 4、实验依据的原理 递归子程序法是一种自顶向下的语法分析方法，它要求文法是LL(1)文法。通过对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，程序能够按LL(1)形式唯一地确定选择某个候选式进行推导，最终识别输入串是否与文法匹配。 递归子程序法的缺点是:对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，例如PASCAL，C等编译系统常常采用的语法分析方法。
为适合递归子程序法，对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下: <程序>?<程序首部><分程序>。 <程序首部>?PROGRAM标识符; <分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε <常量定义>?标识符=无符号整数 <常量定义后缀>?，<常量定义><常量定义后缀> |ε <变量说明部分>?VAR<变量定义><变量定义后缀> |ε <变量定义>?标识符<标识符后缀>:<类型>; <标识符后缀>?，标识符<标识符后缀> |ε <变量定义后缀>?<变量定义><变量定义后缀> |ε <类型>?INTEGER | LONG <过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε <过程首部>?PROCEDURE标识符<参数部分>; <参数部分>?(标识符: <类型>)|ε <过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε <语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>?标识符<后缀> <后缀>?:=<表达式>|(<表达式>)|ε <条件语句>?IF<条件>THEN<语句> <当型循环语句>?WHILE<条件>DO <语句> <读语句>?READ(标识符<标识符后缀>)
编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日
一、目的 编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 二、任务及要求 基本要求： 1．词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数（整）= + * ** ， （ ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言，有几点重要的限制： 首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为
武汉轻工大学 编译原理实验报告 姓名朱春桃 院（系）数学与计算机学院 班级软件工程1203 学号 1205110605 指导教师李禹生 2014 年11 月10 日
一、实验目的 完成自顶向下语法分析算法的程序设计。 二、实验内容 设计、调试并测试自顶向下语法分析算法程序。 三、设计思路 根据课堂讲授的自顶向下语法分析方法，可以根据递归下降子程序方法设计语法分析程序，也可以根据LL（1）算法设计语法分析程序，针对文法：G[E] E→E+T | T T→T*F | F F→( E ) | i （1）由于文法G[E]不满足LL（1）文法条件，需要进行必要的等价文法变换。变换后的等价文法为： H[E] E→TA A→+TA | ε T→FB B→*FB | ε F→( E ) | i （2）等价文法H[E]不含左递归，可以证明文法H[E]满足LL（1）文法条件（3）根据递归下降子程序方法设计语法分析程序 ①递归程序清单 ②调试过程说明 ③测试语句设计 ④测试结果列表 ⑤测试结论分析 （4）根据LL（1）算法设计语法分析程序 ①预测分析表 ②预测分析程序清单 ③调试过程说明 ④测试语句设计 ⑤测试结果列表
⑥测试结论分析 四、程序清单 /* E->TA, A->+TA|ε, T->FB, B->*FB|ε, F->i|(E). */ #include
学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日
一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include
词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 扫描子程序主要部分流程图 其他
词法分析程序的C语言程序源代码： // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针； // 全局变量buffer与line对应保存源文件字符及其行号，char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意，第"< 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： 五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3; 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 . 编译原理实验专业：13级网络工程 语法分析器1 一、实现方法描述 所给文法为G【E】； E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法： 首先计算出五个非终结符的first集合follow集，然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子，字符指针ch指向vocabulary。从非终结符E函数出发，如果首字符属于E的first集，则依次进入T函数和E’函数，开始递归调用。在每个函数中，都要判断指针所指字符是否属于该非终结符的first集，属于则根据产生式进入下一个函数进行调用，若first集中有空字符，还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include #include int a=0; cout<<"按1结束程序"< 第五章自上而下语法分析 1、教学目的及要求： 本章介绍编译程序的第二个阶段语法分析的设计方法和实现原理，包括自上而下分析的无回朔的递归下降分析、 LL(1)分析法。要求理解递归下降分析、LL(1)文法的基本概念；掌握无回朔的递归下降分析的设计和实现、LL(1)分析表的构造与分析方法。 ◇能够对一个给定的文法判断是否是LL(1)文法； ◇能构造预测分析表； ◇能用预测分析方法判断给定的输入符号串是否是该文法的句子； ◇能对某些非LL(1)文法做等价变换： ①消除左递归 ②提取左公共因子 可能会变成LL(1)文法。这样可扩大自顶向下分析方法的应用。 2、教学内容： 语法分析器的功能，自上而下语法分析（递归下降分析法，预测分析程序），LL（1）分析法，递归下降分析程序构造，预测分析程序。 3、教学重点： 递归下降子程序，预测分析表构造，LL(1)文法。 4、教学难点： 对一个文法如何判断是否是LL(1)文法，由于在判断 LL(1)文法时用到文法符号串的开始符号集合（FIRST集）和非终结符后跟符号集合（FOLLOW集）的计算，而一般学生往往因概念不清或不够细心对这两个集合的计算常常出错，导致判断和分析结果的错误。 5、课前思考 为了了解自顶向下（自上而下）分析的一般过程和问题，请学生首先回顾本章之前介绍的有关基本概念： ◇句子、句型和语言的定义是什么？ ◇什么叫最左推导？ ◇什么叫最右推导和规范推导？ ◇什么叫确定的自顶向下语法分析？ ◇自顶向下语法分析是从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。 ◇确定的自顶向下语法分析中用的是哪种推导？ ◇在确定的自顶向下语法分析过程中，当以同一个非终结符为左部的产生式有多个不同右部时，如何选择用哪个产生式的右部替换当前的非终结符？ ◇确定的自顶向下语法分析对文法有何限制？ 6、章节内容 第一节概述 第二节 LL(1)分析方法 第三节递归下降分析法 5.1 概述 LL分析法 确定的自上而下分析 自上而下分析递归下降分析法 语法分析不确定的自上而下分析——即带回溯的分析方法 算符优先分析 自下而上分析 LR分析 一、带回溯的自顶向下分析方法 是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的办法，从树根结点（识别符号）出发，根据文法自上而下地为输入串建立一棵语法树，或者说，从识别符号开始，根据文法为输入串建立一个推导序列，这种分析过程本质上是一种试探过程，是反复使用不同规则谋求匹配输入串的过程。 例有文法G[S]：S→cAd，A→ab|a，输入串w=cad。其分析过程为带回溯的。 二、存在问题及解决办法 1、左递归问题： 自顶向下分析方法只有把规则排列得合适时才能正确工作，该方法不能处理具有左递归性文法，可采取某些算法消除左递归。 2、回溯问题： 编译原理实验报告 实验名称：编写语法分析分析器实验类型： 指导教师： 专业班级： 学号： 电子邮件： 实验地点： 实验成绩： 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，至少选一题。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求： （a）根据算符优先分析算法，编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入： Ⅰ：通过构造算符优先关系表，设计编制并调试一个算法优先分析程序Ⅱ：输入FIRSTVT，LASTVT集合，由程序自动生成该文法的算符优先关系矩阵。 Ⅲ：输入已知文法，由程序自动生成该文法的算符优先关系矩阵。（b）程序具有通用性，即所编制的语法分析程序能够使用于不同文法以及各种输入单词串，并能判断该文法是否为算符文法和算符优先文法。 （c）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。 三、实验结果 算符优先分析器： 测试数据：E->E+T|T T->T*F|F F->(E)|i 实验结果：(输入串为i+i*i+i) 四、讨论与分析 自下而上分析技术－算符优先分析法： 算符文法：一个上下无关文法G，如果没有且没有P→..QR...(P ,Q ,R属于非终结符)，则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...，则a∈FIRSTVT(P)。 2、若有产生式P→...，则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：…P…，则对所有：b∈firstVT(P)都有：a≦b。 构造优先关系表： 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式，则对于每个b∈FIRSTVT(P)都有 第四章 自顶向下语法分析方法 语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。 在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。 本章重点：自顶向下分析、LL （1）分析 第一节 自顶向下分析方法 一、带回溯的自顶向下分析算法 这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。 下面用一个简单例子来说明这种过程： 假定有文法G[S]： S→c Ａd A →ab|a 以及输入串w=cad 为了自上而下地构造w 的语法树，我们首先按文法的识别符号产生根结点S ，并让指示器IP 指 c S 的规则仅有一条）把这棵树发展为 （ a ） （b ） （c ） 图3-1-1 图3-1-1a 。我们希望用S 的子结从左至右匹配整个输入串w 。首先，此树的最左子结是终结符c 为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP 调整为指向下一输入符号a ，并让第二个子结A 去进行匹配，非终结符A 有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b 。子树A 的最左子结和IP 所指的符号相符，然后我们再把IP 调为指向下一符号d 并让A 的第二个子结进入工作。但A 的第二个子结为终结符号b ，与IP 当前指的符号d 不一致。因此，A 宣告失败。这意味着A 的第一个选择此刻不适用于构造w 的语法树。这时，我们应该回头（回溯）看A 是否还有别的选择。 为了实现回溯，我们一方面应把A 的第一个选择所生长的子树注销掉；另一方面，应把IP 恢复为进入A 时的原值，也就是让它重新指向第二输入符号a 。现在我们试探用A 的第二个选择，即考虑生成图3-1-1c 的语法树。 由于子树A 只有一个子结a ，而且，它和IP 所指的符号相一致，于是，A 完成了匹配任务。在A 获得匹配后，指示器指向下一个未被触及的符号d 。 在S 的第二子结A 完成匹配后，接着就轮到第三个子结d 进行工作。由于这个子结和最后一个输入符号相符，于是，我们完成了构造语法树的任务，证明了w 是文法G[ s]的一个句子。 上述自顶向下地为输入符号w 建立语法树的过程，实际上也是设法建立一个最左推导序列，以便通过一步步推导将输入串推导出来。很明显，对于输入串w 可以通过如下的推导过程将其推导出来：S ?CAd ?cad 所以用最左推导，是因为我们对输入串是自左向右扫描的，只有使用最左推导，才能保证按扫描顺序去匹配输入串。在上述推出符号串w 的过程中，由于出现在符号串中的非终结符号只有一个，因此，未明显地表现出最左推导的性质。 根据以上分析，不难编出程序来实现这种分析的算法。但是，上述这种自顶向下的分析算法存 一、实验目的 了解词法分析程序的两种设计方法：1.根据状态转换图直接编程的方式；2.利用DFA 编写通用的词法分析程序。 二、实验内容及要求 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 2．编写DFA模拟程序 算法如下： DFA（S=S0,MOVE[][],F[],ALPHABET[]） /*S为状态，初值为DFA的初态，MOVE[][]为状态转换矩阵，F[] 为终态集，ALPHABET[] 为字母表，其中的字母顺序与MOVE[][] 中列标题的字母顺序一致。*/ { Char Wordbuffer[10]=“”//单词缓冲区置空 Nextchar=getchar（）；//读 i=0； while（nextchar！=NULL）//NULL代表此类单词 { if （nextcha r！∈ALPHABET[]）{ERROR（“非法字符”），return（“非法字符”）；} S=MOVE[S][nextchar] //下一状态 if（S=NULL）return（“不接受”）；//下一状态为空，不能识别，单词错误 wordbuffer[i]=nextchar ；//保存单词符号 i++； nextchar=getchar（）； } Wordbuffer[i]=‘\0’; 昆明理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：编译原理开课实验室： 445 2011年 12 月 19日年级、专业、 班 计科093 学号200910405310 姓名孙浩川成绩 实验项目名称语法分析器指导教师严馨 教 师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强□ B.中等□ C.差□ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般□ C.没有□ 教师签名： 年月日 一、实验目的及内容 实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检 查和结构分析。 实验内容：在上机(一)词法分析的基础上,采用递归子程序法或其他适合的语法分析方法,实现其语法分析程序。要求编译后能检查出语法错误。 已知待分析的C语言子集的语法，用EBNF表示如下： <程序>→main()<语句块> <语句块> →‘{’<语句串>‘}’ <语句串> → <语句> {; <语句> }; <语句> → <赋值语句> |<条件语句>|<循环语句> <赋值语句>→ID=<表达式> <条件语句>→if‘(‘条件’)’<语句块> <循环语句>→while’(‘<条件>’)‘<语句块> <条件> → <表达式><关系运算符> <表达式> <表达式> →<项>{+<项>|-<项>} <项> → <因子> {* <因子> |/ <因子>} <因子> →ID|NUM| ‘(’<表达式>‘)’ <关系运算符> →<|<=|>|>=|==|!= 二、实验原理及基本技术路线图（方框原理图或程序流程图） 词法分析器实验报告 一、实验目的 选择一种编程语言实现简单的词法分析程序,设计、编制并调试一个词法分析程序,加深对词法分析原理的理解。 二、实验要求 2、1 待分析的简单的词法 (1)关键字: begin if then while do end 所有的关键字都就是小写。 (2)运算符与界符 : = + - * / < <= <> > >= = ; ( ) # (3)其她单词就是标识符(ID)与整型常数(SUM),通过以下正规式定义: ID = letter (letter | digit)* NUM = digit digit* (4)空格有空白、制表符与换行符组成。空格一般用来分隔ID、SUM、运算符、界符与关键字,词法分析阶段通常被忽略。 2、2 各种单词符号对应的种别码: 表2、1 各种单词符号对应的种别码 2、3 词法分析程序的功能: 输入:所给文法的源程序字符串。 输出:二元组(syn,token或sum)构成的序列。 其中:syn为单词种别码; token为存放的单词自身字符串; sum为整型常数。 例如:对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件,经过词法分析后输出如下序列: (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想: 算法的基本任务就是从字符串表示的源程序中识别出具有独立意义的单词符号,其基本思想就是根据扫描到单词符号的第一个字符的种类,拼出相应的单词符号。 3、1 主程序示意图: 主程序示意图如图3-1所示。其中初始包括以下两个方面: ⑴ 关键字表的初值。 关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。如能查到匹配的单词,则该单词为关键字,否则为一般标识符。关键字表为一个字符串数组,其描述如下: Char *rwtab[6] = {“begin ”, “if ”, “then ”, “while ”, “do ”, “end ”,}; (2)3、2 扫描子程序的算法思想: 首先设置3个变量:①token 用来存放构成单词符号的字符串;②sum 用来整型单词;③syn 用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 语法分析器的设计 一、实验内容 语法分析程序用LL(1)语法分析方法。首先输入定义好的文法书写文件(所用的文法可以用LL(1)分析)，先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT 集的交集是不是都为空，如果是，则输入文法符合LL(1)文法，可以进行分析。对于文法： G[E]: E->E+T|T T->T*F|F F->i|(E) 分析句子i+i*i是否符合文法。 二、基本思想 1、语法分析器实现 语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。这里采用自顶向下的LL(1)分析方法。 语法分析程序的流程图如图5-4所示。 语法分析程序流程图 该程序可分为如下几步： （1）读入文法 （2）判断正误 （3）若无误，判断是否为LL(1)文法 （4）若是，构造分析表； （5）由句型判别算法判断输入符号串是为该文法的句型。 三、核心思想 该分析程序有15部分组成： （1）首先定义各种需要用到的常量和变量； （2）判断一个字符是否在指定字符串中； （3）读入一个文法； （4）将单个符号或符号串并入另一符号串； （5）求所有能直接推出&的符号； （6）求某一符号能否推出‘& ’； （7）判断读入的文法是否正确； （8）求单个符号的FIRST； （9）求各产生式右部的FIRST； （10）求各产生式左部的FOLLOW； （11）判断读入文法是否为一个LL(1)文法； （12）构造分析表M； （13）句型判别算法； （14）一个用户调用函数； （15）主函数； 下面是其中几部分程序段的算法思想： 1、求能推出空的非终结符集 Ⅰ、实例中求直接推出空的empty集的算法描述如下： void emp(char c){ 参数c为空符号 char temp[10];定义临时数组 int i; for(i=0;i<=count-1;i++)从文法的第一个产生式开始查找 { if 产生式右部第一个符号是空符号并且右部长度为1, then将该条产生式左部符号保存在临时数组temp中 将临时数组中的元素合并到记录可推出&符号的数组empty中。 } Ⅱ、求某一符号能否推出'&' int _emp(char c) { //若能推出&，返回1；否则，返回0 int i,j,k,result=1,mark=0; char temp[20]; temp[0]=c; temp[1]='\0'; 存放到一个临时数组empt里,标识此字符已查找其是否可推出空字 如果c在可直接推出空字的empty[]中,返回1 for(i=0;;i++) { if(i==count) return(0); 找一个左部为c的产生式 j=strlen(right[i]); //j为c所在产生式右部的长度 if 右部长度为1且右部第一个字符在empty[]中. then返回1(A->B,B可推出空) if 右部长度为1但第一个字符为终结符,then 返回0(A->a,a为终结符) else 第四章自顶向下语法分析方法 语法分析是编译过程的核心部分。语法分析的任务是：按照文法，从源 程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。执行语法分析任务的程序称为分析程序。也称为语法分析器，它是编译程序的主要子程序之一。 在第二章中我们已经介绍过。通过语法分析可建立起相应的语法树。按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。下面，我们先介绍自顶向下分析。 本章重点：自顶向下分析、LL（1）分析 第一节自顶向下分析方法 一、带回溯的自顶向下分析算法 这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。 下面用一个简单例子来说明这种过程： 假定有文法G[S] ： S—c A d A — ab|a 以及输入串w=cad 为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S, 并让指示器IP 指 向输入串的第一符号c。然后，用S的规则（此处左部为S的规则仅有一条）把这棵树发展为| （a） （b）（c） 图3-1-1 图3-1-1a。我们希望用S的子结从左至右匹配整个输入串w。首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。于是，我们就把IP调整为指向下一输入符号a,并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b。子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。但A 的第二个子结为终结符号b，与IP当前指的符号d不一致。因此，A宣告失败。这意味着A的第一个选择此刻不适用于构造w的语法树。这时，我们应该回头（回溯）看A是否还有别的选择。 为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。现在我们试探用A的第二个选择，即考虑生成图3-1-1C的语法树。 由于子树A只有一个子结a，而且，它和IP所指的符号相一致，于是，A 编译原理 实验报告 实验名称：词法分析及语法分析专业班级： 姓名： 学号： 完成日期： 实验一、sample语言的词法分析 一、实验目的 给出SAMPLE文法规范，要求编写SAMPLE语言的词法分析程序。 二、实验准备 了解sample语言单词的定义，选择任一种编程语言实现词法分析。 三、实验内容 给出SAMPLE语言文法，输出单词（关键字、专用符号以及其它标记）。 1、格式 输入：源程序文件。输出：关键字、专用符号以及其它标记。 2、实现原理 程序中先判断这个句语句中每个单元为关键字、常数、运算符、界符，对与不同的单词符号给出不同编码形式的编码，用以区分之。 3、实验方法 读懂Sample源代码，自己重点独立实现对常量的判别。 四、实验设计 1、设计SAMPLE语言的词法分析器 A、字符集定义 1． <字符集> → <字母>│<数字>│<单界符> 2． <字母> → A│B│…│Z│a│b│…│z 3． <数字> → 0│1│2│…│9 4． <单界符> → +│-│*│/│=│<│>│(│)│[│]│:│. │; │, │' B、单词集定义 5．<单词集> → <保留字>│<双界符>│<标识符>│<常数>│<单界符> 6．<保留字> → and│array│begin│bool│call│case│char│constant│dim│do│else │end│false│for│if│input│integer│not│of│or│output│procedure│program │read│real│repeat│set│stop│then│to│true│until│var│while│write 7．<双界符> → <>│<=│>=│:= │/*│*/│.. 8．<标识符> → <字母>│<标识符> <数字>│<标识符> <字母> 9．<常数> → <整数>│<布尔常数>│<字符常数> 10．<整数> → <数字>│<整数> <数字> 11．<布尔常数> → true│false 12．<字符常数> → ' 除 {'} 外的任意字符串 ' 2、词法分析系统流程设计编译原理 语法分析器 (java完美运行版)(精选.)
编译原理词法分析和语法分析报告+代码(C语言版)
编译原理实验报告(语法分析器)
第五章 自上而下语法分析
编译原理-语法分析-算符优先文法分析器
编译原理 第四章自顶向下语法分析法
编译原理词法分析器
昆明理工大学 编译原理 实验二 语法分析器
编译原理词法分析实验报告
编译原理语法分析器实验
编译原理-四章自顶向下语法分析法
编译原理词法分析及语法分析
相关主题
文本预览