2-1

采用自顶向下分析，文法必须( )。 (3分)

消除左递归消除右递归消除回溯提取公共左因子

2-2

编译过程中,语法分析器的任务是（ ）。 (3分) ①分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的 ③分析语句和说明是如何构成程序的 ④分析程序的结构

②和③④②③④①②③④

2-3

常用的语法分析方法分为（ ）和自底而上分析方法两大类。 (2分)

自顶向下语法分析自左向右递归分析算符分析

2-4

语法分析程序的输出是（ ） 。 (3分)

表达式语法分析树四元式句子

2-5

语法分析程序的输入是 ( ) 。 (3分)

表达式句型程序单词

2-6

高级语言编译程序常用的语法分析方法中，递归分析法属于( ) 分析方法？ (3分)

自底而上自左至右自顶向下自右至左

2-7

一个文法G,若( ) ,则称它是LL(1)文法. (3分)

G中不含左递归G无二义性G中产生式不含左公因子G的LL(1)分析表不含多重定义

2-8

在自上而下的语法分析中，应从 ( )开始分析。 (3分)

句型句子文法开始符号句柄

2-9

在递归子程序方法中，若文法存在左递归，则会使分析过程产生( )。 (3分)

回溯非法调用无限循环有限次调用

2-10

LL（1）分析法中“1”的含义是（ ）。 (3分)

确定最左推导确定句柄在输入串中查看一个输入符号，可以确定用哪个产生式进行推导确定是否推导

2-11

LL（1）分析法中第一个"L"的含义是（ ）。 (3分)

确定句柄确定最左推导从左向右扫描输入串确定使用哪一个产生式进行展开

2-12

LL（1）分析法中第二个“L”的含义是 （ ）。 (2分)

分析过程采用最左推导确定句柄确定使用哪一个产生式进行展开确定是否推导

2-13

已知文法G[S]: 

S→ SaA| bB A → aB | c B → Bb | d

存在直接左递归，消除左递归后的文法是( )。 (4分)

S→bB S’ S’→aA S’ A→aB|c B→dB’ B’→bB’ S→bB S’ S’→aA S’|ε A→aB|c B →bB | d S→bB S’ S’→aA S’|ε A→aB|c B→dB’ B’→bB’|ε S→aA S’ S’→ bB S’|ε A→aB|c B→bB’ B'→dB’|ε

 2-14

已知文法G[S]:

S→ A| B A → aA |a B →bB |b

存在公共左因子，消除公共左因子后的文法是( )。 (4分)

S→ A| B A → aA |a B→ bB’ B ’ →B|ε S→ A| B A → aA’ A’ →A|ε B →bB |b S→ A| B A → aA’ A’ →A|ε B→ bB’ B ’ →B|ε S→ A| B A → aA’ A’ →A B→ bB’ B ’ →B|ε

 2-15

已知文法G[M]:

M→ MaH| H H → b(M) |(M)|c

存在直接左递归，消除左递归后的文法是( ) 。 (4分)

M→HM’ M’ → aHM’|ε H → b(M) |(M)| c M→aHM’ M → HM’|ε H → b(M) |(M)| c M→HM’ M’ →M'aH|ε H → b(M) |(M)| c M→HM’ M’ → aHM’ H → b(M) |(M)| c

 

2-16

已知文法G[S]:

S→ aSb| P P →bPc|bQc Q →Qa|a

文法消除左递归、提取左公因子后是( )。 (4分)

S→ aSb| P P →bP' P’→ Pc| Qc Q →aQ’ Q’ →aQ’|ε S→ PS’ S’→aSb P’|ε P →bPc|bQc Q →aQ’ Q ’→aQ ’|ε S→ aSb| P P’ → Pc| Qc Q →Qa|a S→ aSb| P P →bPc|bQc Q →aQ’ Q’ →aQ’|ε

 2-17

已知文法G[S]:

S→ AB A →Ba|ε B →Bb|D D→d|ε

文法消除左递归后是（ ）。 (4分)

S→ AB A→Ba|ε B→DB’ B’→bB'|ε D→d|ε S→ AB A →aA’ A’→Ba|ε B →DB’ B’→bB'|ε D→d|ε S→ AB A →aA’ A’→Ba|ε B →Db|D D→d|ε S→ AB A →aA’ A’→Ba|ε B →bD’ D’→d|ε

 

(4 分)

2-18

递归下降分析器由一组递归函数组成，且每一个函数对应文法的（ ）。 (3分)

一个终结符多个终结符一个非终结符多个非终结符

2-19

已知文法G[S]:

S → a | ∧ | (T) T→ T , S | S

文法消除左递归后是（ ）。 (3分)

S→ a | ∧ | (T) T→ ST′ T'→ ,ST′ |ε S→ a | ∧ | (T) T→ ST′|ε T'→ ,ST′ S→ a | ∧ | (T) T→, ST′ T'→ ST′ |ε S→ a | ∧ | (T) T→ ST′ T'→ ,ST |ε

 2-20

下述文法描述了C语言整数变量的声明语句：

　　G[D]: D→TL 　　    T→int | long | short 　　    L→id | L,id

文法消除左递归后是（ ）。 (4分)

D→TL 　　T→int | long | short 　　L→idL′ 　　L′→,idL′| ε D→TL 　　T→int | long | short 　　L→,idL′ 　　L′→idL′| ε D→TL 　　T→int | long | short 　　L→idL′| ε 　　L′→,idL′| ε D→TL 　　T→int | long | short 　　L→idL′| ε 　　L′→,idL′|id

 2-21

已知文法G[S]:

S → C$ C → bA |aB A → a|aC|bAA B→b|bC|aBB

文法消除左因子后是（ ） (4分)

S → C$ C → bA |aB A → aA’|bAA A’→C|ε B→bB’|aBB B’→C|ε S → C$ C → bA |aB A → aA’|bAA A’→C|ε B→b|bC|aBB S → C$ C → bA |aB A → a|aC|bAA B→bB’|aBB B’→C|ε S → C$ C → bA |aB A → aA’|bAA A’→C|ε|B B→bB’|aBB B’→C|ε

 2-22

已知文法G[A]:

A→aABe | a B→Bb | d

文法消除左递归、提取左公因子后是（ ）。 (2分)

A→aA’ A’→ABe |ε B→dB’ B’→bB’ |ε A→aA’ A’→ABeA’ |ε B→dB’ B’→bB’ |ε A→ABeA’ A’→aA’ |ε B→bB’ B’→dB’ |ε A→aA’ A’→ABe |ε B→bB’ B’→dB’ |ε

 2-23

已知文法G[S]:

S →(L) | aS’ S’→S |ε L→SL’ L’→,SL’ |ε

则FIRST(S)和FIRST(L')是( ) 。 (4分)

FIRST(S)={(，a} FIRST(L')={ ， ，ε} FIRST(S)={# ，(，a} FIRST(L')={ , ，ε} FIRST(S)={ (，a} FIRST(L')={ )，，，ε} FIRST(S)={# ，(，a} FIRST(L')={ )， , ，ε}

 2-24

已知文法G[S]:

S →(L) | aS’ S’→S |ε L→SL’ L’→,SL’ |ε

则FOLLOW(S)和FOLLOW(L’)是 ( ) 。 (4分)

FOLLOW(S)={ ,, ), #} FOLLOW(L’)={ )} FOLLOW(S)={ ,, ) } FOLLOW(L’)={ )} FOLLOW(S)={ ,, ), ε} FOLLOW(L’)={ )} FOLLOW(S)={ ,, ), #} FOLLOW(L’)={ ),#}

2-25

已知文法G[S]:

S →(L) | aS’ S’→S |ε L→SL’ L’→,SL’ |ε

则SELECT(S’ →S)和SELECT(S’→ ε)是( ) 。 (4分)

SELECT(S’→S)={(,a} SELECT(S’→ ε)={,,),#} SELECT(S’→S)={(,a} SELECT(S’→ε)= {,, ), #,ε} SELECT(S’→S)={(,a} SELECT(S’→ ε)= { ), #} SELECT(S’→S)={(,a} SELECT(S’→ ε)= {,, ) }

 2-26

已知文法G[S]:

S→eT|RT T→DR|ε R→dR|ε D→a|bd

求FIRST(S)=（ ）。 (4分)

{e }{e，d，a，b}{e，d }{e，d，a，b，ε}

 2-27

已知文法G[S]:

S→eT|RT T→DR|ε R→dR|ε D→a|bd

求FOLLOW(D)=（ ）。 (4分)

{d,e}{d,ε}{d,#}{a,d}

2-28

在自顶向下的语法分析方法中，分析的关键是( )。 (3分)

寻找句柄寻找句型消除递归选择候选式

多选题

3-1

已知文法G[A]: (20分)

A→aA’ A’→ABe |ε B→dB’ B’→bB’ |ε

(1)计算各非终结符的FIRST集合和FOLLOW集合,选择合适的选项将表1 补充完整;

表1 

(2)计算各产生式的SELECT集合,选择合适的选项将表2补充完整;

表2

(3)请选择合适选项将表3补充，并判断该文法是否是LL(1)文法？

表3

(4)构造文法LL(1)预测分析表，请将表4补充完整；

表4

(5) 表5中是串 aadbe#的推导过程， 选择合适的选项将其补充完整。

表5

{a} {#,d}{a,ε} {#,d}{b,ε} {e}{b,ε} {#,d}{a，#}{a}{#, d}{e}是不是对非终结符A和B,只有一个产生式，不用考虑select(B’→bB’)∩select(B’→ε)=φselect(A’→ε)∩select(B’→ε)=φA'→ABe 空 空 A'→ ε A'→ εA'→ABe 空 A’→ ε 空 A’→ ε空 空 B→dB’ 空 空空 B’→bB’ 空 B’→ ε 空空 B’→bB’ 空 空 B’→ ε#eBA adbe# A→aA’ 推导，aA’逆序入栈，输入指针不动#eB A’ dbe# A’→ ε推导, ε自动匹配，输入指针不动#eB dbe# B→dB’ 推导，dB’逆序入栈，输入指针不动#eB’d dbe# d匹配成功出栈，输入指针后移一位#eB’ be# B’→bB’ 推导，bB’逆序入栈，输入指针不动#ABe adbe# A→aA’ 推导，aA’逆序入栈，输入指针不动#dB’e dbe# d匹配成功出栈，输入指针后移一位#eBε dbe# B→dB’ 推导，dB’逆序入栈，输入指针不动

3-2

已知文法G[S]: (2分)

S→ a | ∧ | (T) T→ ST' T'→ ,ST' |ε

(1)请给出各非终结符的FIRST集合和FOLLOW集合,选择合适的选项将表1 补充完整;

表1

(2) 请给出各产生式的SELECT集合,选择合适的选项将表2补充完整;

表2

(3)请选择合适选项将表3补充，并判断该文法是否是LL(1)文法？

表3

(4) 构造文法LL(1)预测分析表，请将表4补充完整；

表4

(5) 下表中是句子(a,a)#的推导过程， 选择合适的选项将表5补充完整。

表5

{a, ∧,( } { # ，，， ) } {a, ∧,( } { ) } { , ,ε} { ) } { ( }{ a , ∧ , ( }{ ) }非终结符T只有一个产生式，不用考虑select(T'→ ,ST' )∩select(T’→ ε)=φ是 S→a S→∧ S→(T) 空 空 空 T→ST’ T→ST’ T→ST’ 空 空 空 空 空 空 T’→ε T’→,ST’ 空 {, , ε} {# , )} #)T’a a,a)# a匹配成功出栈，输入指针前移一位 {# , )}不是所有非终结符的SELCECT集合都要 考虑select(T'→ ,ST' )∩select(T’→ ε) ∩select(T→ST’)= φ 空 空 空 T’→ε T’→,ST’ T’→ε T→ST’ T→ST’ 空 T→ST’ 空 空 #)T’S a,a)# S→a 推导， a逆序入栈，输入指针不动 #)T’a a,a)# a匹配成功出栈，输入指针后移一位 )T’ ,a)# T’→,ST’ 推导，，ST’逆序入栈，输入指针不动 )T’S, ,a)# ,匹配成功出栈，输入指针后移一位 #)T’ )# T’→ε推导, ε自动匹配，输入指针不动 #)ε )# T’→ε推导, ε自动匹配，输入指针不动