一:文法G1:

E→ET+|T

T→TF*|F

F→FP↑|P

P→E|i

1.试证明符号串TET+*i↑是G1的一个句型(要求画出语法树).

2.写出该句型的所有短语,简单短句和句柄.

二:

1.给出下图FA的正规式.

a b

──→──→②

　→○①a↑↓ε

　　←──←──③

εb

2.已知正规文法G2:

S→aS|A

A→bB

B→aB|ε

试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.

三:

1.试写出一个上下文无关文法G3,它能产生配对的圆括号串(例如,(),(()),()(())等,甚至包含0对括号).

2.使用文法G3给出输入串(())()#的自上而下分析过程.

四:已知文法G4:

S→aAb|Sc|ε

A→aAb|ε

1.给出G4文法的LR(0)项目集规范族;

2.构造SLR分析表;

3.G4文法所定义的语言;

4.已知有如下文法及相应的LR分析表,试给出语句01001#的LR分析过程(填写下表).

S→AAA

A→1A

A→0

LR分析表:

───┬──┬──┬──┰──┬──

状态│1　│0　│#　┃S　│A　

───┼──┼──┼──╂──┼──

0　│S3│S4│┃1　│2

───┼──┼──┼──╂──┼──

1　│　　│　　│acc┃　　│

───┼──┼──┼──╂──┼──

2　│S3│S4│　　┃　　│5

───┼──┼──┼──╂──┼──

3　│S3│S4│　　┃　　│6

───┼──┼──┼──╂──┼──

4　│r3│r3│r3┃　　│

───┼──┼──┼──╂──┼──

5　│S3│S4│　　┃　　│7

───┼──┼──┼──╂──┼──

6　│r2│r2│r2┃　　│

───┼──┼──┼──╂──┼──

7　│　　│　　│r1┃　　│

───┴──┴──┴──┸──┴──

分析过程:

──────┬──────┬──────

　状态栈　│　符号栈│输入串

──────┼──────┼──────

　　　　　　│　　　　　　│

　　　　　　│　　　　　　│

　　　　　　│　　　　　　│

　　　　　　│　　　　　　│

　　　　　　│　　　　　　│

　　　　　　│　　　　　　│

　　　　　　│　　　　　　│

──────┴──────┴──────

五:

1.翻译下面语句成四元式中间代码序列和后缀式(逆波兰式);

while x+y>a do

if a<10 then a:=a+1 else x:=x-1;<>

2.翻译布尔表达式

(a>b) or (c=d) and not (e

成转移四元式序列(即四元式中仅包含(zθ,-,-,-)和(j,-,-,-)两类语句,其中θ为关系运算符.)

六:

1.有如下Fortran说明语句,试借助符号表登记等价环链EQ和相对数OFFSET,即填写下表的EQ栏和OFFSET栏.设每个整型量占1子编址.

integer a,b,c(10,10),d(10)

equivalence (a,d(8),c(5,5))

equivalence (b,c(5,8))

　符号表

┌───┬──────┬───┬───┐

│name│...│EQ│OFFSET│

├───┼──────┼───┼───┤

1│a│...│││

├───┼──────┼───┼───┤

2│b│...│││

├───┼──────┼───┼───┤

3│c│...│││

├───┼──────┼───┼───┤

4│d│...│││

└───┴──────┴───┴───┘

2.有如下pascal语言的程序轮廓,当运行该程序且第一次递归调用Q过程(即在过程Q中又调用了Q)时,数据区建立情况.假定各数据区首址用SP(i)(i=0,1,……)表示,试给出P,Q数据区的display表.

┌main

│┌P

││┌Q

│││Call Q

││└

││Call Q

│└

│┌R

││Call P

│└

│┌S

││Call R

│└

│Call S

└

七:已知如下流图,试给出回边与循环.

↓

　　　┌─→①←┐

　　　│　/ /　/

│↓　↓/

/②　③

/ / /↑

/↓↓/

┌→④──┐

　　　││　↓

││┌→⑤

　　　│↓/　│

　　　└─⑥←─┘