编译原理必过宝典

更新时间:2024-06-13 09:33:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

第三章复习重点:1.文法与语言的对应关系

语言L(G)=L(G’) 文法G {bn | n>0} B→bB | b n{b | n≥0} P→bP |ε S→DB n{ab | n>0} D→a B→bB | b T→PD n{ba | n≥0} D→a P→bP |ε U→EU | E {(ab)n | n>0} E→ab V→AB mn{ab|m>0,n>0} A→aA | a B→bB | b W→AB mn{ab|m≥0,n>0} A→aA |ε B→bB | b nn {ab| n>0} X→aXb | ab {(akcd) nbn | k,n>0} {a2n+1bn| n>=0} Y→aaYb |a 文法G’ B→Bb | b P→Pb |ε S→aB B→Bb | b T→Pa P→Pb |ε U→Uab | ab V→aV | aB B→bB | b W→aW | B B→bB | b X→DXH | DH D→Acd A→aA |a H→b Y→KYH | a K→aa H→b

思路要点:注意结构拆分

技巧:如何将表示语言的通用字符串形式作适当的“切割”?

例:已知语言:L1 = {abc | x, y >= 0},给出此语言的文法,并证明此语言是上

x2xy

下文无关语言。

提示:该题实际上要求为相应语言设计上下文无关文法。

一个文法设计好后,严格来说应当证明此文法是否对应于该语言。

解:G[S]: S → AB A → ? | aAbb B → ? | cB

推导过程:

S ? AB +? axAb2xB /*使用A → aAbb x次*/ ? axb2xB /*使用A → ? 一次*/ ? axb2xcxB /*使用B → cB x次*/

? axb2xcx /*使用B →? 一次*/

举一反三:已知语言L2 = {axb2ycy | x, y >= 0},给出此语言的文法,并证明此语言是上下文无关语言。

解:G[S]: S → AB A → ? | aA B → ? | bBcc

练习:14:写出下列语言对应的文法 (1).{anbnambm|n,m≥0}

2. {1n0m1m0n|n,m≥0} 3. {1n0m1m0n|n≥0,m>0} 4. { anbmck|n,m,k≥0} G1: S—>AA G2: S—>AB A—>aAb|ε A—>aAb|ε B—>aBb|ε G: S—>1S0 S—>A A—>0A1 A—>ε G: S?1S0|A S?1S0|0A1 A?0A1|01 A?0A1|ε 2. 给出文法,证明文法符号串是否为文法的句型,若是句型,找出这个句型的所有短语、直接短语、句柄。 1. 令文法G[E]为: Z→bMb M→a|(L L→Ma) ① 符号串b(Ma)b是否为该文法的一个句型,并证明。 ② 若此符号串是句型,指出这个句型的所有短语、直接短语、句柄。 1)(5分)证明:S=> bMb=>b(Lb=>b(Ma)b 所以,符号串b(Ma)b是该文法的一个句型。 (2)(5分)短语: Ma), (Ma), b(Ma)b 直接短语: Ma) 句柄: Ma) 练习: (10分)已知文法G[T]: T→T*F | F ;F→F↑P | P ; P→(T) | i (1)用最右推导法证明β:T*P↑(T*F) 是G[T]的一个句型; (2)画出β的语法树; (3)写出β的全部短语、直接短语和句柄。 (1) T=>T*F=>T*F↑P=>T*F↑(T)=> T*F↑(T*F) =>T*P↑(T*F) 证毕。 (2) 如图 T T * F P F ↑ ( P T ) T 第3题 语法树 * F (3)短语:T*P↑(T*F) ;P↑(T*F) ;(T*F) ;T*F ;P 直接短语:T*F ;P

句柄: P

3. 证明一个文法是二义性文法。

证明下述文法G[S]是二义的。 (5分) S->iSeS|iS|i

解:

S S

i S e S i S

i S i S e S

可见,句型iises有两种不同的语法树,所以G[S]是二义的。 练习:证明下述文法G: S?aSbS|aS|d 是二义性文法。 解:

一个文法,如果存在某个句子有不只一棵语法分析树与之对应,那么称这个 文法是二义性文法。

句子aadbd有两棵语法树。如下图:

S S

a S S a S b

S a S b a d S

d d

d (1) (2)

由此可知,S?aSbS|aS|d定义的文法是二义性文法。 第四章: 重点:1. NFA?DFA的确定化及DFA的最小化。 2. 试写出描述语言L的正规式,构造能识别该语言L等价的NFA,再确定化 将下图所示的NFA确定化,再最小化。(2010年出过) 3 a X a 1 ? ? ? ? b 2 Y 4 a b 用子集法确定化如下表: 编号 A B C I A{X,1,2,4} B{1,2,3,4} Ia Ib B{1,2,3,4} C{1,2,4,Y} B {1,2,3,4} C{1,2,4,Y} C{1,2,4,Y} B {1,2,3,4} C{1,2,4,Y} 由于对于非终态的状态A和B来说,它们输入a、b的下一个状态都是一样的,故状态A和B可以合并,将合并后的状态重命名为A,而终态则重命名为B,则合并后的状态转换矩阵为: S A B 由此可以得到最小化的DFA,如下图所示: a A B b a A A b B B

练习1:给出接受字母表?={a,b},语言为以b开头,以aa结尾的字符串集合的正规表达式,并构造与之等价状态的DFA。(2010年出过) 答:依题意,以b开头,以aa结尾的字符串集合的正规表达式可写为: b(a|b)*aa 画NFA,如下图所示 a X b 1 a 2 a Y I Ia Ib 0 b 用子集法确定化如下表 {X}A - {1}B {1} B {1,2}C {1} B {1,2}C {1,2,Y}D {1} B {1,2,Y}D {1,2,Y}D. {1} B b A b B a b a C a D (10分)将下图的NFA确定化为DFA。(2011年重修卷A出过)

b

答:用子集法确定化如下表 用子集法对所给图的确定化 I {X,1,2} {1,2}.. {1,2,3} {1,2,Y} 确定化后如下图 Ia {1,2}.. {1,2}.. {1,2,Y} {1,2}.. Ib {1,2,3} {1,2,3} {1,2,3} {1,2,3} 状态 X 1 2 3

第五章重点:1.LL(1)的判别 要点:(1)计算First\\Follow\\Select集,然后判断是否是LL(1)文法。 (2)如果是LL(1)文法,则构造预测分析表。 (消除左递归和左公共因子也要了解) 例:(10分)已给文法 G[S] : S → PS' S' → aPS'| fS' |? P → qP'

P' → bP |?

(1)该文法是否是LL(1)文法,并说明理由。 (2)给出该文法的预测分析表。 答:(10 分)

(1)Select(S → PS')=first(P)={q} Select(S’→ aPS')={a} Select(S’→ fS')={f}

Select(S' →?)=follow(S’)=follow(S)={#} Select(P→ qP')={q}

Select(P' → bP)={b} Select( P' →?)=follow(P’)

=follow(P)={first(S’)-{ ?}}?follow(S)={a,f}?{#}={a,f,#} Select(S’→ aPS')? Select(S’→ fS') ? Select(S' →?)=? Select(P' → bP) ? Select( P' →?)=? 所以文法是LL(1)文法。 (7分)

(2)预测分析表:(3分) S S’ P P’ a aPS’ b f fS’ q PS’ qP’ # ? bP ? ? ? (15分)写出下列文法中各候选式的FIRST集和各非终结符的FOLLOW集,构造该文法的LL(1)分析表,并说明它是否为LL(1)文法。(2011年重修卷A出过) S → aA|BA A→ cB|? B → bB|? 各候选式的FIRST集 (4分) FIRST(aA)={a} FIRST(BA)={ b,c,? } FIRST(cB)={c} FIRST(?)={?} FIRST(bB)={ b } FIRST(?)={?} 各非终结符的FOLLOW集 (4分) FOLLOW(S)= {#} FOLLOW(A)= {#} FOLLOW(B)= { c,#} LL(1)分析表 (5分) a b c # S S → aA S → BA S → BA S → BA A A→ cB A → ? B B → bB B → ? B → ? 说明它是否为LL(1)文法 (2分) 判断1分,理由1分 因为LL(1)分析表无冲突,所以该文法是LL(1)文法。 2. 设文法G(S): S→^ | a | (T) T→T,S | S

⑴ 消除左递归;

⑵ 构造相应的FIRST和FOLLOW集合; ⑶ 构造预测分析表

解:(1)消除左递,文法变为G’[S]: S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε

此文法无左公共左因子。

(2)构造相应的FIRST和FOLLOW集合: FIRST(S)={a, ^, (}, FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ,FOLLOW(T)={}} FIRST(T’)={,, ε} ,FOLLOW(F)={)} (3)构造预测分析表: S T T’ a S→a T→ST’ ^ S→^ T→ST’ ( S→(T)' T→ST’ ) T’→ε , T’→,ST’ # 第七章重点:1. 识别活前缀的有限自动机的构造,判断某个文法是否是LR(0)文法,或SLR(1)文法或LR(1)文法,若不是,请说明理由,若是,构造相应的LR分析表。 2. 查LR分析表,进行句子的识别。 典型例题:文法G[S]及其LR分析表如下,请给出串baba#的LR分析过程。 (1) S → DbB (2) D → d (3) D → ε (4) B → a (5) B → Bba (6) B → ε LR分析表 状态 0 1 2 3 4 5 6 7 8 ACTION b r3 S4 r2 r6 r4 S7 r5 D s3 a S5 S8 # acc r6 r4 r1 r5 S 1 GOTO B 6 D 2 (注:答案格式为 步骤

答案:

状态栈 符号栈 输入串 ACTION GOTO) 步骤 状态

0 1 2 3 4 5 6 7 8

0 02 024 0245 0246 02467 024678 0246 01

符号 输入串 ACTION GOTO

baba# r3 2 baba# S4 aba# S5

ba# r4 6 ba# S7 a# S8

# r5 6 # r1 1 # acc

#

#D #Db #Dba #DbB #DbBb #DbBba #DbB #S

2. (8分) 已知拓广文法G[S’]:S’→S S→AS∣ε A→aA∣b

(1)试构造以LR(1)项目集为状态的识别活前缀的有穷自动机;

I5 I1 [S'→S.,#] I2 S [S→AS.,#] A S I0 A b I4 b I3 [A→b.,a/b/#] a a b [A→a.A,a/b/#] [A→.aA,a/b/#] [A→.b,a/b/#] a A I6

(2)试判断文法是否是LR(1)文法,并说明理由。 ( 1 ) I0: I2: I6: [S'→.S,#] [S→.AS,#] [S→.,#] [A→.aA,a/b/#] [A→.b,a/b/#] [S→A.S,#] [S→.AS,#] [S→.,#] [A→.aA,a/b/#] [A→.b,a/b/#] [A→aA.,a/b/#] (2)有穷自动机所有的状态都不含有“移进-归约”、“归约-归约”冲突,因

而该文法是LR(1)文法。

练习:. (20 分 ) 给定文法 G[S] : S → SaA|a A → AbS|b

⑴ (8 分 ) 请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵ (4 分 ) 请构造该文法的 LR(0) 分析表。

⑶ (4 分 ) 什么是 LR(0) 文法?该文法是 LR(0) 文法吗?为什么? ⑷ (4 分 ) 什么是 SLR(1) 文法?该文法是 SLR(1) 文法吗?为什么? 答:⑴拓广文法 1 分

G[S ′ ]: S ′→ S ⑴ S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸

该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA :

⑵ 该文法的 LR(0) 分析表: 状态 0 1 2 3 4 5 6 7 ACTION a S 2 S 3 r 3 r 2 r 5 S 2 r 4 /S 3 b r 3 S 5 r 2 /S 6 r 5 r 4 # acc r 3 r 2 r 5 r 4 GOTO S 1 7 A 4 ⑶ LR(0) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。 该文法不是 LR(0) 文法 因为存在冲突状态: I 4 和 I 7 ⑷ SLR(1) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态,冲突可用 FOLLOW 集解决。 该文法不是 SLR(1) 文法。 因为 FOLLOW(S)={a,b,#} ,所以无法解决冲突 。 其它练习可以直接做书本上我们布置的作业!

第八章:1.给出代码,写成代码对应的四元式(三地址码形式!) 重点:(1). 赋值语句 (2). For语句

(3).if …then语句 (4)数组赋值 (5).while语句

例:写出下面语句经语法制导翻译后所生成的四元式代码序列。 (共10分) if xc do c:=c+1 else x:=x+5 (依次翻译,再考虑回填!)

解:假设初始为100,则四元式代码序列为

100 if xc goto 104 103 goto 109 104 M:=C+1 105 C:=M 106 goto 102 107 N:=X+5 108 X:=N 109

(10分)试完成下列语句翻译的四元式序列。(2010年出过) while (A>B) do

if(C>D) then X:=Y*Z else X:=Y+Z; (1) if A>B goto (3) (2) goto (11) (3) _________ (4) goto (8) (5) _________ (6)X:=T1

(7) _________ (8)T2:=Y+Z (9)X:=T2

(10) _________ (11)

答:(3) if C

练习:已知源程序如下: prod:=0; i:=1;

write(x); end (* A *); procedure B; const n=7; var e,g; procedure D; var j,k;

begin (* D *) read(j,k); x:=x+j*n; call A; end ;(* D *) begin (* B *) call D; end ;(* B *) begin (* main *) read(x); call B; end. (* main *)

给出PL/0示意程序编译到D过程体时TABLE表的内容。其中TABLE表的格式可为下表。 TABLE表的格式 name kind level val adr size 解:问答第5题PL/0示意程序编译到D过程体时TABLE表的内容如下表。 TABLE表的内容 name main x A B n e g D j k kind procedure variable procedure procedure constant variable variable procedure variable variable level . 0 0 0 . 1 1 1 2 2 val . . . . 7 adr 0 dx 过程A的入口 过程B的入口 (待填) . dx dx+1 过程D的入口 dx dx+1 size 4 . 4 (待填5) . . . 5 由于A和B是并列过程,当编译到B过程时A过程体已经编译结束,A所定义的标识符不会再被使用,所以由B过程定义的标识符覆盖。

本文来源:https://www.bwwdw.com/article/gl66.html

Top