构造识别文法活前缀dfa的三种方法

编译原理习题⼀、填空题:1-01.编译程序的⼯作过程⼀般可以划分为词法分析,语法分析,语义分析，之间代码⽣成,代码优化等⼏个基本阶段,同时还会伴有表格处理和出错处理.1-02.若源程序是⽤⾼级语⾔编写的,⽬标程序是机器语⾔程序或汇编程序,则其翻译程序称为编译程序.1-03.编译⽅式与解释⽅式的根本区别在于是否⽣成⽬标代码.1-04.翻译程序是这样⼀种程序,它能够将⽤甲语⾔书写的程序转换成与其等价的⽤⼄语⾔书写的程序. 1-05.对编译程序⽽⾔,输⼊数据是源程序,输出结果是⽬标程序.1-06.如果编译程序⽣成的⽬标程序是机器代码程序,则源程序的执⾏分为两⼤阶段:编译阶段和运⾏阶段.如果编译程序⽣成的⽬标程序是汇编语⾔程序,则源程序的执⾏分为三个阶段:编译阶段,汇编阶段和运⾏阶段.1-07.若源程序是⽤⾼级语⾔编写的，⽬标程序是机器语⾔程序或汇编程序，则其翻译程序称为编译程序。

1-08.⼀个典型的编译程序中，不仅包括词法分析、语法分析、中间代码⽣成、代码优化、⽬标代码⽣成等五个部分，还应包括表格处理和出错处理。

其中，词法分析器⽤于识别单词。

1-09.编译⽅式与解释⽅式的根本区别为是否⽣成⽬标代码。

2-01.所谓最右推导是指：任何⼀步αβ都是对α中最右⾮终结符进⾏替换的。

2-02.⼀个上下⽂⽆关⽂法所含四个组成部分是⼀组终结符号、⼀组⾮终结符号、⼀个开始符号、⼀组产⽣式。

2-03.产⽣式是⽤于定义语法成分的⼀种书写规则。

2-04.设G[S]是给定⽂法，则由⽂法G所定义的语⾔L(G)可描述为：L(G)＝{x│S x,x∈V T*}。

2-05.设G是⼀个给定的⽂法，S是⽂法的开始符号，如果S x（其中x∈V*），则称x是⽂法的⼀个句型。

2-06.设G是⼀个给定的⽂法，S是⽂法的开始符号，如果S x(其中x∈V T*),则称x是⽂法的⼀个句⼦。

3-01.扫描器的任务是从源程序中识别出⼀个个单词符号。

4-01.语法分析最常⽤的两类⽅法是⾃上⽽下和⾃下⽽上分析法。

编译原理实验报告实验名称自动生成LR（0）分析表实验时间 2013、12、10 院系计算机科学与电子技术系班级 2011级计算机软件学号 JV114023 JV114052 JV114078 段国顺立冬黄磊一、实验目的输入：任意的压缩了的上下文无关文法。

输出：相应的LR（0）分析表。

二、实验原理对于LR文法，我们可以自动构造相应的LR分析表。

为了构造LR分析表，我们需要定义一个重要概念——文法的规句型“活前缀”。

这种句柄之后不含任何符号的前缀称为活前缀。

在LR分析工作过程中的任何时候，栈里的文法符号（自栈底而上）X1X2 (X)m应该构成活前缀，把输入串的剩余部分配上之后即应成为规句型（如果整个输入串确实构成一个句子）。

因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。

对于一个文法G，我们可以构造一个有限自动机，它能识别G的所有活前缀，然后把这个自动机转变成LR分析表，按照该LR分析表进行LR分析，就能保证在分析的过程中，如果分析的句子是正确的，栈里的文法符号（自栈底而上）始终构成活前缀。

假若一个文法G的拓广文法G 的活前缀识别自动机中的每个状态（项目集）不存在下述情况：（1）既含移进项目又含归约项目；（2）含有多个归约项目，则称G是一个LR（0）文法。

该自动机的状态集合即为该文法的LR（0）项目集规族。

构造识别文法活前缀DFA有3种方法：（1）根据形式定义求出活前缀的正则表达式，然后由此正则表达式构造NFA 再确定为DFA；（2）求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA；（3）使用闭包函数（CLOSURE）和转向函数(GO(I,X))构造文法G’的LR(0)的项目集规族，再由转换函数建立状态之间的连接关系来得到识别活前缀的DFA。

符号串的前缀是指该符号串的任意首部，包括空串ε。

例如，对于符号串abc，其前缀有ε，a，ab，abc。

编译原理（清华⼤学-第2版）课后习题答案第三章N=>D=> {0,1,2,3,4,5,6,7,8,9}N=>ND=>NDDL={a |a(0|1|3..|9)n且 n>=1}(0|1|3..|9)n且 n>=1{ab,}a nb n n>=1第6题.(1) <表达式> => <项> => <因⼦> => i(2) <表达式> => <项> => <因⼦> => (<表达式>) => (<项>)=> (<因⼦>)=>(i)(3) <表达式> => <项> => <项>*<因⼦> => <因⼦>*<因⼦> =i*i(4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因⼦>+<项>=> <因⼦>*<因⼦>+<项> => <因⼦>*<因⼦>+<因⼦> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因⼦>+<项>=i+<项> => i+<因⼦> => i+(<表达式>) => i+(<表达式>+<项>)=> i+(<因⼦>+<因⼦>)=> i+(i+i)(6) <表达式> => <表达式>+<项> => <项>+<项> => <因⼦>+<项> => i+<项> => i+<项>*<因⼦> => i+<因⼦>*<因⼦> = i+i*i第7题第9题语法树ss s* s s+aa a推导: S=>SS*=>SS+S*=>aa+a*11. 推导:E=>E+T=>E+T*F语法树:E+T*短语: T*F E+T*F直接短语: T*F句柄: T*F12．短语：直接短语：句柄：13.(1)最左推导：S => ABS => aBS =>aSBBS => aBBS=> abBS => abbS => abbAa => abbaa 最右推导：S => ABS => ABAa => ABaa => ASBBaa => ASBbaa => ASbbaa => Abbaa => a1b1b2a2a3 (2) ⽂法：S → ABSS → AaS →εA → aB → b(3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa,直接短语： a1 , b1 , b2, a2 , ,句柄：a114 (1)S → ABA → aAb | εB → aBb | ε(2)S → 1S0S → AA → 0A1 |ε第四章1. 1. 构造下列正规式相应的DFA (1)1(0|1)*101NFA(2) 1(1010*|1(010)*1)*0NFA(3)NFA(4)NFA2.解：构造DFA 矩阵表⽰b其中0 表⽰初态，*表⽰终态⽤0，1，2，3，4，5分别代替{X} {Z} {X,Z} {Y} {X,Y} {X,Y,Z} 得DFA状态图为：3．解：构造DFA矩阵表⽰构造DFA的矩阵表⽰其中表⽰初态，*表⽰终态替换后的矩阵4．（1）解构造状态转换矩阵：{2，3} {0，1}{2，3}a={0,3}{2},{3},{0,1}{0,1}a={1,1} {0,1}b={2,2}（2）解：⾸先把M的状态分为两组：终态组{0}，和⾮终态组{1，2，3，4,5} 此时G=( {0},{1,2,3,4,5} ) {1,2,3,4,5}a={1,3,0,5} {1,2,3,4,5}b={4,3,2,5}由于{4}a={0} {1,2,3,5}a={1,3,5}因此应将{1,2,3,4,5}划分为{4},{1,2,3,5}G=({0}{4}{1,2,3,5}){1,2,3,5}a={1,3,5}{1,2,3,5}b={4,3,2}因为{1,5}b={4} {23}b={2,3}所以应将{1,2,3,5}划分为{1,5}{2,3}G=({0}{1,5}{2,3}{4}){1,5}a={1,5} {1,5}b={4} 所以{1,5} 不⽤再划分{2,3}a={1,3} {2,3}b={3,2}因为 {2}a={1} {3}a={3} 所以{2,3}应划分为{2}{3}所以化简后为G＝（ {0},{2},{3},{4},{1,5}）7.去除多余产⽣式后，构造NFA如下G={(0,1,3,4,6),(2,5)} {0,1,3,4,6}a={1,3}{0,1,3,4,6}b={2,3,4,5,6}所以将{0,1,3,4,6}划分为 {0,4,6}{1,3} G={(0,4,6),(1,3),(2,5)}{0,4,6}b={3,6,4} 所以划分为{0},{4,6} G={(0),(4,6),(1,3),(2,5)}不能再划分，分别⽤ 0，4，1，2代表各状态，构造DFA 状态转换图如下；b8．代⼊得S = 0(1S|1)| 1(0S|0) = 01(S|ε) | 10(S|ε) = (01|10)(S|ε)= (01|10)S | (01|10)= (01|10)*(01|10)构造NFA由NFA可得正规式为(01|10)*(01|10)=(01|10)+9.状态转换函数不是全函数,增加死状态8,G={(1,2,3,4,5,8),(6,7)}(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出(1,2,3,4,5,8)b=(2,6,7,8)(1,2,3,4,5,8)c=(3,8)(1,2,3,4,5,8)d=(3,8)所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4)G={(1,2,5,8),(3,4),(6,7)}(1,2,5,8)a=(3,4,8) 8应分出(1,2,5,8)b=(2,8)(1,2,5,8)c=(8)(1,2,5,8)d=(8)G={(1,2,5),(8),(3,4),(6,7)}(1,2,5)a=(3,4,8) 5应分出G={(1,2), (3,4),5, (6,7) ,(8) }去掉死状态8,最终结果为 (1,2) (3,4) 5,(6,7) 以1,3,5,6代替,最简DFA为b正规式:b*a(da|c)*bb*第五章1.S->a | ^ |( T )(a,(a,a))S => ( T ) => ( T , S ) => ( S , S ) => ( a , S) => ( a, ( T )) =>(a , ( T , S ) ) => (a , ( S , S )) => (a , ( a , a ) ) S=>(T) => (T,S) => (S,S) => ( ( T ) , S ) => ( ( T , S ) , S ) => ( ( T , S , S ) , S ) => ( ( S , S , S ) , S )=> ( ( ( T ) , S , S ) , S ) => ( ( ( T , S ) , S , S ) , S ) =>( ( ( S , S ) , S , S ) , S ) => ( ( ( a , S ) , S , S ) , S ) => ( ( ( a , a ) , S , S ) , S ) => ( ( ( a , a ) , ^ , S ) , S ) => ( ( ( a , a ) , ^ , ( T ) ) , S )=> ( ( ( a , a ) , ^ , ( S ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , S ) => ( ( ( a , a ) , ^ , ( a ) ) , a )S->a | ^ |( T )T -> T , ST -> S消除直接左递归：S->a | ^ |( T )T -> S T’T’ -> , S T’ | ξSELECT ( S->a) = {a}SELECT ( S->^) = {^}SELECT ( S->( T ) ) = { ( }SELECT ( T -> S T’) = { a , ^ , ( }SELECT ( T’ -> , S T’ ) = { , }SELECT ( T’ ->ξ) = FOLLOW ( T’ ) = FOLLOW ( T ) = { ）}构造预测分析表分析符号串（ a , a ）#分析栈剩余输⼊串所⽤产⽣式#S ( a , a) # S -> ( T )# ) T ( ( a , a) # ( 匹配# ) T a , a ) # T -> S T’# ) T’ S a , a ) # S -> a# ) T’ a a , a ) # a 匹配# ) T’，a) # T’ -> , S T’# ) T’ S , , a ) # , 匹配# ) T’ S a ) # S->a# ) T’ a a ) # a匹配# ) T’) # T’ ->ξ# ) ) # )匹配# # 接受2.E->TE’E’->+E E’->ξT->FT’T’->T T’->ξF->PF’F’->*F’F’->ξP->(E) P->a P->b P->∧SELECT（E－>TE’）=FIRST(TE’)=FIRST(T)= {（，a，b，^）SELECT（E’－>+E）={+}SELECT（E’－>ε）=FOLLOW(E’)= {#，)}SELECT（T－>FT’）=FIRST（F）= {（，a，b，^}SELECT（T’ —>T）=FIRST（T）= {（，a，b，^）SELECT(T’－>ε)=FOLLOW(T’)= {＋，#，)}SELECT(F －>P F’)=FIRST(F)= {（，a，b，^}SELECT(F’－>*F’)={*}SELECT(F’－>ε)=FOLLOW(F’)= {（，a，b，^，＋，#，）}3. S->MH S->a H->Lso H->ξK->dML K->ξL->eHf M->K M->bLM FIRST ( S ) =FIRST(MH)= FIRST ( M ) ∪FIRST ( H ) ∪{ξ}∪{a}= {a, d , b , e ,ξ} FIRST( H ) = FIRST ( L ) ∪{ξ}= { e , ξ}FIRST( K ) = { d , ξ}FIRST( M ) = FIRST ( K ) ∪{ b } = { d , b ,ξ}FOLLOW ( S ) = { # , o }FOLLOW ( H ) = FOLLOW ( S ) ∪{ f } = { f , # , o }FOLLOW ( K ) = FOLLOW ( M ) = { e , # , o }FOLLOW ( L ) ={ FIRST ( S ) –{ξ} } ∪{o} ∪FOLLOW ( K )∪{ FIRST ( M ) –{ξ} } ∪FOLLOW ( M )= {a, d , b , e , # , o }FOLLOW ( M ) ={ FIRST ( H ) –{ξ} } ∪FOLLOW ( S )∪{ FIRST ( L ) –{ξ} } = { e , # , o }SELECT ( S-> M H) = ( FIRST ( M H) –{ξ} ) ∪FOLLOW ( S )= ( FIRST( M ) ∪FIRST ( H ) –{ξ} ) ∪FOLLOW ( S )= { d , b , e , # , o }SELECT ( S-> a ) = { a }SELECT ( H->L S o ) = FIRST(L S o) = { e }SELECT ( H ->ξ) = FOLLOW ( H ) = { f , # , o }SELECT ( K->ξ) = FOLLOW ( K ) = { e , # , o }SELECT ( L-> e H f ) = { e }SELECT ( M->K ) = ( FIRST( K ) –{ξ} ) ∪FOLLOW ( M ) = {d，e , # , o }SELECT ( M -> b L M )= { b }4 . ⽂法含有左公因式，变为S->C $ { b, a }C-> b A { b }C-> a B { a }A -> b A A { b }A-> a A’ { a }A’-> ξ{ $ , a, b }A’-> C { a , b }B->a B B { a }B -> b B’ { b }B’->ξ{ $ , a , b }B’-> C { a, b }5. <程序> --- S <语句表>――A <语句>――B <⽆条件语句>――C <条件语句>――D <如果语句>――E <如果⼦句> --FS->begin A end S->begin A end { begin }A-> B A-> B A’ { a , if }A-> A ; B A’-> ; B A’ { ; }A’->ξ{ end }B-> C B-> C { a } B-> D B-> D { if }C-> a C-> a { a }D-> E D-> E D’ { if }D-> E else B D’-> else B { else }D’->ξ{; , end } E-> FC E-> FC { if }F-> if b then F-> if b then { if }⾮终结符是否为空S－否A－否A’－是B－否C－否D－否D’－是E－否F－否FIRST(S) = { begin }FIRST(A) = FIRST(B) ∪FIRST(A’) ∪{ξ} = {a , if , ; , ξ} FIRST(A’) ={ ; , ξ}FIRST(B) = FIRST(C) ∪FIRST(D) ={ a , if }FIRST(C) = {a}FIRST(D) = FIRST（E）= { if }FIRSR(D’) = {else , ξ}FIRST(E) = FIRST(F) = { if }FIRST(F) = { if }FOLLOW(S) = {# }FOLLOW(A) = {end}FOLLOW(A’) = { end }FOLLOW(B) = {; , end }FOLLOW (C) = {; , end , else }FOLLOW(D) = {; , end }FOLLOW( D’ ) = { ; , end }FOLLOW(E) = { else , ; end }FOLLOW(F) = { a }S A A’ B C D D’ E F if then else begin end a b ;6. 1.(1) S -> A | B(2) A -> aA|a(3)B -> bB |b提取（2），（3）左公因⼦(1) S -> A | B(2) A -> aA’(3) A’-> A|ξ(4) B -> bB’(5) B’-> B |ξ2.(1) S->AB(2) A->Ba|ξ(3) B->Db|D(4) D-> d|ξ提取（3）左公因⼦(1) S->AB(2) A->Ba|ξ(3) B->DB’(4) B’->b|ξ(5) D-> d|ξ3.(1) S->aAaB | bAbB(2) A-> S| db(3) B->bB|a4(1)S->i|(E)(2)E->E+S|E-S|S提取（2）左公因⼦(1)S->i|(E)(2)E->SE’(3)E’->+SE’|-SE’ |ξ5(1)S->SaA | bB(2)A->aB|c(3)B->Bb|d消除（1）(3)直接左递归(1)S->bBS’(2)S’->aAS’|ξ(3)A->aB | c(4) B -> dB’(5)B’->bB’|ξ6.(1) M->MaH | H(2) H->b(M) | (M) |b消除（1）直接左递归，提取（2）左公因⼦(1)M-> HM’(2)M’-> aHM’ |ξ(3)H->bH’ | ( M )(4)H’->(M) |ξ7. (1)1)A->baB4)B->a将1）、2)式代⼊3）式1)A->baB2)A->ξ3)B->baBbb4)B->bb5)B->a提取3）、4）式左公因⼦1)A->baB2)A->ξ3)B->bB’4)B’->aBbb | b5)B->a(3)1)S->Aa2)S->b3)A->SB4)B->ab将3）式代⼊1）式1)S->SBa2)S->b3)A->SB4)B->ab消除1）式直接左递归1)S->bS’2)S’->BaS’ |ξ3)S->b4)A->SB5)B->ab删除多余产⽣式4）1)S->bS’（5）1)S->Ab2)S->Ba3)A->aA4)A->a5)B->a提取3）4）左公因⼦1)S->Ab4)A’-> A |ξ5)B->a将3）代⼊1）5）代⼊21)S->aA’b2)S->aa3)A->aA’4)A’-> A |ξ5)B->a提取1）2）左公因⼦1)S-> aS’2)S’->A’b | a3)A->aA’4)A’-> A |ξ5)B->a删除多余产⽣式5）1)S-> aS’2)S’->A’b | a3)A->aA’4)A’-> A |ξA A’S’S将3）代⼊4）1)S-> aS’2)S’->A’b | a3)A->aA ’4)A’-> aA’ |ξ3)S’->a4)S’->b5)A->aA ’6)A’-> aA’ |ξ对2）3)提取左公因⼦1)S->aS’2)S’->aS’’3)S’’->A’b|ξ4)S’->b5)A->aA ’6)A’-> aA’ |ξ删除多余产⽣式5）1)S->aS’2)S’->aS’’3)S’’->A’b|ξ4)S’->b第六章1S → a | ∧ | ( T )T → T , S | S解：(1) 增加辅助产⽣式 S’→＃S＃求 FIRSTVT集FIRSTVT（S’）＝ {#}FIRSTVT（S）＝ {a ∧ ( }＝ { a ∧ ( } FIRSTVT (T) ＝ {,} ∪ FIRSTVT( S ) = { , a ∧ ( }求 LASTVT集LASTVT（S’）＝ { # }LASTVT（S）＝ { a ∧ )}LASTVT (T) ＝ { , a ∧ )}(2)因为任意两终结符之间⾄多只有⼀种优先关系成⽴，所以是算符优先⽂法(3)a ∧( ) , #F 1 1 1 1 1 1g 1 1 1 1 1 1f 2 2 1 3 2 1g 2 2 2 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1f 3 3 1 3 3 1g 4 4 4 1 2 1(4)栈优先关系当前符号剩余输⼊串移进或规约＃<·( a,a)# 移进＃( <· a ,a)# 移进＃(T <·, a)# 移进＃(T，<· a )# 移进＃(T,a ·> ) # 规约＃(T,T ·> ) # 规约＃(T =·) # 移进＃(T) ·> ＃规约＃T =·＃接受4.扩展后的⽂法S’→#S# S→S;G S→G G→G(T) G→H H→a H→(S)T→T+S T→S（1）FIRSTVT(S)={;}∪FIRSTVT(G) = {; , a , ( }FIRSTVT(G)={ ( }∪FIRSTVT(H) = {a , ( }FIRSTCT(H)={a , ( }FIRSTVT(T) = {+} ∪FIRSTVT(S) = {+ , ; , a , ( }LASTVT(S) = {;} ∪LASTVT(G) = { ; , a , )}LASTVT(G) = { )} ∪LASTVT(H) = { a , )}LASTVT(H) = {a, )}LASTVT(T) = {+ } ∪LASTVT(S) = {+ , ; , a , ) }构造算符优先关系表因为任意两终结符之间⾄多只有⼀种优先关系成⽴，所以是算符优先⽂法（2）句型a(T+S);H;(S)的短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H直接短语有: a T+S H (S)句柄： a素短语：a T+S (S)最左素短语：a(3)（4）不能⽤最右推导推导出上⾯的两个句⼦。

编译原理_国防科技大学中国大学mooc课后章节答案期末考试题库2023年1.对于文法G(S')，该文法识别活前缀的DFA如下图，状态I5包含的项目有G(S')：(0) S' → S(1) S → iSeS(2) S → iS(3) S → a【图片】答案:S → iSeŸS_S → ŸiSeS_S → ŸiS_S → Ÿa2.(a+b)/(c-d)对应的逆波兰式(后缀式)是答案:ab+cd-/3.表达式(a+b)/c-(a+b)*d对应的间接三元式表示如下，其中三元式表中第(3)号三元式应为间接码表三元式表(1) OP ARG1 ARG2 (2) (1) + a b (1) (2) / (1)c (3) (3) (4) (4) - (2) (3)答案:( *, (1), d)4.设AS 为文法的综合属性集, AI 为继承属性集, 则对于下面的属性文法G(P)定义中，AS和AI正确描述是产生式语义规则P → xQR Q.b:=R.d R.c:=1R.e:=Q.a Q → u Q.a:=3 R → v R.d:=R.c R.f:=R.e答案:AS={ Q.a, R.d, R.f } AI={ Q.b, R.c, R.e }5.考虑下面的属性文法G（S）【图片】过程enter(name, type)用来把名字name填入到符号表中，并给出此名字的类型type。

按照该属性文法，关于语句【图片】 , 【图片】 , 【图片】:integr的语义描述准确的是答案:说明 , , 是integer变量，把 , , 三个名字填入符号表中，并在类型栏中填上integer6.考虑下面的属性文法G(S)【图片】对于输入字符串abc进行自下而上的语法分析和属性计算，设S.u的初始值为5，属性计算完成后，S.v的值为答案:187.关于属性文法，下列说法中正确的是答案:属性文法是对上下文无关文法的扩展。

一、单项选择题概述部分1．构造编译程序应掌握 。

DA. 源程序B. 目标语言C. 编译方法D. 以上三项都是2．编译程序绝大多数时间花在 上。

DA. 出错处理B. 词法分析C. 目标代码生成D. 表格管理3．编译程序是对 。

DA. 汇编程序的翻译B. 高级语言程序的解释执行C. 机器语言的执行D. 高级语言的翻译4. 将编译程序分成若干“遍”，是为了 。

BA. 提高程序的执行效率B. 使程序的结构更为清晰C 利用有限的机器内存并提高机器的执行效率D. 利用有限的机器内存但降低了机器的执行效率词法分析部分1．DFA M(见图1-1)接受的字集为 。

DA. 以0开头的二进制数组成的集合B. 以0结尾的二进制数组成的集合C. 含奇数个0的二进制数组成的集合D. 含偶数个0的二进制数组成的集合 2．词法分析器的输出结果是 。

C A. 单词的种别编码 B. 单词在符号表中的位置C. 单词的种别编码和自身值D. 单词自身值3．正规式M1和M2等价是指 。

CA. M1和M2的状态数相等B. M1和M2的有向边条数相等C. M1和M2所识别的语言集相等D. M1和M2状态数和有向边条数相等4．词法分析器的加工对象是 。

CA ．中间代码B ．单词C ．源程序D ．元程序5．同正规式（a|b ）*等价的正规式为 。

DA ．(a|b)+B ．a*|b*C ．(ab)*D ．(a*|b*)+6. 两个DFA 等价是指： 。

DA. 这两个DFA 的状态数相同B. 这两个DFA 的状态数和有向弧条数都相等C. 这两个DFA 的有向弧条数相等D. 这两个DFA 接受的语言相同7. 下列符号串不可以由符号集S ＝{a,b}上的正闭包运算产生的是：（A ）A. εB. aC. aaD. ab8．称有限自动机A1和A2等价是指________。

DA ．A1和A2都是定义在一个字母表上的有限自动机B ．A1和A2状态数和有向边数相等C ．A1和A2状态数或有向边数相等图1-11D．A1和A2所能识别的字符串集合相等9．同正规式（a|b）+等价的正规式是_______。

1、已知文法G(S)：S→aS|bS|a(1)构造该文法的LR(0)项目集规范族(2)构造识别该文法所产生的活前缀的DFA。

(3)构造其SLR分析表，并判断该文法是否是SLR(1)文法。

解题思路构造LR(0)项目集规范族，有两种方法：一种是利用有限自动机来构造，另一种是利用函数CLOSURE和GO来构造。

本题采取第2种方法，通过计算函数CLOSURE和GO得到文法的LR(0)项目集规范族，而GO函数则把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA。

解答(1)将文法G(S)拓广为G(S’)：(0)S’→S(1)S→aS(2)S→bS(3)S→a构造该文法的LR(0)项目集规范族：I0=CLOSURE({S→·S})={S’ →·S, S→·aS, S→·bS, S→·a}I1=GO( I0, a)=CLOSURE({S→a·S , S→a·})={S→a·S , S→a·, S→·a S, S→·b S, S→·a }I2=GO(I0 , b)=CLOSURE({S→b·S })={ S→b·S, S→·aS,S→·bS, S→·a } I3=GO(I0 , S)=CLOSURE({S’ →S·})={ S’ →S·}GO(I1, a)=CLOSURE({S→a·S , S→a·})=I1GO(I2, b)=CLOSURE({S→b·S})=I2I4=GO(I1, S)=CLOSURE({S→aS·})={S→aS·}GO(I2, a)= CLOSURE({S→a·S , S→a·})=I1GO(I2, b)= CLOSURE({S→b·S})=I2I5=GO(I2, S)=CLOSURE({S→bS·})={ S→bS·}所以，项目集I0，I1，I2，I3，I4和I5构成了该文法的LR(0)项目集规范族。

练习5.1解答：输入(4*7+1)*2n,带注释的分析树如下：练习5.2解答: (1)根据表5.3中的语法制导定义建立表达式((a)+(b))的分析树和语法树(2)根据图5.17的翻译模式构造((a)+(b))的分析树和语法树练习5.3解答:设置下面的函数和属性：expr1||expr2:把表达式expr2拼写在表达式expr1后面。

deletep(expr):去掉表达式expr左端的‘（’和右端的‘)’。

E.expr,T.expr,F.expr:属性变量，分别表示E，T，F的表达式。

E.add,T.add,F.add,属性变量，若为true，则表示其表达式中外层有‘＋’号，否则无‘＋’号。

E.pmark,T.pmark,F.pmark,属性变量，若为true，表示E,T,F的表达式中左端为‘（’，右端是‘）’。

语法制导定义如下：产生式语义规则E -> E1 +T if(T.pmark==true)THEN E.expr=E1.expr||'+'||deletep(T.expr) ELSE E.expr:=E1.expr||'+'||T.expr;E.add:=true;E.pmark:=false;E -> T if(T.pmark==true)THEN E.expr:=deletep(T.expr)ELSE E.expr:=T.expr;E.add:=T.add;E.pmark:=false;T -> T1*F T.expr:=T1.expr||'*'||F.expr; T.add:=false;T.pmark:=false;T -> F T.expr:=F.expr; T.add:=F.add;T.pmark:=F.pmark;F -> (E) if(E.add==false)THEN BEGINF.expr:=E.expr;F.add:=false;F.pmark:=false;ENDELSE BEGINF.expr:='('||E.expr||')';F.add:=true;F.pmark:=true;END;F -> id F.expr:=id.lexval;F.add:=false;F.pmark:=false;练习5.4解答: (1)语法制导定义如下：产生式语义规则E -> E1+T if(E1.type==int) AND (T.type==int) THEN E.type:=intELSE E.type:=real;E -> T E.type:=T.type;T -> num T.type:=int;T -> num.num T.type:=real;(2)设E.pf和T.pf分别是E和T的前缀形式，||是两个字符串的连接，语法制导定义如下：产生式语义规则E -> E1+T if(E1.type==int) AND (T.type==int)THEN E.type:=intELSE BEGINE.type:=real;if(E1.type==int) AND (T.type==real)THEN E1.pf:='inttoreal'||E1.pfELSE if(E1.type==real)AND(T.type==int)THEN T.pf:='inttoreal'||T.pfEND;E.pf:='+'||E1.pf||T.pf;E -> T E.type:=T.type; E.pf:=T.pf;T -> num T.type:=int; T.pf:=int.lexval;T ->num.numT.type:=real; T.pf:=real.lexval;练习5.5解答: (1)用综合属性决定s.val的语法制导定义：产生式语义规则S -> L S.val:=L.val;S ->L1.L2S.val:=L1.val+L2.val*L2.p;L -> B L.val:=B.val; L.p:=2-1;L -> L1B L.val:=L1.val*2+B.val; L.p:=L.p*2-1;B -> 0 B.val:=0;B -> 1 B.val:=1;注：L.p表示恢复L.val的因子。

编译原理习题参考答案第⼆章2.构造产⽣下列语⾔的⽂法（2）{a n b m c p|n,m,p≥0}解： G(S) ：S→aS|X,X→bX|Y,Y→cY|ε（3）{a n # b n|n≥0}∪{cn # dn|n≥0}解： G(S)：S→X,S→Y,X→aXb|#, Y→cYd|# }（5）任何不是以0 打头的所有奇整数所组成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8, J→1|3|5|7|9}（6）（思考题）所有偶数个0 和偶数个1 所组成的符号串集合解：对应⽂法为 S→0A|1B|ε，A→0S|1C B→0C|1S C→1A|0B3.描述语⾔特点（2）S→SS S→1A0 A→1A0 A→ε解：L(G)={1n10n11n20n2… 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm 不全为零}该语⾔特点是：产⽣的句⼦中，0、1 个数相同，并且若⼲相接的1 后必然紧接数量相同连续的0。

（5）S→aSS S→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a5. (1) 解：由于此⽂法包含以下规则：AA→ε，所以此⽂法是0 型⽂法。

7.解：(1)aacb 是⽂法G[S]中的句⼦，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb 不是⽂法G[S]中的句⼦aacbccb 不能从S推导得到时，它仅是⽂法G[S]的⼀个句型的⼀部分，⽽不是⼀个句⼦。

11.解：最右推导:(1) S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上⾯推导中，下划线部分为当前句型的句柄。

对应的语法树为：3 假设M:⼈ W:载狐狸过河，G:载⼭⽺过河，C:载⽩菜过河6 根据⽂法知其产⽣的语⾔是L={a m b n c i| m,n,i≧1}可以构造如下的⽂法VN={S,A,B,C}, VT={a,b,c}P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c} 其状态转换图如下:7 (1) 其对应的右线性⽂法是:A →0D, B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2) 最短输⼊串011(3) 任意接受的四个串： 011,0110,0011,000011(4) 任意以1 打头的串.9．对于矩阵(iii)(1) 状态转换图：(2) 3型⽂法（正规⽂法）S→aA|a|bB A→bA|b|aC|a B→aB|bC|b C→aC|a|bC|b(3)⽤⾃然语⾔描述输⼊串的特征以a 打头，中间有任意个（包括0个）b,再跟a,最后由⼀个a,b 所组成的任意串结尾或者以b 打头，中间有任意个（包括0个）a,再跟b,最后由⼀个a,b 所组成的任意串结尾。

<编译原理>历年试题及答案一．（每项选择2分，共20分）选择题1．将编译程序分成若干个“遍”是为了_b__。

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

a.源程序b.目标语言c.编译方法d.以上三项都是3．变量应当c＿。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值4．编译程序绝大多数时间花在_d___上。

a.出错处理b.词法分析c.目标代码生成d.管理表格5．词法分析器的输出结果是_c___。

a.单词的种别编码b.单词在符号表中的位置c.单词的种别编码和自身值d.单词自身值6．正规式MI和M2等价是指__c__。

a.MI和M2的状态数相等b.Ml和M2的有向弧条数相等。

C.M1和M2所识别的语言集相等 d.Ml和M2状态数和有向弧条数相等7．中间代码生成时所依据的是—c。

a．语法规则b．词法规则c．语义规则d．等价变换规则8．后缀式ab+cd+/可用表达式__b_来表示。

a．a+b/c+d b．(a+b)/(c+d)c．a+b/(c+d)d．a+b+c/d9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。

a.动态存储b.栈式存储c.静态存储d.堆式存储10.堆式动态分配申请和释放存储空间遵守___d____＿原则。

a.先请先放b.先请后放c.后请先放d.任意二（每小题10分，共80分）简答题1.画出编译程序的总体结构图，简述各部分的主要功能。

2.已知文法G[E]:E→ET+|T T→TF*|F F→F^|a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.3．为正规式(a|b)*a(a|b)构造一个确定的有限自动机。

4．设文法G(S)：S→(L)|a S|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。

一．选择题(60分,每小题2分,答案请填写在答题纸上)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.以下( )不是DFA的组成部分。

A．有穷字母表B．初始状态集合C．终止状态集合Ｄ．有限状态集合8.正规式M1和M2等价是指( )。

A．Ml和M2的状态数相等B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等9. 下图所示的DFA M 接受的字集为( )。

A ．以0开头的二进制数组成的集合B ，以0结尾的二进制数组成的集合C ．含奇数个0的二进制数组成的集合D ．含偶数个0的二进制数组成的集合 10. 有文法G （S ）：S －＞aA| a |bC A －＞aS | bB B －＞aC | bA | b C －＞aB | bS则下列（ ）为L （G ）中的句子。

A ．a 100b 50ab 100 B ．a 1000b 500aba C ．a 500b 60aab 2a D ．a 100b 40ab 10aa11. 文法G[S]：S →xSx | y 所识别的语言是（ ）。

A ．xyxB ．(xyx)*C ．x n yx n (n ≥0)D ．x*yx*12. 给定语言L 为：所有以0开头，后接零个或多个10组成的符号串的集合，则描述它的正规文法G[S]应为（ ）。

1、已知文法：A → aAd|aAb|ξ判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串 #ab# 给出分析过程。

解：(0) A’→ A(1)A → aAd(2) A → aAb(3) A →ξ构造该文法的活前缀DFA：由上图可知该文法是SLR（1）文法。

构造SLR（1）的分析表：3、考虑文法：S →AS|b A→SA|aFollow(A) = first(S) = {b}+first(A)= {a,b}(1)列出这个文法的所有LR（0）项目(2)按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。

(3)这个文法是SLR的吗？若是，构造出它的SLR分析表。

(4)这个文法是LALR或LR（1）的吗？解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a(1)列出所有LR（0）项目：S’→·S S→·b A→·a S’→ S· S→b· A→a·S →·AS A→·SAS →A·S A→S·AS →AS· A→SA·(3)构造该文法的活前缀NFA：由上可知：I1 I3 I5 中存在着移进和归约冲突在I1中含项目：S’→ S·归约项 Follow(S’)={#}A →·a 移进项 Follow(S’)∩{a}=∮S →·b 移进项 Follow(S’)∩{b}=∮在I3中含项目：A →SA·归约项 Follow(A)={a,b}S →·b 移进项 Follow(A) ∩ {b}≠∮A →·a 移进项 Follow(A) ∩ {a}≠∮在I5中含项目：S →AS·归约项 Follow(S)={#,a,b}A →·a 移进项 Follow(S) ∩ {a}≠∮S →·b 移进项 Follow(S) ∩ {b }≠∮由此可知，I3、I5的移进与归约冲突不能解决，所以这个文法不是SLR （1）文法。

画一个DFA，它能够接受∑＝{0，1}上能够被5整除的二进制数。

二进制：接受0：等价于×2接受1：等价于×2 + 1101 0111000 51010 111000 N*210101 11000 N*2+1,2、写出正规式(a|b)(ba|a)*a的NFA并确定化。

（要求画出DFA对应的状态图）3．写出表达式A*(B*C-A)*B的逆波兰式、三元式、四元式。

4．构造正规式1(0|1)*101相应的NFA，并确定化、最小化。

5、已知文法G[E]:E→E+T|E-T|TT→T*F|T/F|FF→(E)|i(1)给出句型(i-i)*i的最左推导；(2)给出句型(i-i)*i语法树；(3)给出句型(i-i)*i的短语、直接短语、句柄。

6．已知文法G[A]，给出句型f(i,f(iD)D)的最左推导、语法树、短语、直接短语、句柄、最左素短语。

G[A]: A→f(L)L→BDD→,BDB→A | I 表7．已知文法G[S]，试给出句型(+)+aB*aB的最左推导、语法树、直接短语、句柄、最左素短语。

G[S]: S→B | SaB | +B→A | B+A | aAA→)S* | (8、对文法消除间接左递归和提取左公因子。

(1)A→aABc (2)A→a (3)A→d (4)E→Ta(5)E→b (6)T→EF (7)F→abA→aABc|a|d 有无间接左递归？？？？？？？A → (d|a)A’A’→a(BcA’|ε)排序 F T E左部非终结符下标 > 右部时改写●E→Ta → EFa →EabaE→bE→ Eaba |b●E→ bE’E’→ abaE’|ε9．构造下列文法G[A] 的LL(1)预测分析表：G[A]: A→BCc | gDBB→bCDE | εC→DaB | caD→dD |εE→gAf | c（1）求各非终结符的FIRST集和FOLLOW集B→εD→ε（2）文法G[A]的预测分析表10．将文法G[E]改写为等价的LL(1)文法，并给出相应的预测分析表。

竭诚为您提供优质文档/双击可除lr(0)项目集规范族的四类项目篇一：编译原理习题※填空题：1、编译阶段按前后端组合，可分为编译前端和编译后端，其中与目标机有关的阶段一般属于分析阶段，而与源语言相关的阶段一般属于综合阶段。

2、设文法g=（Vn，Vt，p，s），若p中的每一个规则a→β满足：a∈Vn，β∈(Vn∪Vt)*,则称此文法为0型文法。

3、已知m为一个确定的有穷自动机，m=（q，∑，q0，F，δ），则q表示一个有穷的状态集合;∑表示字母表，δ表示状态转换函数，q0是唯一的初始状态。

4、规范推导是指最右推导，每步推导只变换符号串中最右边的非终结符，其逆过程即最左规约，称为规范归约。

5、lR(0)项目集规范族中的项目可分为四类，即移进项目、待约项目、归约项目和接受项目，其中归约项目和归约项目或移进项目共存于一个项目集中会引起冲突。

6、表达式s:=a+b*c/d+(b-d)的逆波兰式表示为sabc*d/bd-++:=。

判断题：1、从功能上看，一个编译程序就是一个语言翻译程序。

t2、ＬＥＸ是一个语法分析程序的生成系统。

F3、一个句型的最左（直接）简单短语称为句柄。

t4、已证明文法的二义性是可判定的。

F5、一个ＮＦＡ一定能转换为ＤＦＡ。

t6、递归下降分析法是一种不确定的自顶向下分析法。

F简答：1、文法Ｇ是ll(1)文法的充要条件是什么？答：（1）.不能有左递归；（2）.ll(1)文法的分析表不出现多重定义即：对于文法g的每个非终结符a的任何两条不同规则a→α|β，下面条件成立：FiRst(α)∩FiRst(β)=φ即头符号集不相交。

假若β==*>ε，那么，FiRst(α)∩Follow(a)=φ，即α所能推出的符号串的头符号集中的元素不能出现在Follow(a)中。

2、将表达式a:=b*（c-d）/d：翻译成波兰后缀表达式。

答：abcd-d/*:=※填空题：1、对给定文法g[e]，由推导序列e=>e+t=>t+t=>i+t=>i+i可知：该推导为（最左）推导，从该推导序列可得到（5）个句型，其中的（i+i）同时也是句2、用四元组g=（Vn，Vt，p，s）表示文法，则其元素Vn表示（非终结符）集；元素Vt表示（终结符）集；元素p表示规则集；元素s表示开始符号，它必须是一个（至少在某个产生式的左部出现一次的非终结符）符号。

⼀、请选择符合题⽬描述和要求的选项,如果答案中包含多个选项,.⼀、请选择符合题⽬描述和要求的选项，如果答案中包含多个选项，注意选项的次序。

1、如果⼀个⽂法满⾜，则称该⽂法是⼆义⽂法。

A. ⽂法的某⼀句⾃存在两棵（包括两棵）以上不同的语法树B. ⽂法中存在某个句⼦，它有两个（包括两个）以上不同的最右（或最左）推导C. ⽂法中存在某个句⼦，它有两个（包括两个）以上不同的最右（或最左）归约D. 在进⾏归约时，⽂法的某些规范句型的句柄不惟⼀解 A B C D2、⼀个句型的最左称为该句型的句柄。

A. 短语B. 直接（简单）短语C. 素短语D. 终结符解 B3、在编译的过程中，符号表的主要作⽤是。

A. 帮助错误处理B. 辅助语法错误的检查C. 辅助语义的（即上下⽂有关的）正确性检查D. 辅助代码⽣成E. 辅助对⽬标程序的优化解 C D4、在编译过程中，编译程序可以找出源程序的全部错误和部分错误。

A. 语法B. 语义C. 语⽤D. 运⾏解 A B5、⼀个上下⽂⽆关⽂法G包括四个组成部分，他们依次为：⼀个表⽰语⾔的基本符号的集合，⼀个表⽰语⾔的语法成分的集合，⼀个以及⼀个集合。

A. 字符串B. 字母数字串C. 产⽣式D. 结束符号E. 开始符号G. ⾮终结符号H. 终结符号解 H G E C6、下述语⾔中属于上下⽂⽆关语⾔的是。

A. L1={wcw-1 |w-1为w的逆序，w ∈{a，b}*}B. L2={a n b m c n d m | n ≥1，m≥1}C. L3={a n b n c n | n≥0}D. L4={a n b m c m d n | n≥1，m≥1}解 A D7、设有⽂法G[S]：S→Ax∣ByA→By∣C wB→x∣B wC→y下列正规表达式中与⽂法G[S]定义同⼀语⾔的正规表达式是。

A. xw*y|xw*yx|ywxB. xw*y|xwxyz|ywxC. xwy|xw*xyx|ywxD. xwxy|xww*y|ywx解 A8、设有如图1所⽰的⾃动机。