注:还有一份试卷将句型改为adT<(S)，与这个类似，大家自己做做，答案是
短语：a,(S),T<(S),adT<(S) 直接短语：a,(S) 句柄：a 最左素短语：SdG
下面两道例题大家看看，一定要会找短语，直接短语，句柄等.
考题：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→aS|ε(ε是空字)
{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|ε
3、按指定的类型给出下列语言的文法（10 分）
(1)L1={ ca n b m| n≥0,m>0 } 用正规文法。
S→cA A→aA|B B→bB|b 4、按指定的类型给出下列语言的文法（10 分）
(1)L1={a n b m c|n>=0,m>0}用正规文
法
(2)L2={ 0n a 1n b m| n>0，m ≥0} 用二型文法。S→AB A→0A1|0a1 B→bB|ε
S→aS|A A→bA|bB B→c (2)L2={a0n1n bd m|n>0,m>0}用二型
文法
S→AB A→aT T→0T1|01
B→bD D→dD|d
这是书P36 第11题的答案如下：大家作为练习，可以发现比上述题目简单的多了。
或者G4:
4、词法分析——
—正规式、NFA和
DFA之间的转化：
（1）这类题目一般是三者之间的转换，正规
式→NFA→确定化的DFA→最小化的DFA，有时已经给出NFA了，则只需要确定化为DFA和最小化就行了，一般每一步都是五分。具体怎么转换请参照我期中考试时整理的提纲，主要就是下面这幅关系对照图，因时间和篇幅限制不再追溯。
（2）注意优先级关系，闭包运算*最高，连接运算.次之，或运算|最低。
(3)考题1：
1）构造正则式a*b|(ab)*b对应的DFA。（15分）
①画出NFA
②确定化DFA
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 C
B D E
C - -
D D C
E F C
F - G
G F C
注：C和E是终态
③最小化DFA
首先将集合分为{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}.
考题2：将NFA确定化为DFA(10分)
NFA: DFA:
Ia Ib {X,0,1,3} {0,2,1,3} {3,Y} {0,2,1,3} {0,2,1,3} {1,3,Y} {3,Y} Ф{Y}
a b
S A B
A A C
B Ф E
C D E
D Ф F
E ФФ
G1:
S→AC
A→aAb|ab C→cC|εG2:
S→AB
A→aA|ε
B→bBc|bc
G3:
S→AB
A→aAb|ε
B→aAb|ε
G4:
S→1S0|A
A→0A1|ε
{1,3,Y} {2} {Y}
{2} Ф{1,3}
{Y} ФФ
{1,3} {2} {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：写出文法G[A]: A→Ba|Cb|c B→dA|Ae|f C→Bg|h消除左递归后的文法。
答：(1)经分析发现文法G[A]并无直接左递归；
(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
将A消除直接左递归A→dAaA’|fa A’|dAgb A’ |fgb A’|hb A’|c A’A’→ea A’| egb A’|?
此时，对于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)经分析该文法无左递归；
(2)①非终结符的First和Follow集合如下表所示
非终结符X First(X) Follow(X)
S a # b
D ε a # b
T b e
M b e
H ε b e
②将文法分解为：S→aD D→Ste D→ε T→bM M→bH H→M H→ε
依次计算：
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)分析表如下：
a b e #
S S→aD
D D→STe D→εD→ε
T T→bM
M M→bH
H H→M H→ε
(3)aabe的分析过程如下：
步骤符号栈输入串所用产生式
0 #S aabe#
1 #Da aabe # S→aD
2 #D abe#
3 #eTS abe# D→STe
4 #eTDa abe#
5 #eTD be#
6 #eT be# D→ε
7 #eMb be# T→bM
8 #eM e# 出错
考题2：判断下面文法是不是LL(1)文法，若是请构造相应的LL(1)分析表，写出aaabd的分析过程。S→aH H→aMd|d M→Ab|?A→aM|e
答：（1）可以判断该文法无左递归。
（2）将文法分解为分解：S→aH H→aMd H→d M→Ab M→?A→aM A→e 求First和Follow集合
非终结符X First(X) Follow(X)
S a #
H a,d #
M
?, a,e
d,b
A a,e b
求Select集合
Select(S→aH)=First(aH)={a} Select(H→aMd)=First(aMd)={a}
Select(H→d)={d} Select(M→Ab)=First(Ab)={a,e}
Select(M→?)=First(?)UFollow(M)= Follow(M)={d,b}
Select(A→aM)=First{aM}={a} Select(A→e)=First(e)={e}
∵Select(H→aMd) ∩Select(H→d)= Ф
Select(M→Ab) ∩Select(M→e)=Ф
Select(A→aM) ∩Select(A→e)= Ф
∴该文法是LL(1)文法。
（3）LL(1)分析表如下：
a d
b e
S S→aH
H H→aMd H→d
M M→Ab M→?M→?M→Ab
A A→aM A→e
aaabd#的分析过程如下：
步骤符号栈输入串所用产生式
0 #S aaabd#
1 #Ha aaabd # S→aH
2 #H aabd#
3 #dMa aabd# H→aMd
4 #dM abd#
5 #dbA abd# M→Ab
6 #dbMa abd# A→aM
7 #dbM bd#
8 #db bd# M→?
9 #d d#
10 # #
考题3：构造LL(1)分析方法的总控流程图
6、构造递归下降识别程序
这类题目首先看文法有无左递归和左公因子，有的话一定要消除，我期中给大家的答案错了，考题1为更正后的答案。
考题1：为文法G[E]： E → V | V+E V → N | N[E] N → i构造递归下降识别程序（10分）
解：（1）提取左公因子：E→VE’E’ →+E|?V →NV’V’→[E]|?N → i
(3)构造递归下降识别程序
PROCEDURE E；BEGIN
V; E’?
END; PROCEDURE E’；
IF SYM=‘+’ THEN
BEGIN
ADVANCE；
E
PROCEDURE Ｖ；
BEGIN
N;V’
END;
END
PROCEDURE F；
IF SYM=‘[’THEN
BEGIN
ADVANCE;
E；
IF SYM=‘]’
THEN
ADVANCE
ELSE ERROR END
ELSE ERROR; PROCEDURE N；IF SYM=‘i’ THEN
ADVANCE ELSE ERROR;
考题2：为文法G[E]:E→E+T|T T→T*F|F F→(E)|i构造递归下降识别程序
解：（1）消除左递归：E→TE' E'→+TE' | εT→FT'T'→*FT' | εF→(E) | i
(2)构造递归下降识别程序
PROCEDURE E；BEGIN
T；E' END；PROCEDURE T；
BEGIN
F；T'
END
PROCEDURE F；
IF SYM=‘i’ THEN
ADVANCE
ELSE
IF SYM=‘(’ THEN
BEGIN
ADVANCE;
E；
IF SYM=‘)’
THEN ADVANCE
ELSE ERROR
END
ELSE ERROR;
PROCEDURE E'；
IF SYM=‘+’ THEN
BEGIN
ADVANCE；
T；E'
END PROCEDURE T'；
IF SYM=‘*’ THEN
BEGIN
ADVANCE；
F；T'
END
7、自底向上分析法——LR（0）分析法
注：自底向上分析法本质是从输入串开始，逐步进行“归约”，直到文法的开始符号,其关键问题是寻找句柄。
自底向上分析法还有算符优先分析法，SLR(1),LR（1）等等，老师那天重点讲了一道LR(0)分析法的题目，他说算符优先分析法A卷不考，但是补考的B卷会考，按照他的意思，这次期末考试LR(0)是考定的了，
SLR(1),LR（1）应该不考，因为LR(0)分析法个人感觉也是所有题目中最繁的了，下面已老师讲的题目为例这，也是一份试卷上的考题，首先介绍一些相关知识。
（1）LR(0)项目：通俗点讲，文法G中的任何一个产生式的右部的任何位置添加一个圆点就成了LR(0)项目，比如A→Ab是产生式，则A→?Ab A→A?b A→Ab?都是该产生式对应的全部项目。项目动态的表示归约的一个阶段：对于项目A→A?b，可以这样理解它：“?”之前的A表示的是在识别Ab过程中已输入到栈终的部分；“?”之后的表示在识别Ab过程中期望出现的部分；“?”表示则是在识别Ab过程中当前的识别进度的定位。项目A→Ab?已经具备了识别Ab的一切条件，因此被称为归约项目。
项目可以分为以下四类：P→α?aβ称为移进项目其中, P→α?Xβ称为待约项目，其中X为非终结符，P→α?
称为归约项目，S’→S称为接收项目
（2）LR(0)的分析栈可以看成两部分状态栈
LR分析器的核心是一张分析表：
ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
GOTO[s，X]：状态s面对文法符号X时，下一状态是什么.
下面几张PPT大家看看，对基本概念有个印象：
这一章的概念较多较抽象，我一时半会也讲不完讲不清楚，这里不再赘述，直接看题目，知道怎么做就行，下面以一道考题这也是老师讲的原题为例讲解如何做这类题目，首先一般这种题目分三步走：
(1)拓广文法：假定文法G是一个以S为开始符号的文法，我们构造一个G'，它包含了整个G，但它引进了一个不出现在G中的非终结符S'，并加进一个新产生式S'→S，而这个S'是G'的开始符号。那么，我们称G'是G 的拓广文法。这样，便会有一个仅含项目S'→S.的状态，这就是唯一的“接受”态。
（2）构造识别文法活前缀的DFA:对于任意的项目即I,其闭包CLOSURE(I)计算方法如下，I中的所有项目都属于CLOSURE(I);如果P→α?Xβ,并且X为非终结符，则所有形如X→?γ的项目也属于ClOSURE(I)定义函数GO(I,X)，其中I是项目集，X是任意的文法符号（终结符，非终结符都可以），GO(I，X)=CLOSURE(J).J 是从I中项目出发后读取X后到达的后继项目,即J={P→αX?β| P→α?Xβ∈I}
有了上述CLOSURE和GO的定以后，从CLOSURE({S'→?S})出发，利用GO函数，产生出它在每个可能的文法符号下，要转移的项目集，再对新产生的项目集采取同样的方法直到没有新产生的项目集未被处理为止。
(4)根据计算出的项目集之间的关系画出DFA和LR(0)分析表，其中LR(0)构造方法如
下:
(5)对具体的句子运用LR(0)分析的方法如下：
每一项ACTION[s，a]所规定的四种动作:
1. 移进把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入
符号.
2. 归约指用某产生式A→β进行归约. 假若β的长度为r，归约动作是，去除
栈顶r个项，使状态s m-r变成栈顶状态，然后把(s m-r, A)的下一状态s’=GOTO[s m-r, A]和文法符号A推进栈.
3. 接受（即acc）宣布分析成功，停止分析器工作.
4. 报错
考题：构造文法G[E]的LR(0)分析表，并给出accd的分析过程。
（0）S'→E（1）E→aA （2）E→bB （3）A→cA （4） A→d （5）B→cB （6）B→d
分析：题中已经进行了推广文法，所以第一步就不需要了，下面就是开始构造识别活前缀的DFA，然后构造出LR（0）分析表，最后在进行分析，实际上对于accd我们自己可以先推一下，E?aA?acA?accA?accd所以该句子符合文法，那么最终构造出的LR（0）分析表对该句子进行分析后必定得到“acc”（接受的意思），否则构造的LR(0)分析表出错。
答：（1）构造识别活前缀的DFA:
I0=Closure({S'→?E })={ S'→?E, E→?aA, E→?bB }
I1=GO(I0,E)=Closure({S'→E?})={ S'→E? }
I2=GO(I0,a)=Closure({ E→a?A })={ E→a?A，A→?cA ，A→?d }
I3=GO(I0,b)=Closure({ E→b?B })={E→b?B, B→?cB ，B→?d }
（为了方便，下面计算中的Closure不再写了，直接给出答案,考试时可以不写，当然计算I0是必须要的）I4=GO(I2,A)={ E→aA?} I5=GO(I2,c)={ A→c?A，A→?cA ，A→?d }
I6= GO(I2,d)={ A→d?} I7=GO(I3,B)={ E→bB?}
I8= GO(I3,c)= { B→c?B，B→?cB ，B→?d } I9= GO(I3,d)={ B→d?}
I10= GO(I5,A) ={ A→cA?} GO(I5,c)=I5GO(I5.d)=I6
I11= GO(I8,B) { B→cB?} GO(I8,c)=I8GO(I8.d)=I9
画出DFA:
注：实际上构造LR(0)分析表时这个图没有必要画，根据上述计算结果即可填写下表。
（2）画出LR(0)分析表
注：至于怎么填这个表请参见上一页中的PPT,这里不再赘述,Action表中si代表跳转到第i个状态，ri代表选择文法中第i条规则进行归约,acc代表接受，即分析成功。Goto表中数字i代表跳转到第i个状态。（3）对accd#进行分析
步骤分析栈输入串操作
1 #0 accd# s2
2 #0a2 ccd# s5
3 #0a2c5 cd# s5
4 #0a2c5c
5 d# s6
5 #0a2c5c5d
6 # r4
6 #0a2c5c5A10 # r3
7 #0a2c5A10 # r3
8 #0a2A4 # r1
9 #0E1 # acc
8、写出表达式或者程序的中间形式
逆波兰式和四元式是三地址代码的两种记录表现形式，当然表示形式还有三元式、间接三元式等等，根据老师的意思应该不考，四元式和逆波兰式必考。
（1）逆波兰表达式
逆波兰表达式即后缀表达式，就是中缀表达式（也就是我们一般看到的表达式形式）对应的后续遍历结果，这个方法有很多，个人认为搞清楚运算优先级，观察一下就可写出，先算谁就将其对应的操作数写出，运算符放在后面就行很简单：
例如：写出下列各式的逆波兰表示
（1） -a-(b*c/(c-d) + (-b)*a)
(2) -A+B*C↑ (D/E)/F
解：（1）a@bc*cd-/b@a*+ -（2）A@BCDE/↑*F/+
注：@代表负号“-”
（2）四元式
四元式形式如下（op,arg1,arg2,Result）从左至右分别代表运算符，第一操作数，第二操作数,运算结果。
如：A + B * ( C - D ) + E / ( C - D ) ^N 对应的四元式序列如下:
四元式: (1) ( - ,C ,D,T1 ) (2) ( * ,B,T1,T2)
(3) ( + ,A,T2,T3) (4) ( - ,C,D,T4)
(5) ( ^ ,T4,N,T5) (6)( / ,E ,T5,T6)
(7) ( + ,T3 ,T6 ,T7)
注：T1,T2等等位存放结果的临时变量。
条件语句等四元式的表示
（jnz , a ,-- , p ) 表示 if a goto p
(jrop, x , y, p ) 表示 if x rop y goto p（rop代表关系运算符，如<,>等等） (j , --, --- , p ) 表示 goto p
例如：写出条件语句 IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1) 四元式序列
解：
(1)( j > , a ,0 ,(3))
(2)( j , -, -,(6))
(3)(+,x , 1 , T1)
(4)( := , T1,-, T2 )
(5)(j ,-, -,(9))
(6)( -, x,1, T3)
(7) (*, 4 ,T3 ,T4 )
(8) ( := , T4 ,-,x)
(9)
注意：（5）和（9）不能写丢，否则一分没有！上述四元式中第二第三个位置的“-”代表没有元素。
其实四元式就是对上述程序进行解释，如果满足则跳转到哪里执行，不满足则跳转到哪里执行，大家自己分析一下，应该能够看懂。
考题：根据要求写出下列表达式的中间形式。
（1）5+6*（a+b）写出表达式的逆波兰式逆波兰表达式为：56ab+*+
（2）
答案（1）答案（2）
if x > y then {
y:=y-1;
x：=y*z+10
}
else
x:= z + y
写出上述代码的四元式
或者三址码。
（有的试卷上问法是写出下列表达式三地址形式的中间表示，答案一样）(0)(j>,x,y,(2))
(1)(j,-,-,(8))
(2)(-,y,1,T1)
(3)(:=,T1,-,y)
(4)(*,y,z,T2)
(5)(+,T2,10,T3)
(6)( :=,T3,-,x)
(7)(j,-,-,(10))
(8)(+,z,y,T4)
(9)( :=,T4,-,x)
(10)
100: if x>y goto 102
101: goto 108
102: T1:=y-1
103: y:=T1
104: T2:=y*z
105: T3:=T2+10
106: x:=T3
107: goto 110
108: T4:=z+y
109: x:=T4
110:
注意：同上题，本题答案加红色的部分此外上述编号随意，从0开始也行从100开始也行。不能丢，否则一分没有！
9、参数传递
这种题目很简单，是送分题，一定要做对！
参数传递方式分为三种，值传递，地址传递和传名。
值传递过程中形参值的改变不会影响实参值的改变，地址传递形参值的改变导致对应是实参值的改变，传名传递类似于C语言中的宏展开，将实参原封不动的替换相应的形参（文字替换）。
请看下题：
(1)高级语言程序中常用的参数传递方式有哪些？请根据这些传递方式写出程序的运行结果。
static int a=1;
int p(int x,int y,int z) {
y=y+1;
z=z+x;
cout<<"In P "<{
int a=2;
int b=3;
p(a,a,a);
cout<<"In main "<}
分析：函数p中输出地a的值是全局变量a的值,与主函数中的局部变量a无关，不要被迷惑住，所以p 中输出的a就是1.传值时，由于实参值不受影响，所以a仍为2；
传地址时，在函数P中，将实参代入后a=a+1得a=3;再由a=a+a得到a=6;传名时，直接将实参带入形参，原来程序被替换为:a=a+1;a=a+a；将a=2代入得到结果为6.
答：①C语言中函数传递的方式有1)传值 2）传地址 3）传名
②运行结果：
1)传值方式：In P 1
In main 2 2)传地址：In P 1
In main 6
3）传名: In P 1
In main 6
（2）
Procedure p (x,y,z) ; begin
y:=y+1;
z:=z+x;
end; {p} begin
a:=2;
b:=3;
p(a+b , a , a) print a
end.
传值传递时输出结果为： 2 (实参值不受影响,a=2)
传地址传递时输出结果为：8 （a=2+1=3;a=3+5=8）
传名传递时输出结果为：9 (a=a+1；a=a+a+b;得到a=2+1=3;a=3+3+3=9)
10、程序分块、画DAG图
这个也比较简单，具体方法如下：
（1）分块就是将程序分成一块块的，主要就是确定每一块的入口语句：
1）寻找入口语句的方法：满足以下条件之一的都是入口语句
a）程序的第一条语句；b）条件转移语句或无条件转移语句可以转移到的语句
c)紧跟在条件转移语句后面的语句
2）对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。
3）凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。
例如划分基本块:
(1) read X
(2) read Y
(3) R:=X mod Y
(4) if R=0 goto (8)
(5) X:=Y
(6) Y:=R
(7) goto (3) 划分结果
(1) read X （入口语句）
(2) read Y
(3) R:=X mod Y （入口语句）
(4) if R=0 goto (8)
(5) X:=Y （入口语句）
(6) Y:=R
(7) goto (3)
(8) write Y
(9) halt (8) write Y （入口语句）
(9) halt
根据基本块画DAG图
上述图中的DAG只给出了最后完整的结果，老师要求在考试中需要把每一步都体现出来，具体请参见书上284页，因为篇幅限制所以不再赘述。另外，根据老师的意思可能会将DAG和四元式结合在一起考，给一段程序，先写出其四元式然后在画出其DAG图，四元式与DAG对应关系如下：根据下面的对应关系，DAG图很容易画出来。
0型: A:=B
(:=，B，-，A)
0型: goto (s)
(j，-，-，(s))
1型: A:=op B
(op，B，-，A)
2型：A:=B op C
(op，B，C，A)
2型:if B rop C goto (s)
(jrop，B，C，(s))
2型: A:=B[C]
(=[]，B[C]，-，A)
3型: D[C]:=B
([]=，B，-，D[C])
编译原理实验指导
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成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<<"请输入中缀表达式: ";
最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)
编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
编译原理实验报告实验一编写词法分析程序
编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：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.效率低，代价高。
编译原理结课论文
目录
1.绪论 概述 “编译原理”是一门研究设计和构造编译程序原理课程，是计算机各专业的一门重要的专业课。编译原理这门课程蕴含着计算机学科中解决问题的思路和解决问题的方法，对应用软件和系统软件的设计与开发有一定的启发和指导作用。“编译原理”是一门实践性很强的课程，要掌握这门课程中的思想，就必须要把所学到的知识应用于实践当中。而课程设计是将理论与实践相互联系的一种重要方式。 设计目的 课程设计是对学生的一种全面综合素质训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂很多，但也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构解决问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的能力。 设计题目及要求 基于这个学期所学习的内容以及自己所掌握到的知识，本次我所要设计的题目是赋值语句的四元式生成。
要求： （1）设计语法制导生成赋值语句的四元式的算法； （2）编写代码并上机调试运行通过； （3）输入一赋值语句； （4）输出相应的表达式的四元式； 2.背景知识 语法制导翻译方法 语法制导翻译的方法就是为每个产生式配上一个翻译子程序（称语义动作或语义子程序），并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段，它一方面指出了一个产生式所产生的符号串的意义，另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析的过程中，当一个产生式获得匹配（对于自顶向下分析）或用于规约（对于自底向上分析）时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。语法制导翻译分为自底向上语法制导翻译和自顶向下语法制导翻译。 属性文法 属性文法是编译技术中用来说明程序语言语义的工具，也是当前实际应用中比较流行的一种语义描述方法。属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征。属性文法是一种
编译原理实验报告一
实验一词法分析程序实现 一、实验目得与要求 通过编写与调试一个词法分析程序,掌握在对程序设计语言得源程序进行扫描得过程中,将字符流形式得源程序转化为一个由各类单词符号组成得流得词法分析方法 二、实验内容 基本实验题目：若某一程序设计语言中得单词包括五个关键字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．目的 通过设计、编制、调试一个具体的词法分析程序，加深对词法分析原理的理解，并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
编译原理实验报告
《编译原理》实验报告软件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)单词分类 为了编程的实现。我们假定要编译的语言中，全部关键字都是保留字，程序员不得将它们作为源程序中的标识符；作了这些限制以后，就可以把关键字和标识符的识别统一进行处理。即每当开始识别一个单词时，若扫视到的第一个字符为字母，则把后续输入的字母或数字字符依次进行拼接，直至扫视到非字母、数字字符为止，以期获得一个尽可能长的字母数字字符串，然后以此字符串查所谓保留字表（此保留字表要事先造好），若查到此字符串，则取出相应的类别码；反之，则表明该字符串应为一标识符。
计算机题库编译原理试题汇总
编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。
编译原理实验-词法分析器的设计说明
集美大学计算机工程学院实验报告 课程名称：编译原理班级： 指导教师：： 实验项目编号：实验一学号： 实验项目名称：词法分析器的设计实验成绩： 一、实验目的 通过设计编制调试一个具体的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 二、实验容 编写一个词法分析器，从输入的源程序（编写的语言为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"))
编译原理实验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
编译原理实验指导书(图)
编译原理 实 验 指 导 书
前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。
编译原理概念总结
第一章 引论 ? 为什么要用编译器 ? 与编译器相关的程序 ? 翻译步骤 ? 编译器中的主要数据结构 1、语言处理器 1、简单的说，一个编译器就是一个程序，它可以阅读以某一种语言（源语言）编写的程序，并把该程序翻译成一个等价的、用另一种语言（目标语言）编写的程序。 2、编译器的重要任务之一就是报告它在翻译过程中发现的源程序中的错误。 3、使用编译器是为了提高编程的速度和准确度。 4、与编译器相关的程序：解释程序（interpreter ）、汇编程序（assembler ）、连接程序（linker ）、装入程序（loader ）、预处理器（preprocessor ）、编辑器（editor ）、调试程序（debugger ）、描述器（profiler ）、项目管理程序（project manager ）。 5、解释器是另一种常见的语言处理器。它并不通过翻译的方法生成目标程序。从用户的角度来看，解释器直接利用用户提供的输入执行源程序中指定的操作。 6、一个源程序可能被分割成多个模块，并存放于独立的文件中。把源程序聚合在 一起的任务有时会由一个被称为预处理器（preprocessor ）的程序独立完成。预处理器还负责把那些称为宏的缩写形式转换为源语言的语句。 7、连接器（linker ）能够解决外部内存地址的问题。 8、加载器（loader ）把所有的可执行目标文件放到内存中执行。 2、一个编译器的结构 Output Source Program Front end Back end Object
1、将编译器看成黑盒，则源程序映射为在语义上等价的目标程序，而这个映射由两部分组成：分析部分和综合部分。 2、分析部分把源程序分解成多个组成要素，并在这些要素之上加上语法结构。 3、综合部分根据中间表示和符号表中的信息来构造用户期待的目标程序。 4、编译器的第一个步骤：词法分析（lexical）或扫描（scanning）。词法分析器读入组成源程序的字符流，并且将它们组成有意义的词素（lexeme）的序列。词法分析器产生词法单元（token）。 5、分隔词素的空格会被词法分析器忽略掉。 6、编译器的第二个步骤：语法分析（syntax）或解析（parsing）。语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示。 7、语义分析（static semantic analysis）：语义分析器使用语法树和符号表中的信息 来检查源程序是否和语言定义的语义一致。它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用。语义分析的一个重要部分是类型检查（type checking）。编译器检查每个运算符是否具有匹配的运算分量。 8、总的说，编译器的翻译步骤是：扫描程序----语法分析程序----语义分析程序---- 源代码优化程序----代码生成器----目标代码优化程序。 3、编译器结构中的主要数据结构 1、记号（token） 2、语法树（syntax tree） 3、符号表（symbol table） 4、常数表（literal table） 5、中间代码（intermediate code） 6、临时文件（temporary file） 4、将编译器分成了只依赖于源语言（前端（ front end））的操作和只依赖于目 标语言（后端（ back end））的操作两部分。 第二章词法分析 ? 扫描处理 ? 正则表达式 ? 有穷自动机 ? 从正则表达式到D FA ? 利用L e x自动生成扫描程序 1、Tokens记号标记：identifiers、keywords、integers、floating-point、symbols、strings、comments 1、使用正则表达式去描述程序语言tokens 2、一个正则表达式是归纳确定 3、一个正则表达式R描述一组字符串集合L(R) 4、L(R) = the language defined by R 5、所有的token都能用正则表达式表示 2、正则表达式： 1、基本正则表达式：他们是字母比哦啊中的单个字符且自身匹配
