LL(1)文法分析程序?qū)嶒?yàn)報(bào)告

LL（1）文法分析程序?qū)嶒?yàn)報(bào)告學(xué)院：計(jì)算機(jī)科學(xué)與信息學(xué)院班級(jí)：××××學(xué)號(hào)：1109×××××姓名：×××指導(dǎo)老師：孫老師專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)計(jì)算機(jī)科學(xué)與技術(shù)系1、概述當(dāng)我們需選用自頂向下分析技術(shù)來(lái)分析文法時(shí)，首先必須判別所給文法是否是LL(1)文法。因而我們對(duì)任給文法需計(jì)算FIRST、FOLLOW、SELECT集合，進(jìn)而判別文法是否為L(zhǎng)L(1)文法。2、LL(1)的判定步驟2.1、求出能推出ε的非終結(jié)符

首先建立一個(gè)以文法的非終結(jié)符個(gè)數(shù)為上界的一維數(shù)組，其數(shù)組元素為非終結(jié)符，對(duì)應(yīng)每一非終結(jié)符有一標(biāo)志位，用以記錄能否推出ε。其值有三種情況："未定"、"是"、"否"。①將數(shù)組X[]中對(duì)應(yīng)每一非終結(jié)符的標(biāo)記置初值為"未定"。②掃描文法中的產(chǎn)生式。

(a)刪除所有右部含有終結(jié)符的產(chǎn)生式，若這使得以某一非終結(jié)符為左部的所有產(chǎn)生式都被刪除，則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)記值改為"否"，說(shuō)明該非終結(jié)符不能推出ε。

(b)若某一非終結(jié)符的某一產(chǎn)生式右部為ε，則將數(shù)組中對(duì)應(yīng)該非終結(jié)符的標(biāo)志置為"是"，并從文法中刪除該非終結(jié)符的所有產(chǎn)生式。例中對(duì)應(yīng)非終結(jié)符A、B的標(biāo)志改為"是"。③掃描產(chǎn)生式右部的每一符號(hào)。

(a)若所掃描到的非終結(jié)符號(hào)在數(shù)組中對(duì)應(yīng)的標(biāo)志是"是"，則刪去該非終結(jié)符，若這使產(chǎn)生式右部為空，則對(duì)產(chǎn)生式左部的非終結(jié)符在數(shù)組中對(duì)應(yīng)的標(biāo)志改"是"，并刪除該非終結(jié)符為左部的所有產(chǎn)生式。

(b)若所掃描到的非終結(jié)符號(hào)在數(shù)組中對(duì)應(yīng)的標(biāo)志是"否"，則刪去該產(chǎn)生式，若這使產(chǎn)生式左部非終結(jié)符的有關(guān)產(chǎn)生式都被刪去，則把在數(shù)組中該非終結(jié)符對(duì)應(yīng)的標(biāo)志改成"否"

④重復(fù)③，直到掃描完一遍文法的產(chǎn)生式，數(shù)組中非終結(jié)符對(duì)應(yīng)的特征再?zèng)]有改變?yōu)橹埂?.2、計(jì)算FIRST集

(a)若X∈VN，且有產(chǎn)生式X→a…，a∈VT，則a∈FIRST(X)。

(b)若X∈VN，X→ε,則ε∈FIRST(X)。

(c)若X∈VN；Y1，Y2，…，Yi∈VN，且有產(chǎn)生式X→Y1Y2…Yn；當(dāng)Y1Y2…Yi-1都ε時(shí)，(其中1≤i≤n)，則FIRST(Y1)、FIRST(Y2)、…、FIRST(Yi-1)的所有非{ε}元素和FIRST(Yi)都包含在FIRST(X)中。(d)當(dāng)(d)中所有Yiε,(i=1,2,…n)，則

FIRST(X)=FIRST(Y1)∪FIRST(Y2)∪…∪FIRST(Yn)∪{ε}，反復(fù)使用上述(a)～(d)步直到每個(gè)符號(hào)的FIRST集合不再增大為止。2.3、計(jì)算FOLLOW集

對(duì)文法中每一A∈VN計(jì)算FOLLOW(A)

(a)設(shè)S為文法中開(kāi)始符號(hào)，把{#}加入FOLLOW(S)中(這里"#"為句子括號(hào))。

(b)若A→αBβ是一個(gè)產(chǎn)生式，則把FIRST(β)的非空元素加入FOLLOW(B)中。

如果βε則把FOLLOW(A)也加入FOLLOW(B)中。

(c)反復(fù)使用(b)直到每個(gè)非終結(jié)符的FOLLOW集不再增大為止。2.4、計(jì)算SELECT集對(duì)文法中每一A->a,A∈VN,a屬于V*,若a不能推出空，則SELECT(A->a)=FIRST(a)。否則SELECT(A->a)={FIRST(a)-{ε}UFOLLOW(A)。2.5、判定對(duì)于每個(gè)非終結(jié)符的兩個(gè)不同產(chǎn)生式，A->a,A->b,滿足SELECT(A->a)ΠSELECT(A->b)=ф。其中a,b不能同時(shí)推出ε。3、預(yù)測(cè)分析3.1、構(gòu)建文法的預(yù)測(cè)分析表分析表又可用一個(gè)矩陣M(或稱二維數(shù)組)表示。矩陣的元素M[A，a]中的下標(biāo)A表示非終結(jié)符，a為終結(jié)符或句子括號(hào)"#"，矩陣元素M[A,a]中的內(nèi)容為存放著一條關(guān)于A的產(chǎn)生式，表明當(dāng)用非終結(jié)符A向下推導(dǎo)時(shí)，面臨輸入符a時(shí)，所應(yīng)采取的候選產(chǎn)生式，當(dāng)元素內(nèi)容無(wú)產(chǎn)生式時(shí)，則表明用A為左部向下推導(dǎo)時(shí)遇到了不該出現(xiàn)的符號(hào)，因此元素內(nèi)容為轉(zhuǎn)向出錯(cuò)處理的信息。3.2、預(yù)測(cè)分析程序框圖4、文法分析實(shí)現(xiàn)5、實(shí)驗(yàn)心得本次實(shí)驗(yàn)利用自上而下的分析方法對(duì)任給的文法進(jìn)行判斷，基本完成了實(shí)驗(yàn)要求，但僅僅局限于LL（1）文法才能用，具有一