北京航空航天大學(xué)-程序設(shè)計(jì)語言原理ZY1906-大作業(yè)-語言設(shè)計(jì)規(guī)格說明書

1.語言設(shè)計(jì)的背景及范型

Python是解釋執(zhí)行的動(dòng)態(tài)語言，具有豐富的語法糖和類庫。缺點(diǎn)是執(zhí)行效率低；

并且動(dòng)態(tài)語言由于沒有構(gòu)建的過程，因此很多錯(cuò)誤只有等到運(yùn)行時(shí)才會(huì)發(fā)現(xiàn)，代碼檢

查工具的效率不高。

因此，我們想設(shè)計(jì)一種類Pascal的靜態(tài)類型的編譯型語言，既擁有高效的執(zhí)行效

率，又具有豐富的語言特性。

它的優(yōu)點(diǎn)有：

1、嚴(yán)格的結(jié)構(gòu)化形式，簡明靈活的控制結(jié)構(gòu)。

2、豐富完備的數(shù)據(jù)類型

3、運(yùn)行效率高

4、查錯(cuò)能力強(qiáng)，語言簡單易學(xué)

2.語言的語法、語義規(guī)格說明

2.1詞法EBNF

2.1.1詞法定義：

本語言的詞法包括以下幾大部分的類型定義：

2.1.2關(guān)鍵字：

本語言有20個(gè)關(guān)鍵字，在此將其定義為keyword類型，EBNF表達(dá)如下：

keyword::=begin|proc|while|var|func|is|do|array|in|record|if|let|

then|of|type|end|else|const|try|catch

2.1.3運(yùn)算符：

本語言有36種運(yùn)算符，同樣地，將其定義為Calculation類型，EBNF表達(dá)如下：

Calculation::=+|-1*|/|,|;|>|>=|<|<=|=|==|!=|(|)|{|)|[|]|A|

&&||||!|/*|*/|:|%|//|++|-|>>|<<|+=|-=|*=|/+

2.1.4數(shù)值類型：

本語言有7種數(shù)值類型，在此將其定義為Value類，EBNF表達(dá)如下：

valueType::=Integer|Char|Real|Boolean

另外

digit"0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"

Integer::=digit,{digit}

Real::=int,,int

Char::="a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"kn|"I"|"m"|"n"|

"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z"

Boolean::="0"I"1"

2.2語法EBNF

2.2.1命令

我們將Identifier,Integer_Literal,Character_Literal,Operator為原子操作，不

再進(jìn)一步定義。

Command::=

|V_name:=Expression

|Identifier(Actual_Parameter_Sequence)

|Command;Command

|beginCommandend

|letDeclarationinCommand

|ifExpressionthenCommandelseCommand

|whileExpressiondoCommand

|tryCommandcatch(Identifier:Type_denoter)Command

指稱語義：

execute:Commamd—(Environ-Store-Store)

executeK]envsto=

sto

executeRV:=E]envsto=

letvariableval=identifyEenvstoin

letval=evaluateEenvstoin

update_variable(sto,var,val)

executeKI(APS)]]envsto=

letprocedureproc=find(env,I)in

letargs=give_argumentsAPSenvstoin

procargssto

executeKC1；C2Renvsto=

executeC2env(executeClenvsto)

execute[beginCend]]=

executeC

execute[letDinC3envsto=

let(env',sto')=elaborateDenvstoin

executeC(overlay(env',env))sto'

executeRifEthenClelseC23envsto=

ifevaluateEenvsto=truth_valuetrue

thenexecuteClenvsto

elseexecuteC2envsto

execute[whileEdoCD=

letexecute_whileenvsto=

ifevaluateEenvsto=truth_valuetrue

thenexecute_whileenv(executeCenvsto)

elsesto

in

execute_while

execute[tryCcatch(I:T)CJ=

letexecute_catchenvsto=

evaluateCenvsto

ifevaluateIenvsto=Type_denoter

thenexecuteCenvsto

in

execute_catch

2.2.2表達(dá)式

Expression::=Integer_Literal

|Character_Literal

|V_name

|Identifier(Actual_Parameter_Sequence)

|OperatprExpression

|ExpressionOperatprExpression

|(Expression)

|letDeclarationinCommand

|ifExpressionthenCommandelseCommand

|{Record_Aggegate}

[Array_Aggregate]

*Identifier

|&Identifier

Record_Aggegate::=

|Identifier=Expression

|Identifier=Expression,Array_Aggregate

Array_Aggregate::=Expression

|Expression,Array_Aggregate

指稱語義：

evaluate:Expression一(Environ—Store-?Value)

evaluate_record:Record_Aggregate->(Environ-Store—Record_value)

valuate_array:Array_Aggregate^-(Environ^Store^Array_Value)

//evaluateEenvsto給出在環(huán)境env和存儲(chǔ)sto之下執(zhí)行E得到的值

//evaluaterecordRAenvsto給出在環(huán)境env和存儲(chǔ)sto之下對記錄聚集RA求值得

到的記錄“evaluatearrayAAenvsto給出在環(huán)境env和存儲(chǔ)sto之下對數(shù)組聚集

AA求值得到的數(shù)組

evaluate[IL]envsto=

integer(integer_valuationIL)

evaluate[CL]envsto=

character(character_valuationCL)

evaluate[V]envsto=

coerce(sto,identifyyenvsto)

evaluate[I(APS)]envsto=

letfunctionfunc=find(env,I)in

letargs=give_argumentsAPSenvstoin

evaluate[OE]envsto=

letunary_operatorunop=find(env,idO)in

letvail=evaluateElenvstoin

unopval

evaluate[ElOE2]envsto=

letbinary_operatorbinp=find(env,idO)in

letvall=evaluateElenystoin

letval2=evaluateE2enystoin

binp(vail,val2)

evaluate[(E)]=

evaluateE

evaluate[letDinE]envsto=

let(env',sto')=elaborateenvstoin

evaluateE(overlay(env',env))sto'

evaluate[ifElthenE2elseE3]envsto=

ifevaluateElenvsto=truthvalue_true

thenevaluateE2envsto

elseevaluateE3envsto

evaluate[{RA}]envsto=

record_vaIue(evaIuate_recordRAenvsto)

evaluate[[AA]]envsto=

array_value(evaluate_arrayAAenvsto)

evaluate_record[I-E]envsto=

letval=evaluateEenvstoin

unit_recordval(1,val)

evaIuate_record[I-E,RA]envsto=

letval=evaluateEenvstoin

letecvaI=evaIuate_recordRAenystoin

joined_record_val(I,val,reeval)

evaluate_array[E]envsto=

letvalevaluateenvstoin

letarrval=evaluate_arrayAAenvstoin

abutted_array_val(val,arrval)

2.2.3名字

V_name::=Identifier

|V_name,Identifier

|V_name[Expression]

指稱語義：

identify:V_name—(EnvironTStore—Value_or_Variable)

//iddenifyVenysto給出在環(huán)境env存儲(chǔ)sto之下由V命名的值或變量

identify[l]envsto=

find(env,D)

identify[V,l]envsto=

letfield(id,value(record_valuerecval)=

value(field-val(id,recval))

field(id,variable(record-variablerecvar))=

variable(field-var(id,recvar))

in

field(I,identifyVenvsto)

identify[V[E]]envsto=

letcomponent(integerint,value(array-valuearrval))=

value(component-val(int,arrval))

commponent(integerint,variable(array-variablearrvar))=

variable(component-var(int,arrvar))

in

component(evaluateEenvsto,identifyVenvsto)

2.2.4聲明

Declaration::=constIdentifier=Expression

|varIdentifier:Type_denoter

|procIdentifier(Formal_Parameter_Sequence)isCommand

|funcIdentifier(Formal_Parameter_Sequence):Type_denoteris

Expression

|typeIdentifierisType_denoter

|Declaration;Declaration

指稱語義：

claborate:Declaration—(Environ—Store--EnvironXStore)

//elaborateDenvsto給出在環(huán)境env存儲(chǔ)sto之下確立聲明D得到的束定和改變

的存儲(chǔ)

elaborate[constI~E]envsto=

letval=evaluateEenvstoin

(bind(I,valucval),sto)

elaborate[varI:T]envsto=

let(sto',var)=allocate-variableTenvstoin

(bind(I,variablevar),sto')

elaborate[procI(FPS)-C]envsto=

letprocargssto=

letenv=overlay(bind(I,procedureproc),env)in

letparenv=bind-parametersFPSargsin

executeC(overlay(parenv,env))sto'

(bind(l,procedureproc),sto)

elaborate[funcI(FPS):T~E]envsto=

letfuncargssto=

letenv=overlay(bind(I,functionfunc),env)in

letparenv=bind-parametersFPSargsin

evalualeE(overlay(parenv,env))sto'

in

(bind(l,functionfunc),sto)

elaborate[typeI-T]envsto=

letallocsto=allocate-variableTenvstoin

(bind(I,allocatoralloc),sto)

elaborate[DI;D2]envsto=

let(env',sto')=elaborateDIenvstoin

let(env",sto")=elaborateD2(overlay(env',env))sto'in

(overlay(env",env'),sto")

2.2.5參數(shù)

Formal_Parameter_Sequence::=

|Formal_Parameter

Formal_Parameter,Formal_Parameter_Sequence

Formal_Parameter::=Identifier:Type_denoter

|varIdentifier:Type_denoter

|procIdentifier(Formal_Parameter_Sequence)

|funcIdentifier(Formal_Parameter_Sequence):Type_denoter

Actual_Parameter_Sequence::=

|Actual_Parameter

|Actual_Parameter,Actual_Parameter_Sequence

Actual_Parameter::=Expression

|varV_name

|procIdentifier

|funcIdentifier

指稱語義：

定義四個(gè)指稱函數(shù)：

?bind_parameters:Formal_Parameter_Sequence一(Argument*一Environ)

?bind_parameter:Formal_Parameter一(Argument—Environ)

?give_arguments:Actual_Parameter_Sequence一(Environ-*Store一

Argument*)

?give_argument:Actual_Parameter—(Environ一Store—Argument)

//hind_parametersFPSargs給出形參序列FPS和變元表args,結(jié)合后的束定

//bind_parameterFParg給出形式參數(shù)FP和變元arg,結(jié)合后的束定

//give_argumentsAPSenvsto給出在環(huán)境env存儲(chǔ)sto之下實(shí)參序列APS產(chǎn)生的

變元表

//give-argumentAPenvsto給出在環(huán)境env存儲(chǔ)sto之下實(shí)參數(shù)AP產(chǎn)生的變元

1.將形參數(shù)列與變元表arg結(jié)合后的束定。

bind_parametersRFP,FPS3(arg?args)=

overlay(bind_parametersFPSargs,bind_parameterFParg)

2.將形參與變元arg結(jié)合后的束定。

bind_parameterKI:T](valueval)=

bind(I,valueval)

bind_parameterRvarI:tj(variablevar)=

bind(I,valueval)

bind_parameterKprocI(FPS)3(procedureproc)=

bind(I,procedureproc)

bind_parameterRfuncI(FPS):T3(functionfunc)=

bind(I,functionfunc)

3.給出在環(huán)境env存儲(chǔ)sto之下實(shí)參序列APS產(chǎn)生的變元表。

give_argumentsRAP,APS3envsto=

(give_argumentAPenvsto)?(give_argumentsAPSenvsto)

4.給出在環(huán)境env存儲(chǔ)sto之下實(shí)參AP產(chǎn)生的變元。

give_argumentKvarV3envsto=

letvariablevar=identifyVenvstoin

variablevar

give_argument[[proc13envsto=

letprocedureproc=find(env,I)in

procedureproc

give_argumentRfunc13envsto=

letfunctionfunc=find(env,I)in

functionfun

2.2.6類型指示符

Type_denoter::=Identifier

|arrayInteger_LiteralofType_denoter

|recordRecord_Type_denoterend

|Char

|Boolean

|Integer

|Real

|*Type_denoter

Record_Type_denoter::=Identifier:Type_denoter

|Identifier:Type_denoter,Record_Type_denoter

指稱語義:

Allocate_variable:Type-denoter-*(Environ-Store—StoreXvariableAllocate

record:Record_Typedenoter—>(Environ->Store->StoreXRecord-Variable)

//allocate_variableTenvsto在環(huán)境env存儲(chǔ)sto之下創(chuàng)建一個(gè)T類型的變量

//allocate_recordRTenvsto在環(huán)境env存儲(chǔ)sto之下，創(chuàng)建一個(gè)具有RT指明的域

的記錄變量，并給出改變了的存儲(chǔ)和此記錄變量

Allocate_variable[I]enysto=

letallocatoralloc=find(env,I)in

allocsto

allocate_variable[arrayILofT]envsto=

let(sta,arrvar)=

allocate_array(sto,integer_valuationIL

allocate_variableTenv)in

(sto,,array-variablearrvar)

allocate_variable[recordRTend]envsto=

let(sto,recvar)=allocate_recordRTenvstoin

allacate_record[I:T]envsto=

let(sto,var)=allocate_variableTenvstoin

(sto,,unit_record_var(I,var))

allocate_record[I:T,RT]envsto=

let(sto,var)=allocate_variableTenvstoin

Iet(sto",recvar)=allocate_recordRTenvsto'in

(sto",joined_record_var(I,var,recvar))

2.2.7程序.

Program::=Command

指稱語義：

run:Program-*(Text—Text)

standard_environ:Environ

chr_function:Function

ord_function:Function

end_of_file_function:Function

end_of_line_function:Function

get_procedure:Procedure

put_procedure:Procedure

get_integer_procedure:Procedure

put_integer_procedure:Procedure

get_end_of_line_procedure:Procedure

put_end_of_line_procedure:Procedure

//runPtxt給出在給定的輸入正文文件時(shí)執(zhí)行程序P得到的輸出正文文件

//standard_environ由所有預(yù)定義實(shí)體的束定組成的標(biāo)準(zhǔn)環(huán)境

〃以下從chr_function至ijput_end_of_line_procedure都是標(biāo)準(zhǔn)的函數(shù)和過程

run[C]input=

letsto=update(emptystore,input_loe,textinput)in

letsto=update(sto,ouput_loc,textempty_text)in

letsto"=executeCstnadard_environstoin

lettextoutput=fetch(sto",output_loc)in

output

standard_environ=

{“Boolean”—allocatorprimitive_allocator,

"false”—truth_valuefalse,

"true"—truthvaluetrue,

id\-*letnotop(truthvaluetr)=truth_value(nottr)in

unary_operatornotop,

id"A"—*binary_operator(logicalboth),

id"\y"-binary_operator(logicaleither),

"Integer"—allocatorprimitive_allocator,

“maxint”—integermaximum-integer,

id"+"-^binary_operator(arithmeticsum),

id-^binary_operator(arithmeticdifference),

id"xn—binaryoperator(arithmeticproduct),

id"/"-?binary_operator(arithmetictruncated-quotient),

id"H"一binary.operator(arithmeticmodulo),

id"<"-*binary_operator(relationalless),

id"<="-^binary_operator(relational(not"greater)),

id">"->binary_operator(relationalgreater),

id">="—binary_operator(relationalnot"less)),

"char"-?allocatorprimitive_allocator,

"chr"-?functionchr_function,"ord"一functionord_function

"eof"-^functionend_of_file_function,

"eol"—functionend_of_line_function,

"get"-procedureget_procedure,

"put"—procedureput_procedure,

“getint"一proceduregetinteger_procedure,

“putint"一procedureput_integer_procedure,

"geteol"-procedureget_end_of_line_procedure,

“puteol"-procedureputend_of_line_procedure,

id"="一binary_operator(=),

id"\="—binary_operator(H),

)

chr_function=

letfunc(value(integerint)-nil)sto=

character(decode(int))

in

func

ordfunction=

letfunc(value(characterchar)-nil)sto=

integer(code(char))

in

func

end_of_file_funetion=

letfuncnilsto=

lettexttxt=fetch(sto.input_loc)in

truth-value(end_of_file(txt))

in

func

end_of_line_function=

letfuncnilsto=

lettexttxt=fetch(sto,input-loc)in

truth_value(end_of_line(txt))

in

func

end_ofline_function=

letfuncnilsto=

lettexttxt=fetch(sto,input-loc)in

truth_value(end_of_line(txt))

in

func

get_procedure=

letproc(variablevar-nil)sto=

lettexttxt=fetch(sto,input_loc)in

let(char,txt')=gettxtin

letstor=update_variable(sto,var,characterchar)in

update(sto,input_loc,texttxt)

in

proc

put_procedure=

letproc(value(characterchar)-nil)sto=

lettexttxt=fetch(sto,output-loc)in

lettxr=append(txt,char)in

update(sto,output_loc,texttxt)

in

proc

get_integer_procedure=

letproc(variablevar-nil)sto=

lettexttxt=fetch(sto,input-loc)in

lettxr=skip_blankstxtinlet(int,txt")=get=signed_integertxt'in

letsto=update_variable(sto,var,integerint)in

update(sto,input_loc,texttxt")

in

proc

put-ineger_procedure=

letproc(value(integerint)-nil)sto=

lettexttxt=fetch(sto,output_loc)in

lettxt=append_signed_integer(txt,int)in

update(sto,output_loc,texttxt)

in

proc

get_end_of_line_procedure=

letprocnilsto=lettexttxt=fetch(sto,input_loc)in

lettxt=skip_linetxtin

update(sto,inputloc,texttxr)

in

proc

put_end_of_line_procedure=

letprocnilsto=

lettexttxt=fetch(sto,output_loc)in

lettxt=append(txt,end_of_line_character)in

update(sto,output_loc,texttxt')

proc

2.3語言的代碼范例

let

typeLineisrecord

lengthinteger,

content:array80ofChar

end;

procgetline(varl:Line)is

begin

l.length:=0;

while!eol()do

begin

get(varLcontent[l.length]);

l.length:=l.length+1;

end;

geteol();

end;

procputreversedline(kLine)is

letvari:Integer

in

begin

i:=I.length;

whilei>0do

begin

i:=i-1;

put(Lcontent[i])

end;

puteol()

end;

varcurrentlineline

while!eof()do

begin

getline(varcurrentline);

putreversedline(currentline)

3.語法分析器的實(shí)現(xiàn)

我們使用LRQ)文法構(gòu)造了語言的語法分析器，可以語言源代碼進(jìn)行詞法和語法分析并

輸出語法分析樹和符號(hào)表。

運(yùn)行python3main.pymake-parse-table程序會(huì)讀取parser/bnf.txt中定義的語

言范式構(gòu)建LR⑴分析表;運(yùn)行：python3main.pysrc_path語法分析器會(huì)對

src_path指定的源代碼文件進(jìn)行語法分析。

下面為語法分析器對以下源程序進(jìn)行語法分析的結(jié)果：

let

constten=10;

funcpower(a:Integer,n:Integer):Integeris

ifn==0

then1

elsea*power(a,n-1)

in

power(ten)

程序語法樹構(gòu)造結(jié)果：

語法分析程序還能檢測源文件中的詞法、語法錯(cuò)誤，并給出人性化的提示:

源文件存在詞法錯(cuò)誤時(shí)的輸出：

wangweimin&Mangweimins-iMac:~/repos/apps/simple_compiler$python3main.pydemo_src/textl.txt

ScanError

Traceback:File"demo.src/textl.txt",line2

1let

->constten=*10;

3funcpower(a:Integer,n:Integer):Integeris

4ifn=0

ScanError:字符串沒有閉合

源文件存在語法錯(cuò)誤時(shí)的輸出：

wan^eimin^an^eimins-iMac:*/repos/apps/simple_compiler$python3main.pydemo_src/textl.txt

ParseError

Traceback:Filendemo-src/textl.txtM,line8

6elsea?powerfa

7

->in

9power(ten)

ParseError:Except'const*,*type*,,var,,'func',*proc'

Got*in*

3.1詞法分析的實(shí)現(xiàn)

詞法分析器對語言源代碼進(jìn)行詞法分析，詞法分析的結(jié)果為Token序列、符號(hào)表和字

符串表

詞法分析器使用了狀態(tài)機(jī)進(jìn)行實(shí)現(xiàn)，狀態(tài)轉(zhuǎn)移如下：

詞法分析狀態(tài)機(jī)

對應(yīng)代碼為：

tokens=[]#(type,attr)

symbols=[]4芍號(hào)表

const_string=[]-手二生7

q=deque(char_seq_gen(src_path))#翻8源文件路徑構(gòu)造出字符隊(duì)列

whileq：

c=q.popleft()

ifc.isspaceO：

continue

q.insert(0,c)#更新保存讀出的字符

res=check_and_ignore_comment(q)

ifres：|

continue

ifc.isalphaO:

token_type,value=read_alpha(q)

elifc.isdigit():

token_type,value=read_digit(q)

elifc=*'*'：

token__type,value=read_string(q)

elifc=

token_type,value=read_char(q)

else：

token_typervalue=read_separator(q)

iftoken_type=IDENTIFIER:#當(dāng)前蜘際oken為,哪聞一聘入

ifvalueinsymbols：

tokens.append((token_type,symbols.index(value)))

else:

symbols.append(value)

tokens.append((token_type,ten(symbols)-1))

eliftoken_type=STRING:#當(dāng)前,!l的token為字符串常量,要把的結(jié)果寫如字符串表

ifvalueinconst_string：

tokens.append((token_type,const_string.index(value)))

else:

const_string.append(value)

tokens.append((token_type,len(const_string)-1))

else：

tokens.append((token_type,value))

returntokens,symbols,const_string

首先程序根據(jù)用戶傳入的源文件路徑構(gòu)造出一個(gè)字符隊(duì)列，然后程序進(jìn)入循環(huán)迭代，

每循環(huán)一次，就從字符隊(duì)列中讀出一個(gè)Token。下面來詳細(xì)分析循環(huán)中的邏輯：每

次循環(huán)開始后，從字符序列中讀取一個(gè)字符，由于上文所述，可知該字符肯定為空格

或者下一個(gè)Token的開始字符。如果為空格則直接忽略，接下來則根據(jù)該字符的值縮

小Token類型的范圍，就比如若讀到的字符是字母，則接下來的Token肯定為標(biāo)識(shí)

符、關(guān)鍵字、布爾常數(shù)之一。然后調(diào)用相關(guān)函數(shù)讀取接下來的Token,簡單地說，程

序把Token根據(jù)首字母進(jìn)行分類識(shí)別，在循環(huán)中根據(jù)讀到的Token首字符調(diào)用相關(guān)

的識(shí)別函數(shù),同時(shí)存儲(chǔ)識(shí)別到的Token。

下面是各類標(biāo)識(shí)符的讀取過程狀態(tài)機(jī)：

標(biāo)識(shí)符、關(guān)鍵字、布爾常數(shù)識(shí)別狀態(tài)機(jī)：

標(biāo)識(shí)符、關(guān)鍵字、布爾常數(shù)狀態(tài)機(jī)

整形和實(shí)數(shù)識(shí)別狀態(tài)機(jī)：

整形和實(shí)數(shù)狀態(tài)機(jī)

字符常數(shù)識(shí)別狀態(tài)機(jī)：

字符常數(shù)狀態(tài)機(jī)

3.2語法分析的實(shí)現(xiàn)

語法分析部分利用語言的文法推導(dǎo)式構(gòu)造LR(1)分析表，并使用LRQ)分析表對語言源

代碼的Token序列進(jìn)行語法分析。

語法分析表的構(gòu)造

模塊路徑：parser/tools.py,本模塊可以根據(jù)輸入的文法推導(dǎo)式列表計(jì)算其語法非

終結(jié)符的FIRST集、NULLABLE集。可根據(jù)輸入項(xiàng)集計(jì)算項(xiàng)集的閉包、計(jì)算GOTO

轉(zhuǎn)移狀態(tài)，求取語法分析表。

模塊中項(xiàng)的由類Item表示，其成員函數(shù)有piddotahead,pid為該項(xiàng)使用的推導(dǎo)

式的編號(hào)，dot為項(xiàng)中點(diǎn)的位置，ahead為項(xiàng)的前看符號(hào)集合，這里項(xiàng)的表示和課

上的表示略有區(qū)別，這里ahead變成了集合，這樣，多個(gè)相同推導(dǎo)式并且點(diǎn)的位置相

同的項(xiàng)可以合并。

以下選取計(jì)算項(xiàng)集的閉包和求取語法分析表兩個(gè)函數(shù)進(jìn)行分析：

defclosure(items,productions,FIRST,TERMINAL,Nullable):

iitiH

計(jì)算項(xiàng)集的閉包，并檢驗(yàn)閉包是否有移進(jìn)-規(guī)約沖突和規(guī)約-規(guī)約沖突

IIttII

left_lookup=defaultdict(list)#每個(gè)非終結(jié)符的流號(hào)列表

forid,(left,*right)inenumerate(preductions):

left_lookup[left].append(id)

res=set(items)

changing=True

whilechanging:

changing=False

forsinres.copyO:

left,*right=productions[s.pid]

#對于每一個(gè)形如A->a*8b,c的項(xiàng)

iften(right)>s.dotandrightfs.dot]notinTERMINAL:#項(xiàng)可展開

fs=First_S(right[s.dot+1:]rFIRST,TERMINAL,Nullable)

ifNullable_S(right[s.dot+1:],Nullable):#Be可為空

fs=fs.union(s.ahead)

forpidinleft_lookup[right[s.dot]]:

t=Item(pid,0,tuple(fs))

iftnotinres：

res.add(t)

changing=True

函數(shù)先是計(jì)算出每個(gè)非終結(jié)符的推導(dǎo)式編號(hào)列表，用于在后面對待歸約項(xiàng)目(形如A->

aBp)進(jìn)行展開時(shí)求取新項(xiàng)的推導(dǎo)式標(biāo)號(hào)。然后遍歷項(xiàng)集中每一項(xiàng)，如果項(xiàng)可展開(右

部長度大于點(diǎn)的位置)且點(diǎn)后面為非終結(jié)符，這里以A->a-Bp,(a,b,c?.)為例，則開始

求取展開項(xiàng)的前看符號(hào)的集合，即FIRST(0a)+FIRST(Bb)+FIRST(|k)+…，然后對于

待規(guī)約符號(hào)B的每個(gè)推導(dǎo)式B->a,B->B,生成相應(yīng)的項(xiàng)B->.a,ahead,B-

>Sahead加入項(xiàng)集中。

由于循環(huán)終止的條件是項(xiàng)集不發(fā)生改變，對此的實(shí)現(xiàn)為：設(shè)置一個(gè)標(biāo)志變量

changing表示本次迭代有沒有對項(xiàng)集進(jìn)行改變,在迭代中，對項(xiàng)集進(jìn)行了實(shí)際的修

改后，就將此變量置為真。

開始校驗(yàn)閉包是否存在沖突

規(guī)約-規(guī)約沖突：規(guī)約項(xiàng)前看符號(hào)有交集

移進(jìn)-規(guī)約沖突：規(guī)約項(xiàng)前看符號(hào)與移進(jìn)項(xiàng)移入符號(hào)有交集

“，，“

reduct__ahead=set()#規(guī)約項(xiàng)前看符號(hào)

shift_syntol=set()#移進(jìn)項(xiàng)移入符號(hào)

foriteminres：

left,?right=productions[item.pid]

iflen(right)=item.dot:#規(guī)約項(xiàng)

ifset(item.ahead)&reduct_ahead：

raiseValueError。計(jì)算項(xiàng)集閉包時(shí)發(fā)現(xiàn)規(guī)約-規(guī)約沖突，沖突閉包：宅s'%res,res)

else：

reduct_ahead=reduct_ahead.union(item.ahead)

elifright[item.dot]inTS^MINAL：#移進(jìn)項(xiàng)

shift_symbol.add(right[item.dot])

ifshift_symbol&reduct_ahead：

raiseValueError「計(jì)良項(xiàng)集閉包時(shí)發(fā)現(xiàn)移進(jìn)-規(guī)約沖突，沖突閉包：％s'%res,res)

計(jì)算完項(xiàng)集閉包后還要對計(jì)算出的閉包進(jìn)行沖突檢查，判斷是否存在規(guī)約-規(guī)約沖突和

移入-規(guī)約沖突。

構(gòu)造語法分析表的過程如下:

trans_tab為狀移表

{state=>{symbol=>action),}

action：(type,attribute),

type：0for移進(jìn)，1for規(guī)約,2for接受，3forgoto

nitn

trans_tab=defaultdict(dict)

c=closure({Item(0,0,('$,,))},productions,FIRST,THMENAL,Nullable)

states=(c]#closure

unresolve=[0]#closureidthatneedresolve

whileunresolve：

cid=unresolve.pop()

foriteminstates[cid]:

left,*right=productions[item.pid]

iflen(right)=item.dot:#規(guī)約項(xiàng)

foraheadinitem.ahead:

trans_tab[cid][ahead]=(1,item.pid)#設(shè)自action為"規(guī)紂'

ifitem.pid=0:

trans_tab[cid][ahead]=(2,item.pid)#設(shè)建action為"接受"

elifright[item,dot]notintrans_tab[cid]:#矢處理的移迸項(xiàng)目和待歸為項(xiàng)目

c=goto(states[cid],right[item.dot],

productions,FIRST,TERMINAL,Nullable)

try:

index=states.index(c)

exceptValueError:

states.append(c)

index=Ien(states)-1

unresolve.append(index)

ifright[item.dot]inTERMINAL:

trans_tab[cid][right[item.dot]]=(

0,index)#設(shè)置action為'移進(jìn)

else:

trans__tab[cid][right[item.dot]]=(

3,index)#設(shè)第ction為'GOTO"

returnproductions,trans_tab

語法分析表既包含Action表又包含GOTO表，采用的數(shù)據(jù)結(jié)構(gòu)為雙層嵌套字典，外

層字典的鍵為閉包編號(hào)（狀態(tài)編號(hào)）,內(nèi)層字典的鍵為終結(jié)符和非終結(jié)符，終結(jié)符鍵對

應(yīng)的值為原Action表中的前看符號(hào)為終結(jié)符時(shí)進(jìn)行的操作（移入并轉(zhuǎn)移狀態(tài)/使用推導(dǎo)

式進(jìn)行規(guī)約），非終結(jié)符對應(yīng)的值為GOTO表中當(dāng)前狀態(tài)輸入非終結(jié)符后轉(zhuǎn)移的狀態(tài)。

函數(shù)維護(hù)了一個(gè)待處理閉包的棧，首先程序計(jì)算增廣文法第一個(gè)項(xiàng)的閉包，將其加入

待處理閉包棧，然后開始while循環(huán)，直到待處理閉包棧為空。在每次循環(huán)體中，先

取出棧頂未處理的閉包，遍歷閉包的每一項(xiàng)：對于規(guī)約項(xiàng)，向語法分析表的相應(yīng)位置

填入規(guī)約動(dòng)作和規(guī)約使用的推導(dǎo)表達(dá)式編號(hào)；對于移進(jìn)項(xiàng)和待規(guī)約項(xiàng)，調(diào)用GOTO

函數(shù)計(jì)算移進(jìn)和規(guī)約之后項(xiàng)的閉包，判