当前位置：文档之家› 编译原理期末复习

编译原理期末复习

鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。

注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。

1、简答题（或者名词解释）

下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。

注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。

（1）简述编译程序的概念及其构成

答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。

2)构成：

（2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。

语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序

(3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合）

答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号；

2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序

3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。

4）构造优化器：对中间代码进行优化。

5) 构造目标代码生成器：把中间的代码翻译成目标程序。

6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。

7)构造错误处理程序：对出错进行处理。

(4) 说明编译和解释的区别：

1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序；

2)编译程序运行效率高而解释程序便于人机对话。

（5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S∈V N P：产生式集合(有限)。

（6）二义性文法：一个文法中存某个句子，它有两个不同的最左（或者最右推导），则称该文法是二义性的。

例子如文法G：S→if expr then S |other

S→if expr then S else S 句子if e1 then if e2 then s1 else s2是二义性的。

（7）文法的形式（注：文法的形式一定要牢记，特别是2型和3型文法一定要牢记，不仅在概念题中有用，在下面的根据语言写文法题中也有重要作用，如果所写的文法形式不对，一切都是无用功……）

1）0型文法(短语文法，图灵机)：产生式形式为：α→β，其中：α∈ (V T ?V N)*且至少含有一个非终结符；β∈ (V T ?V N)*

2）1型(上下文有关文法，线性界限自动机)：产生式形式为:α→β其中：|α| ≤ |β|，仅 S→ε例外但是S不得出现在任何产生式右部。

3）2型文法（上下文无关文法，非确定下推自动机)：产生式形式为：P→α， P∈V N，α∈(V T ?V N)*。

4）3型文法(正规文法，有限自动机)：右线性文法：产生式形如：A →αB 或 A →α其中：α∈V T*；A，B∈V N 左线性文法：产生式形如：A →Bα或 A →α其中：α∈V T*；A，B∈V N

例题：设G=(V T，V N，S，P)是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？若G是1型文法呢？若G是正则文法呢？

上下文无关文法，产生式形式为：P→α， P∈V N，α∈ (V T ?V N)*。

1型文法：产生式形式为:α→β其中：|α| ≤ |β|，仅 S→ε例外。

正则文法：右线性文法：产生式形如：A →αB 或 A →α其中：α∈ V T*；A，B∈V N 左线性文法：产生式形如：A → Bα或 A →α其中：α∈ V T*；A，B∈V N

(8)什么是PDA(下推自动机)?

答：PDA是下推自动机，PDA M用一个七元组表示(K,Σ,f,H,h0,S,Z)

K: 有穷状态集∑：输入字母表(有穷) H:下推栈符号的有穷字母表

h0 :H中的初始符号 f: K ?（Σ?{ε}) ? H –> K ? H* S：属于K是初始状态。

Z:包含于K，是终结状态集合。

(9) 什么是DFA（有穷状态自动机）?

自动机M是一个五元式M=(S, ∑, f, S0, F),其中：

1）S: 有穷状态集， 2）∑：输入字母表(有穷)，

3） f: 状态转换函数，为S?∑→S的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的一个后继状

态。

4） S0∈S是唯一的一个初态； 5） F?S ：终态集(可空)。

（10）推导：所谓推导就是对于一个含非终结符A的符号串，利用规则A→α，把A替换成α得到新符号串的过程。

最左推导：在推导的每一步，选择符号串最左边的非终结符进行替换。

最右推导：在推导的每一步，选择符号串最右边的非终结符进行替换。

(11)归约：归约是推倒的逆过程，即用产生式的左部非终结符替换右部符号串。

(12)什么是句型？什么称为句子？什么是语言？

句型：从文法的起始符号出发，经过有限步的推导能够推导出来的符号称为句子。

句子：只由终结符构成的句型称为句子。

语言：所有句子的集合构成该文法描述的语言。

(13)什么是短语？什么是直接短语（也称为简单短语）？什么是句柄？什么是素短语？什么是最左素短语？（以下几个概念一定要理解，考试中肯定会考哪些是短语，直接短语，句柄等，具体方法请参见后面的）

短语：如果存在某个文法非终结符P,满足S

?βPγ,并且P+?α则称α为句型βαγ相

对于非终结符P的短语。

直接短语：如果P?α,即从P出发一步推出α，则α称为直接短语。

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

素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。

最左素短语：句型中最左边的素短语。

（14）自顶向下的语法分析方法中需要解决的主要问题什么？如何表示？

答：1）主要需要解决回溯和左递归问题。

2）表示方式，回溯：文法中存在形如A→α1|α2|…|αn,即产生式右部存在多个候选，导致推导时不能确定到底应该选择哪个候选式。

左递归：文法中存在形如P→Pα的形式，推导时会导致推导过程无休止的进行下去。

注：解决方法，对回溯采取的是提取左公因子，对左递归使消除左递归（包括直接左递归和间接左递归）。

(15)内情向量：一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情向量”或“信息向量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有一个内情向量。其中的信息包括，数组的类型，维数，各维的上、下界，以及数组的首地址。

（16）C语言的活动记录：

SP TOP

2、最左最右推导，画语法树，找短语、直接短语、句柄等。

这种题目很简单，送分题，一定不能丢分！

考题：1）文法G[S]为：S→SdT | T T→T

分析：（1）推导和画语法树这些都很简单，不再赘述。

（2）根据所画出的语法树，可以很快的找出短语，直接短语，句柄和最左素短语等，先讲一个简单子树的概念，所谓简单子树是指仅具有单层分支的子树。

具体方法如下：

短语：任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语；

直接短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语；

句柄：最左边的直接短语；

素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。

最左素短语：最左边的素短语。

答：（1）S?T? T

语法树：

（2）短语：G，SdG, (SdG), a, (SdG)

短语：a,(S),T<(S),adT<(S) 直接短语：a,(S) 句柄：a 最左素短语：SdG

下面两道例题大家看看，一定要会找短语，直接短语，句柄等.

※短语、简单短语和句柄示例

【例2.12】图2.3为一个算术表达式(型)的语法树：

?句型： E+F-T/F*i

?短语: E+F-T/F*i，E+F，F，T/F*i，T/F，i

【例2.13】G(S): S->aAcBe ; A->Ab|b ; B->d

⑴ S=>aAcBe=>aAbcBe=> aAbcde

考题：2)文法G[E]的产生式为E→E+T|T T→T*F|F F→i|(E)

①对于句型(i+i)*i，给出最左最右推导及相应的推导树

②列出句型的所有短语、简单短语。（还有一份试卷上是出句型F+T*F的所有短语、简单短语和句柄，大家自己做做）

答：（1）最左推导：E?T?T*F?F*F?(E)*F?(E+T)*F?(T+T)*F?(F+T)*F?(i+T)*F

?(i+F)*F?(i+i)*F?(i+i)*i

最右推导E?T?T*F?T*i?F*i?(E)*i?(E+T)*i?(E+F)*i?(E+i)*i?(T+i)*i ?(F+i)*i?(i+i)*i

推导树如下：

（2）短语;i,i+i,(i+i),(i+i)*i 直接短语：i 句柄：i

3、根据语言推文法

这类题目首先要看清题目，指定的是什么文法，一般都是2型（上下无关文法）或者3型（正规文法），这两类文法形式一定要记住，具体请参见第2页的文法分类。

掌握几个基本形式{a n| n>0}对应文法S→aS| a 如果是n>=0则为S→a S|ε(ε是空字) {a n b n | n>0}对应文法S→aSb| ab

下面这四道题目老是在试卷中重复出现，所以大家好好看看。

考题

1、按指定类型给出下列语言的文法,并指出语言的类型。（10 分）

(1)L1={a n b m c n| n≥0,m>0 }

二型文法：S→aSc|B B→bB|b

(2) L2={ 0n a1n b m c m| n>0，m ≥0}

二型文法：S→AB A→0A1|0a1

B→bBc|ε2、按指定类型给出下列语言的文法。（10 分）

(1)L1={ ca n db m| n≥0,m>0 } 用正规文法。

S→cA A→aA|dB B→bB|b (2)L2={ 0n a 1n b m c m| n>0,m ≥0}用二型文法。

S→AB A→0A1|0a1 B→bBc|ε

、按指定的类型给出下列语言的文法（10

分） (1)L1={ ca n b m | n ≥0,m>0 } 用正规文法。 S →cA A →aA|B B →bB|b

(2)L2={ 0n a 1n b m | n>0，m ≥0} 用二型文法。 S →AB A →0A1|0a1 B →bB|ε

4、按指定的类型给出下列语言的文法（10 分） (1) L1={a n b m c|n>=0,m>0}用正规文法 S →aS|A A →bA|bB B →c (2) L2={a0n 1n bd m |n>0,m>0}用二型文法

S →AB A →aT T →0T1|01 B →bD D →dD|d

这是书P36 第11题的答案如下：大家作为练习，可以发现比上述题目简单的多了。

或者 G4:

B B A A B A S |01|10|→→→ε

4、词法分析———正规式、NFA 和DFA 之间的转化：

（1）这类题目一般是三者之间的转换，正规式→NFA →确定化的DFA →最小化的DFA ，有时

已经给出NFA 了，则只需要确定化为DFA 和最小化就行了，一般每一步都是五分。具体怎么转换请参照我期中考试时整理的提纲，主要就是下面这幅关系对照图，因时间和篇幅限制不再追溯。

（2）注意优先级关系，闭包运算*最高，连接运算.次之，或运算|最低。 (3)考题1：

1）构造正则式a*b|(ab)*b 对应的DFA 。（15分） ①画出NFA

G1: S →AC A →aAb|ab C →cC|ε G2: S →AB A →aA|ε B →bBc|bc

G3: S →AB A →aAb|ε B →aAb|ε

X I a I b {X,1,2,3,4} {1,2,5} {Y}

{1,2,5} {1,2}

{3,4,Y}

{Y} - - {1,2} {1,2} {Y} {3,4,Y} {5} {Y} {5} - {3,4} {3,4} {5} {Y} X I a I b

首先将集合分为{A,B,D,F,G},{C,E}。{A,B,D,G}都有a,b作为条件输出，F只有b输出，所以分为{A,B,D,G}和{F} 同理{C,E}分为{C},{E}。{A,B,D}a={B,D} {G}a={F}所以{A,B,D,G}分为{A,B,D}和{G}。{A}b={C} {B,D}a={D}所以分为{A} {B,D}

综上所述：划分的结果为{A},{B,D},{C},{E},{G}.

{X,0,1,3} {0,2,1,3} {3,Y}

{0,2,1,3} {0,2,1,3} {1,3,Y}

含有Y的状态子集为DFA的终态,上例中的终态有B,C,E.

题目中要求是确定化，没有要求最小化，如若最小化，划分的集合为{S,A},{B,C} {F},{D},{E}然后再画出最小化后的DFA这里不再赘述。

考题3：构造奇数个0和奇数个1组成的自动机。（10分）

状态1：偶数个0 偶数个1 状态2：奇数个0偶数个1

状态3：奇数个0 奇数个1 状态4：偶数个0奇数个1 如果题目改成偶数个0，奇数个1，只要将状态4转换成终态即可，其他类似。

5、语法分析——自顶向下分析法（LL（1）分析法和递归向下构造子程序法）注：自顶向下分析法本质是由开始符号，按照产生式逐步推导看能否产生需要分析的句子。（1）自顶向下分析中存在的问题

左递归和回溯（具体请参见简答题中的第（14）题）

（2）消除回溯——提取公因子法

提取公共左因子:假定关于A的规则A→δβ 1 | δβ 2 | …| δβ n | γ 1 | γ 2 | … | γm(其中，每个γ不以δ开头) 那么，可以把这些规则改写成A→δA' | γ 1 | γ 2 | … | γ m

A'→β 1 | β 2 | … | β n

（3）消除左递归

1)消除直接左递归：直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为P→Pα | β，其中β不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：P→βP'P'→αP'|ε

注：一般而言，假定P关于的全部产生式是P→Pα1 | Pα2 | … | Pαm | β1 | β2|…|βn

其中，每个α都不等于ε，每个β都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→β1P' | β2P'| … | βn P'P'→α1P' | α2P'|… | αm P' | ε

例：文法G(E):

E→E＋T | T T→T*F | F F→(E) | i

经消去直接左递归后变成：

E→TE'E'→+TE' | εT→FT 'T '→*FT ' | εF→(E) | i

2)消除间接左递归

这个请参见我期中整理的提纲篇幅较多，这里不再重复赘述，请参照下面的考题2。

考题1：将文法G[S]改写为等价的G’[S],使得G’[S]不含左递归和左公因子。

S→[A A→B]|AS B→aB|a

答：消除左递归和左公因子后的文法为：

S→[A A→ B]A’A’ → S A’| εB→aB’B’ →B| ε

(2)消除间接左递归：将A,B,C按照B,C,A排序（建议将A放在最后）由于出现C→Bg

形式，将B代入C得：C→dAg|Aeg|fg|h又由于A出现A→Ba A→Cb将B,C带入A得到：A→dAa|Aea|fa|dAgb|Aegb|fgb|hb|c等价于A→Aea|Aegb |dAa|fa|dAgb |fgb|hb|c

此时，对于B→dA|Ae|f，C→dAg|Aeg|fg|h由于未在任何产生式的右部出现，所以是多余的。

综上所述:消除递归后的文法为：A→dAaA’|fa A’|dAgb A’ |fgb A’|hb A’|c A’

A’→ea A’| egb A’|ε

(4)LL(1)分析法

1）含义：LL(1)分析方法（也叫预测分析法）：是指从左到右扫描、最左推导(LL)和只查看一个当前符号（括号中的 1）。

2）判断一个文法是否是LL(1)文法的充要条件：

1. 文法不含左递归，

2. 对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若

A→α 1|α 2|…|α n则FIRST(α i)∩FIRST(α j)＝φ(i≠j)

3. 对文法中的每个非终结符A，若它存在某个候选首符集包含ε，则FIRST(α i)∩FOLLOW(A)=φ i=1,2,...,n如果一个文法G满足以上条件，则称该文法G为LL(1)文法。

(5)LL(1)文法分析表的构造与运用

这类题目，主要就是判断文法是否满足LL(1)文法的三个充要条件，分为以下几步：

1）首先将文法分解，判断是否有左递归好，有的话肯定不是LL(1)文法；

2）算非终结符的First集合和Follow集合，具体方法请参见期中考试的提纲，其实最本质

的要抓住first集合是U

?a…，Follow集合石…Ua…即可。

3）算Select集合，书上没有提到Select集合，计算Select集合实质就是计算First(α)，当然考试时不一定非要写成Select集合形式，可以直接计算First(α)来判断交集是否为空，从而是否为LL(1)文法，请看考题1。

4）至于判断一个句子的分析过程，大家注意一下，所给的句子不一定是能通过该文法分析出来的，实际上在分析之前可以自己根据文法推推看，请看考题1.

5）分析表中没有填的空格代表出错，如果分析时遇到了代表该句子不符合该文法。

考题1：判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表并分析句子aabe 的分析过程。（15分）

S→aD D→STe|εT→bM M→bH H→M|ε

分析：判断一个文法是否为LL(1)文法是否为LL(1)文法，主要就是判断是否满足LL(1)文法的充要条件，有一个不满足就不是LL(1)文法。对于aabe根据文法S?aD?aSTe?aaDTe?aaTe?aabMe由于M不能为空字ε，所以最后肯定推不出来，也就是该句子不能由该文法推出，出错。

当然一般题目都是LL(1)文法，否则题目就不好往下做，没有意义。

答：(1)经分析该文法无左递归；

依次计算：

First(aD)={a} First(Ste)={a}

Follow(D)={# b} First(bM)={b}

First(bH)={b} First(M)={b} Follow(H)={ e }

∵First(Ste)∩Follow(D)=ФFirst(M)∩Follow(H)=Ф

∴该文法是LL(1)文法

LL(1)分析表如下：

编译原理实验指导

编译原理实验指导实验安排：上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。实验报告：上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。

实验一词法分析一、实验目的通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。二、实验预习提示 1．词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则 →|ID|ID →|NUM →a|b|…|z|A|B|…|Z →1|2|…|9|0 →+|-|*|/|=|（|）|{|}|：|，|；|＜|＞|! →＞=|＜=|！=|== →/* →*/ 三、实验过程和指导 1.阅读课本有关章节，明确语言的语法，画出状态图和词法分析算法流程图。 2.编制好程序。 3.准备好多组测试数据。 4.程序要求程序输入/输出示例：

四川大学编译原理期末复习总结

一、简答题 1.什么是编译程序答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术答：优化技术1—删除公共子表达式优化技术2—复写传播优化技术3—删除无用代码优化技术4—对程序进行代数恒等变换（降低运算强度）优化技术5—代码外提优化技术6—强度削弱优化技术7—删除归纳变量优化技术简介——对程序进行代数恒等变换（代数简化）优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构；用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)；并对静态语义进行审查。 8.代码优化须遵循哪些原则答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么答：

编译原理实验中间代码生成

实验四中间代码生成一．实验目的：掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result）三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: ";

编译原理实验报告实验一编写词法分析程序

编译原理实验报告实验名称：实验一编写词法分析程序实验类型：验证型实验指导教师：何中胜专业班级：13软件四姓名：丁越学号：电子邮箱：实验地点：秋白楼B720 实验成绩：日期：2016年3 月18 日

一、实验目的通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。二、实验过程以编写PASCAL子集的词法分析程序为例 1.理论部分（1）主程序设计考虑主程序的说明部分为各种表格和变量安排空间。数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中（编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。还有一些为造表填表设置的变量。主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程，输出错误编号。 2.实践部分

编译原理实验报告

院系：计算机科学学院专业、年级： 07计科2大班课程名称：编译原理学号姓名：指导教师： 2010 年11月17 日组员学号姓名

实验名称实验一：词法分析实验室9205 实验目的或要求通过设计一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。具体要求：输入为某语言源代码，达到以下功能：程序输入/输出示例：如源程序为C语言。输入如下一段： main() { int a,b; a=10; b=a+20; } 要求输出如下（并以文件形式输出或以界面的形式输出以下结果）。（2，”main”）（5，”（“）（5，”）“）（5，”{“} （1，”int”）（2，”a”）（5，”,”）（2，”b”）（5，”;”）（2，”a”）（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”}“）要求：识别保留字：if、int、for、while、do、return、break、continue等等，单词种别码为1。其他的标识符，单词种别码为2。常数为无符号数，单词种别码为3。运算符包括：+、-、*、/、=、>、<等；可以考虑更复杂情况>=、<=、!= ；单词种别码为4。分隔符包括：“，”“；”“（”“）”“{”“}”等等，单词种别码为5。

编译原理概念期末总结复习

翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。编译过程的五个阶段： 1、词法分析任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。 2、语法分析任务：在词法分析的基础上，根据语言规则，把单词符号串分解成各类语法单位。 3、语义分析和中间代码产生任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。 4、优化任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。 5、目标代码生成任务：把中间代码变换成特定机器上的低级语言代码。编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标代码生成器、表格管理和出错处理。编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。词法规则：指单词符号的形成规则。（也就是正规式）语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。空字：不包含任何符号的序列。闭包：中所有的符号组成的集合。上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。上下文无关文法的四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生式。终结符号也就是不可再分的基本符号。非终结符号是用来代表语法范畴，表示一定符号串的集合。开始符号是语言中我们最感兴趣的语法范畴。产生式是定义语法范畴的书写规则。句子：文法中从开始符号推导的终结符号串。句型：从开始符号推导的符号串。语言：文法中所有句子的集合。程序语言的单词符号分为五种：关键字、标识符、常数、运算符和界符。二元式表示：（种类，属性）正规式的运算符有三种：或，连接和闭包。优先顺序是：闭包，连接，或。 DFA怎么识别字：若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字是a，则称a可为DFA所识别。 DFA怎么识别空字：若DFA的初态结点同时又是终态结点，则空字可为DFA所识别。NFA怎么识别字：若存在一条从某一初态结点到终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于a，则称a可为NFA识别。 NFA怎么识别空字：若M的某些结点即是初态又是终态结点，或者存在一条从某个初态结点到某个终态结点的空通路，那么，空字可为M所识别。语言的语法结构是用上下文无关文法描述的。语法分析分为两类：自上而下分析法，自下而上分析法。自上而下分析法面临的问题：1.文法的左递归问题。2.回溯3.成功可能是暂时的，产生虚假匹配。4.难于知道输入串中出错的确切位置。5.效率低，代价高。

编译原理实验报告

编译原理实验报告班级姓名：学号：自我评定：

实验一词法分析程序实现一、实验目的与要求通过编写和调试一个词法分析程序，掌握在对程序设计语言的源程序进行扫描的过程中，将字符形式的源程序流转化为一个由各类单词符号组成的流的词法分析方法。二、实验内容根据教学要求并结合学生自己的兴趣和具体情况，从具有代表性的高级程序设计语言的各类典型单词中，选取一个适当大小的子集。例如，可以完成无符号常数这一类典型单词的识别后，再完成一个尽可能兼顾到各种常数、关键字、标识符和各种运算符的扫描器的设计和实现。输入：由符合或不符合所规定的单词类别结构的各类单词组成的源程序。输出：把单词的字符形式的表示翻译成编译器的内部表示，即确定单词串的输出形式。例如，所输出的每一单词均按形如（CLASS，VALUE）的二元式编码。对于变量和常数，CLASS字段为相应的类别码；VALUE字段则是该标识符、常数的具体值或在其符号表中登记项的序号（要求在变量名表登记项中存放该标识符的字符串；常数表登记项中则存放该常数的二进制形式）。对于关键字和运算符，采用一词一类的编码形式；由于采用一词一类的编码方式，所以仅需在二元式的CLASS字段上放置相应的单词的类别码，VALUE字段则为“空”。另外，为便于查看由词法分析程序所输出的单词串，要求在CLASS字段上放置单词类别的助记符。三、实现方法与环境词法分析是编译程序的第一个处理阶段，可以通过两种途径来构造词法分析程序。其一是根据对语言中各类单词的某种描述或定义（如BNF），用手工的方式（例如可用C语言）构造词法分析程序。一般地，可以根据文法或状态转换图构造相应的状态矩阵，该状态矩阵同控制程序便组成了编译器的词法分析程序；也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序的另外一种途径是所谓的词法分析程序的自动生成，即首先用正规式对语言中的各类单词符号进行词型描述，并分别指出在识别单词时，词法分析程序所应进行的语义处理工作，然后由一个所谓词法分析程序的构造程序对上述信息进行加工。如美国BELL实验室研制的LEX就是一个被广泛使用的词法分析程序的自动生成工具。总的来说，开发一种新语言时，由于它的单词符号在不停地修改，采用LEX等工具生成的词法分析程序比较易于修改和维护。一旦一种语言确定了，则采用手工编写词法分析程序效率更高。四、实验设计 1）题目1：试用手工编码方式构造识别以下给定单词的某一语言的词法分析程序。语言中具有的单词包括五个有代表性的关键字begin、end、if、then、else；标识符；整型常数；六种关系运算符；一个赋值符和四个算术运算符。参考实现方法简述如下。单词的分类：构造上述语言中的各类单词符号及其分类码表。表I 语言中的各类单词符号及其分类码表单词符号类别编码类别码的助记符单词值

编译原理实验报告一

实验一词法分析程序实现一、实验目得与要求通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法二、实验内容基本实验题目：若某一程序设计语言中得单词包括五个关键字begｉｎ、end、if、then、elsｅ；标识符；无符号常数；六种关系运算符；一个赋值符与四个算术运算符，试构造能识别这些单词得词法分析程序（各类单词得分类码参见表Ｉ）。表Ｉ语言中得各类单词符号及其分类码表输入:由符合与不符合所规定得单词类别结构得各类单词组成得源程序文件。输出：把所识别出得每一单词均按形如(CLASS，VＡLUE）得二元式形式输出,并将结果放到某个文件中。对于标识符与无符号常数，CＬASS字段为相应得类别码得助记符;V AL ＵＥ字段则就是该标识符、常数得具体值；对于关键字与运算符,采用一词一类得编码形式，仅需在二元式得CLASS字段上放置相应单词得类别码得助记符，V ALUE字段则为“空". 三、实现方法与环境词法分析就是编译程序得第一个处理阶段，可以通过两种途径来构造词法分析程序.其一就是根据对语言中各类单词得某种描述或定义(如BＮF)，用手工得方式（例如可用Ｃ语言)构造词法分析程序。一般地,可以根据文法或状态转换图构造相应得状态矩阵,该状态矩阵连同控制程序一起便组成了编译器得词法分析程序;也可以根据文法或状态转换图直接编写词法分析程序。构造词法分析程序得另外一种途径就是所谓得词法分析程序得自动生成，即首先用正规式对语言中得各类单词符号进行词型描述,并分别指出在识别单词时,词法分析程

《编译原理》实验指导书

《编译原理》实验指导书实验目的和内容编译原理实验的目的是使学生将编译理论运用到实际当中，实现一个简单语言集的词法、语法和语义分析程序，验证实际编译系统的实现方法，并加深对编译技术的认识。实验内容共需实现编译器的词法、语法和语义分析程序三个组成部分。要求学生必须完成每个实验的基本题目要求，有余力的同学可尝试实验的扩展要求部分。实验报告要求每人针对所完成的实验内容上交一份实验报告，其中主要包括三方面内容：1、实验设计：实验采用的实现方法和依据（如描述语言的文法及其机内表示，词分析的单词分类码表、状态转换图或状态矩阵等，语法分析中用到的分析表或优先矩阵等，语法制导翻译中文法的拆分和语义动作的设计编写等）；具体的设计结果（应包括整体设计思想和实现算法，程序结构的描述，各部分主要功能的说明，法以及所用数据结构的介绍等）。 2、程序代码：实验实现的源程序清单，要求符合一般的程序书写风格，有详细的注释。 3、实验结果分析：自行编写若干源程序作为测试用例，对所生成的编译程序进行测试（编译程序的输入与输出以文件的形式给出）；运行结果分析（至少包括一个正确和一个错误单词或语句的运行结果）；以及改进设想等。注意事项 1、电子版实验报告和源程序在最后一次机时后的一周内上交。（每个同学上交一个压缩文件，其命名格式为“学号_姓名.rar”，内含实验报告和一个命名为“源程序” 的文件夹。注意提交的源程序应是经过调试、测试成功的较为通用的程序，并应有相应的注释、运行环境和使用方法简介。） 2、不接受不完整的实验报告和没有说明注释的源程序，或者说明与程序、运行结果不符合的作业。特别鼓励：扩展题目 1、为亲身经历一个小型编译器的开发全过程，触摸一下与实际编译器开发相关的工作，大家可以自由组成3人左右的小组，推举组长，模拟一个团队分工协作开发大型软件的实战环境，融入软件工程的思想规范和一般理论方法，初步体验从系统分析设计、编码测试到交付维护的一个完整编译器软件的开发过程。要求组长为每个小组成员分配主要负责的任务，完成相应的分析设计员、程序员和测试员等角色的工作，并以小组为单位提交一份实验报告和源程序，在报告封面上写明每个同学主要完成和负责的部分。 2、以组为单位完成的实验内容至少必须整合词法、语法和语义三个部分的实验，对于选定的适当规模的文法（如C语言的一个大小适宜的子集），进行系统的总体设计、功能分析、编码测试等工作。完成一个从对源程序的词法分析开始，到中间代码生成的完整的编译器前端的开发，使所涉及到的编译系统的各个组成模块有机地衔接在一起，提交一份完整的实验报告和源程序，并将以下几个方面描述清楚：

编译原理学习心得

编译原理学习心得编译原理学习心得1 编译程序在计算机科学与技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。而“编译原理”这门课程一直以来是国内外大学计算机相关专业的重要课程。因为它的知识结构贯穿程序设计语言、系统环境以及体系结构，能以相对的视角体现从软件到硬件以及软硬件协同的整机概念。其理论基础又涉及形式语言与自动机、数据结构与算法等计算机学科的许多重要方面，为联系计算机科学理论和计算机系统的典范。虽然编译原理这门课程在大多数的人里认为枯燥无味，学起来就像看天书一样。然而学习这门课程还是有一定的好处的。比如可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的，可以更加客观的比较不同语言的差异，并且学习新的语言的效率也会更加高，语言转换也会更加游刃有余。不学“编译原理”这门课程的话，自己的编程思想会很浅显。而且编程也只仅仅停留在编程上，无法深入理解其中的原理。学习编译原理的话，从文法、正规式、NFA与DFA的定义，下手，要用心动脑去体会编译原理学习心得2

从联系最紧密的操作系统来说吧，你写多线程/多进程的程序就得和操作系统的知识打交道。写多线程得加锁吧，临界区、死锁的四个条件之类的标准的操作系统的内容吧(不得不吐槽一下，某国内一线电商干了三年的程序猿，写多线程居然不知道加锁，也是醉了)。进程间通信的几种方式什么管道、socket、共享内存等，这也是操作系统的内容吧。文件系统，这也是经常要打交道的东西。还有内存什么的，你做Android 开发，这些里边有很多东西都在系统层面被封装好了，但是你要是不知道原理，一旦出了错根本无从调试，况且你该不会打算写一辈子写Android 就是填逻辑吧。然后，是编译原理，普通的程序猿是接触不到编译器或者虚拟机的开发的。但是这并不意味着编译原理就用不到。说个最常见的读取配置文件，只要你的配置文件有自定义的语法，你就要用编译原理的东西。还有类似于自动生成代码啦、正则表达式啦这些都算是编译原理的内容。你既然是写Java 的不了解虚拟机怎么可以，最基本的字节码总是需要能看懂的吧，分析一些疑难杂症的时候字节码还是很有用的。最后，是计算机原理，如果只是做应用开发的话计算机原理其实不必要掌握的多深入，但是一些基本的概念还是要清楚的。比如寄存器、缓存、中断什么的，关键的时候可以帮助你调试。在一些对性能要求非常高的场合，也是很有作用的。此外，学了

编译原理实验指导书2010

《编译原理》课程实验指导书课程编号：课程名称：编译原理/Compiler Principles 实验总学时数： 8 适用专业：计算机科学与技术、软件工程承担实验室：计算机学院计算机科学系中心实验室、计算机技术系中心实验室一、实验教学的目的与要求上机实习是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实习题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的2次上机实验都属于一种设计类型的实验，每个实验的训练重点在于基本的编译技术和方法，而不强调面面俱到；实验的目的是旨在使学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容；培养学生编制算法的能力和编程解决实际问题的动手能力。要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法设计和程序代码的编写；上机时应随带有关的编译原理教材或参考书；要学会程序调试与纠错。每次实验后要交实验报告，实验报告的内容应包括：（1）实验题目、班级、学号、姓名、完成日期；（2）简要的需求分析与概要设计；（3）详细的算法描述；（4）源程序清单；（5）给出软件的测试方法和测试结果；（6）实验的评价、收获与体会。开发工具：（1）DOS环境下使用Turbo C；（2）Windows环境下使用Visual C++ 。考核：实验成绩占编译原理课程结业成绩的10%。三、单项实验的内容和要求：要求每个实验保证每个学生一台微机。实验一（4学时）：单词的词法分析程序设计。（一）目的与要求 1．目的通过设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。

编译原理实验报告总结

学年第学期《编译原理》实验报告学院（系）：计算机科学与工程学院班级：11303070A 学号：11303070*** 姓名：无名氏指导教师：保密式时间：2016 年7 月

目录 1．实验目的 (1) 2．实验内容及要求 (1) 3．实验方案设计 (1) 3.1 编译系统原理介绍 (1) 3.1.1 编译程序介绍 (2) 3.1.2 对所写编译程序的源语言的描述 (2) 3.2 词法分析程序的设计 (3) 3.3 语法分析程序设计 (4) 3.4 语义分析和中间代码生成程序的设计 (4) 4. 结果及测试分析 (4) 4.1软件运行环境及限制 (4) 4.2测试数据说明 (5) 4.3运行结果及功能说明 (5) 5．总结及心得体会 (7)

1．实验目的根据Sample语言或者自定义的某种语言，设计该语言的编译前端。包括词法分析，语法分析、语义分析及中间代码生成部分。 2．实验内容及要求（1）词法分析器输入源程序，输出对应的token表，符号表和词法错误信息。按规则拼单词，并转换成二元形式；滤掉空白符，跳过注释、换行符及一些无用的符号；进行行列计数，用于指出出错的行列号，并复制出错部分；列表打印源程序；发现并定位词法错误；（2）语法分析器输入token串，通过语法分析，寻找其中的语法错误。要求能实现Sample 语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while语句、do while语句等。（3）语义分析和中间代码生成输入token串，进行语义分析，修改符号表，寻找其中的语义错误，并生成中间代码。要求能实现Sample语言或自定义语言中几种最常见的、基本的语法单位的分析：算术表达式、布尔表达式、赋值语句、if语句、for语句、while 语句、do while语句等。实验要求：功能相对完善，有输入、输出描述，有测试数据，并介绍不足。3．实验方案设计 3.1 编译系统原理介绍编译器逐行扫描高级语言程序源程序，编译的过程如下： (1).词法分析识别关键字、字面量、标识符(变量名、数据名)、运算符、注释行(给人看的，一般不处理)、特殊符号(续行、语句结束、数组)等六类符号，分别归类等待处理。 (2).语法分析一个语句看作一串记号(Token)流，由语法分析器进行处理。按照语言的文法检查判定是否是合乎语法的句子。如果是合法句子就以内部格式保存，否则报错。直至检查完整个程序。 (3).语义分析语义分析器对各句子的语法做检查：运算符两边类型是否相兼容；该做哪些类型转换(例如，实数向整数赋值要"取整")；控制转移是否到不该去的地方；是

编译原理实验报告

《编译原理》实验报告软件131 陈万全132852

一、需求分析通过对一个常用高级程序设计语言的简单语言子集编译系统中词法分析、语法分析、语义处理模块的设计、开发，掌握实际编译系统的核心结构、工作流程及其实现技术，获得分析、设计、实现编译程序等方面的实际操作能力，增强设计、编写和调试程序的能力。通过开源编译器分析、编译过程可视化等扩展实验，促进学生增强复杂系统分析、设计和实现能力，鼓励学生创新意识和能力。 1、词法分析程序设计与实现假定一种高级程序设计语言中的单词主要包括五个关键字begin、end、if、then、else；标识符；无符号常数；六种关系运算符；一个赋值符和四个算术运算符，试构造能识别这些单词的词法分析程序。输入：由符合和不符合所规定的单词类别结构的各类单词组成的源程序文件。输出：把所识别出的每一单词均按形如（CLASS，VALUE）的二元式形式输出，并将结果放到某个文件中。对于标识符和无符号常数，CLASS字段为相应的类别码的助记符；VALUE字段则是该标识符、常数的具体值；对于关键字和运算符，采用一词一类的编码形式，仅需在二元式的CLASS字段上放置相应单词的类别码的助记符，VALUE字段则为“空”。 2、语法分析程序设计与实现选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的

一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式>→<项> | <算术表达式>+<项> | <算术表达式>-<项> <项>→<因式>|<项>*<因式>|<项>/<因式> <因式>→<运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F和i 代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID······输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 3、语义分析程序设计与实现对文法G2[<算术表达式>]中的产生式添加语义处理子程序，完成运算对象是简单变量（标识符）和无符号数的四则运算的计值处理，将输入的四则运算转换为四元式形式的中间代码。输入：包含测试用例（由标识符、无符号数和+、?、*、/、(、)构成的算术表达式）的源程序文件。输出：将源程序转换为中间代码形式表示，并将中间代码序列输出到文件中。若源程序中有错误，应指出错误信息二、设计思路 1、词法分析程序设计与实现 1)单词分类为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。

计算机题库编译原理试题汇总

编译原理实验-词法分析器的设计说明

集美大学计算机工程学院实验报告课程名称：编译原理班级：指导教师：：实验项目编号：实验一学号：实验项目名称：词法分析器的设计实验成绩：一、实验目的通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。二、实验容编写一个词法分析器，从输入的源程序（编写的语言为C语言的一个子集）中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）三、实验要求 1、词法分析器的功能和输出格式词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符 2 别单词的类型，将标识符和常量分别插入到相应的符号表中，增加错误处理等。 3、编程语言不限。

四、实验设计方案 1、数据字典本实验用到的数据字典如下表所示：

3、实验程序 #include #include #include #include //判断读入的字符是否为字母 bool isLetter(char c){ if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')){ return true; } else return false; } //判断读入的字符是否为数字 bool isDigit(char c){ if(c >='0' && c <= '9'){ return true; } else return false; } //判断是否为关键字 bool isKey(char *string) { if(!strcmp(string,"void") || !strcmp(string,"if")|| !strcmp(string,"for")|| !strcmp(string,"wh ile") || !strcmp(string,"do")|| !strcmp(string,"return")|| !strcmp(stri ng,"break") || !strcmp(string,"main")|| !strcmp(string,"int")|| !strcmp(strin g,"float")|| !strcmp(string,"char") || !strcmp(string,"double")|| !strcmp(string,"String"))

编译原理实验报告

编译原理实验报告课程：编译原理系别：计算机系班级：11网络姓名：王佳明学号：110912049 教师：刘老师实验小组：第二组 1

实验一熟悉C程序开发环境、进行简单程序的调试实验目的： 1、初步了解vc++6.0环境； 2、熟悉掌握调试c程序的步骤：实验内容： 1、输入下列程序，练习Turbo C 程序的编辑、编译、运行。 #include main() { printf(“Programming is fun.\n”); } 2、分析程序，预测其运行结果，并上机检测你的预测。 #include main() { printf(“*\n”); printf(“* * *\n”); printf(“* * * * *\n”); printf(“* * * * * * *\n”); } 3、下面是一个加法程序，程序运行时等待用户从键盘输入两个整数，然后求出它们的和并输出。观察运行结果（程序输出），上机验证该程序。 #include main() { int a,b,c; printf(“Please input a,b:”); scanf(“%d,%d”,&a,&b); c=a+b; printf(“%d+%d=%d\n”,a,b,c); } 2

实验二词法分析器一、实验目的：设计、编制、调试一个词法分析子程序－识别单词，加深对词法分析原理的理解。二、实验要求： 1.对给定的程序通过词法分析器弄够识别一个个单词符号，并以二元式(单词种别码，单词符号的属性值)显示。而本程序则是通过对给定路径的文件的分析后以单词符号和文字提示显示。 2.本程序自行规定： (1)关键字"begin","end","if","then","else","while","write","read", "do", "call","const","char","until","procedure","repeat" (2)运算符："+","-","*","/","=" (3)界符："{","}","[","]",";",",",".","(",")",":" (4)其他标记如字符串，表示以字母开头的标识符。 (5)空格、回车、换行符跳过。在屏幕上显示如下： ( 1 , 无符号整数) ( begin , 关键字) ( if , 关键字) ( +, 运算符) ( ；, 界符) ( a , 普通标识符) 三、使用环境： Windows下的visual c++6.0; 四、调试程序： 1.举例说明文件位置：f：、、11.txt目标程序如下： begin x:=9 if x>0 then x:=x+1; while a:=0 do 3

编译原理实验1

大学学生实验报告开课学院及实验室：年月日实验目的设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。针对表达各类词语的一组正规表达式，设计一个确定化的最简的有限自动机，对输入的符号串进行单词划分及词类识别。实验容将词法分析器分解为以下几个部分： 1.正规表达式的解析：将正规表达式中的符号分解为常量字符、正规表达式标识符和正规表达式运算符，然后基于正规表达式运算将正规表达式分解为更小的正规表达式（通过正规表达式运算符进行串接）。 2.正规表达式到NFA的转换：根据转换规则，基于正规表达式运算，将正规表达式转换为非确定有限自动机，并确定各类词的终止状态。

3.NFA的确定化：通过计算各状态的传递闭包，将NFA确定化，并确定各类词的终止状态。 4.最小化：通过子集法，求得最简的确定有限自动机，并确定各类词的终止状态。例如：分析C语言子集的词法 1）关键字 main if else int return void while （都是小写）2）专用符号 = + —* / < <= < >= = = != ；：，{ } [ ] ( ) 3）其他模式（正规表达式） STRING::=" [^"]* ID::=letter(letter|digit)* INT::=digit digit* letter::= a|…|z|A|…|Z digit::= 0|…|9 4）空格由空白、制表符和换行符组成空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段通常被忽略。部分单词符号对应的种别码

词法分析程序的功能输入：所给文法的源程序字符串输出：二元组（syn, token或sum）构成的序列。其中syn 为单词种别码；token 为存放的单词自身字符串；sum为整型常量（作为常量的值）。实现时，可将单词的二元组用结构进行处理代码： #include #include