句子分析演算法

⑴ 循環語句的語法分析及語義分析程序設計

目 錄
1 課程任務書····································（2）
1問題描述·······································（3）
2文法及屬性文法的描述···························（3）
2.1 while-do循環語句的文法·····················（3）
2.2while-do循環語句的結構翻譯·················（3）
3語法分析及中間代碼形式的描述···················（4）
3.1 語法分析方法·······························（4）
3.2 中間代碼形式描述···························（4）
4簡要的分析與概要設計···························（5）
4.1詞法分析··································（5）
4.2遞歸下降翻譯器的設計·······················（5）
4.3語法制導翻譯·······························（5）
5 詳細的演算法描述································（6）
5.1 文法·······································（6）
5.2 查錯·······································（6）
6 測試方法和測試結果···························（9）
6.1測試方法··································（9）
6.2測試結果··································（10）
7 設計的特點、不足、收獲與體會·················（10）
7.1 設計的特點································（10）
7.2 不足、收獲與體會··························（11）
8 參考文獻·····································（11）

課程設計任務書
題 目: 循環語句的語法分析及語義分析程序設計（遞歸下降法）
1．目的
通過設計、編制、調試一個語法及語義分析程序，加深對語法及語義分析原理的理解。

2.設計內容及要求
WHILE〈布爾表達式〉DO〈賦值語句〉
其中
（1）學號29至32的同學按順序分別選擇遞歸下降法、LL（1）、算符優先分析法（或簡單優先法）、LR法完成以上任務，中間代碼選用四元式。
（2）如1題寫出符合分析方法要求的文法，給出分析方法的思想，完成分析程序設計。
（3）編制好分析程序後，設計若干用例，上機測試並通過所設計的分析程序。

3.課程設計報告書的內容應包括：
1.設計題目、班級、學號、姓名、完成日期；
2.給出語法分析方法及中間代碼形式的描述、文法和屬性文法的設計；或者詞法分析方法
3.及符號表和TOKEN代碼的設計。
4.簡要的分析與概要設計；
5.詳細的演算法描述；
6.源程序清單；
7.給出軟體的測試方法和測試結果；
8.設計的評價、收獲與體會。

4.時間安排：
第17周，周1-周4上午，周五全天

指導教師簽名： 年 月 日
系主任（或責任教師）簽名： 年 月 日

1問題描述
設計一個WHILE〈布爾表達式〉DO〈賦值語句〉循環語句的詞法﹑語法及語義分析程序，語法分析選擇遞歸下降法，採用用語法制導翻譯輸出中間代碼四元式。
2文法及屬性文法的描述。
2.1 while-do循環語句的文法
產生式為S-> while E do A，為便於語法制導翻譯將其改寫如下：
文法G(s)如下：
S-->WEDG （意思是while E do G）
G-->c=R
R-->dTe|d
T-->+|-|*|/
E-->aFb
F--> >|==|<

2.2 whlie-do循環語句的結構翻譯：

3.語法分析方法及中間代碼形式的描述
3.1語法分析方法
遞歸下降法的實現思想是為文法的每個非終結符號設計一個相對應的遞歸子程序，識別程序由一組這樣的子程序組成。
它的優點是簡單直觀，易於構造，很多編譯系統所實現
缺點是對文法要求很高，由於遞歸調用多，影響分析器的效率
其文法可以表示為：
E→T│E+T
T→F│T*F
F→i│（E）
可以用語法圖來表示語言的文法，如圖：

E

T

F

3.2中間代碼形式描述
中間代碼採用四元式輸出，一個四元式是一個帶有四個域的記錄結構，這四個域分別稱為op﹑arg1﹑arg2及result。域op包含一個代表運算符的內部碼。語句while a<b do a=a+b的四元式輸出形式如下：
100 ( <, a , b , 102 )
101 ( j , _ , _ , 105 )
102 ( + , a , b , n )
103 ( = , n , _ , a )
104 ( j , _ , _ , 100)
105
4．簡要的分析與概要設計
4.1詞法分析
詞法分析程序的任務是：從左至右逐個字元地對源程序進行掃描，產生一個個的單詞符號，把作為字元串的源程序改造成為單詞符號的中間程序。詞法分析檢查的錯誤主要是挑出源程序中出現的非法符號。所謂非法符號是指不是程序設計語言中允許出現的符號，就像自然語句中的錯字。
4.2遞歸下降翻譯器的設計
1.：對每個非終結符A構造一個函數過程，對A的每個繼承屬性設置一個形式參數，函數的返回值為A的綜合屬性，A對應的函數過程中，為出現在A的產生式中的每一個文法符號的每一個屬性都設置一個局部變數。非終結符A對應的函數過程中，根據當前的輸入符號決定使用哪個產生式候選。
2：每個產生式對應的程序代碼中，按照從左到右的次序，對於單詞符號，非3：終結符和語義動作分別做以下工作。
（1）對於帶有綜合屬性x的終結符X，把x的值存入為X，x設置的變數中。然後產生一個匹配X的調用，並繼續讀入一個輸入符號。
（2）對於每個非終結符號B，產生一個右邊帶有函數調用的賦值語句c=B(b1,b2,…，bk)
（3）對於語義動作，把動作的代碼抄進分析器中，用代表屬性的變數來代替對應屬性的每一次引用。
4.3語法制導翻譯
在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯。屬性文法的每個符號有屬性，所以每個符號入棧時，必須連屬性一起入棧，這樣，棧符號就由文法符號及存放該符號屬性的域所組成。由於屬性類型不同，屬性域存放的內容就要根據屬性的類型來定。有的可能直接存放屬性值，也有的存放的是指向屬性值的指針。對於綜合屬性，其屬性域不存放其屬性值，而是存放一個指針，指向存貯該屬性值的單元。對於繼承屬性，其屬性域直接保存其屬性值。繼承屬性的屬性域剛入棧時為空，但是在該棧符號變成棧頂符號之前的某一時刻，它們必須接受相應的屬性值，即在成為棧頂時，繼承屬性的屬性域必須有值。
5詳細的演算法描述
5.1 文法
/*
文法G(s)
s-->WEDG
G-->c=R
R-->dTe|d
T -> +|-|*|/|%E-->aFb
F--> >|==|<
*/
5.2 查錯
按照遞歸下降法求Wa<bDa=a+b，程序的執行順序應該是S()W()EF()D()G()R()T()
S()
void S()
{
printf("%d\tS-->WEDG\n",total);total++;
W();
E();
}

W()
void W()
{
if(ch!='W')
{
printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
}

E()
void E()
{
ch=a[++i1];
if(ch!='a')
{
printf("有非法字元%c %c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
printf("%d\tE-->aFb\n",total);total++;
F();
}

F()
void F()
{
int i;
ch=a[++i1];
i=i1+1;
if(a[i]!='b')
{
printf("有非法字元%c請按回車返回!!",a[i]);
getchar();
getchar();
exit(1);
}
switch(ch)
{
case '>':
printf("%d\tF-->>\n",total);total++;
break;
case '==':
printf("%d\tF-->==\n",total);total++;
break;
default:
printf("%d\tF--><\n",total);total++;
break;
}
D();
G();
}

D()
void D()
{
++i1;
ch=a[++i1];
if(ch!='D')
{
printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);}
ch=a[++i1];
}

G()
void G()
{
int i=i1+1;
if(ch!='c'&&a[i]!='=')
{
printf("有非法字元%c %c請按回車返回!!",ch,a[i]);
getchar();
getchar();
exit(1);
}
printf("%d\tG-->c=R\n",total);total++;
R();
}

R()
void R()
{
int i;
i=i1+1;
i1=i1+2;
ch=a[i1];
if(a[i]!='='&&ch!='d')
{
printf("有非法字元%c %c請按回車返回!!",a[i],ch);
getchar();
getchar();
exit(1);
}
else
{
if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))
{
printf("%d\tR-->dTe\n",total);total++;
T();
}
else
{
printf("%d\tR-->d\n",total);total++;
W();
E();
}
}
}

T()
void T()
{
ch=a[++i1];
switch(ch)
{
case '+':
printf("%d\tT-->+\n",total);total++;
break;
case '-':
printf("%d\tT-->-\n",total);total++;
break;
case '*':
printf("%d\tT-->*\n",total);total++;
break;
default:
printf("%d\tT-->/\n",total);total++;
break;
}
ch='#';
}

6測試方法和測試結果
6.1測試方法
在C++環境下，設計幾個有代表的用例，進行測試，例如：輸入語句Wa<bDa=a+b#(其中d表示do ,w表示while)。若得出的不是預期的結果，那麼程序就出現問題。如果有問題的話就進行單步調試找到程序中出現的邏輯問題。

6.2測試結果
測試結果如下：

7設計的特點、不足、收獲與體會
7.1設計的特點
本次設計是採用遞歸下降的方法對輸入的while--do 循環語句進行語法，語義分析，並輸出四元式。因此程序中充分體現了遞歸下降的思想。

7.2設計的不足，收獲與體會
本次的設計的不足主要是我沒將程序一般化，實現不了用戶自動輸入代碼進行詞法分析的四元式輸出，此程序只能實現對Wa<bDa=a+b#的分析與四元式輸出，由於我所設計的棧中只能一個字元一個字元的存放，因此只能用D W分別表示do while；而且我對語法制導翻譯這一塊很不熟悉，因此我始終不能用程序實現語法制導翻譯輸出四元式，於是根據自己的理解，直接把四元式寫了出來。
本次課程設計鞏固了我所學習的關於遞歸下降法這一方面的知識，並且使我對WHILE—DO循環語句也有了更深刻的理解,提高了我的動手能力。

8 課程設計參考資料
1張幸兒 《編譯原理》（第二版）清華大學出版社
2何炎祥 《編譯原理》華中理工大學出版社
3陳火旺 《程序設計語言編譯原理》（第3版）國防工業出版社

本科生課程設計成績評定表
班級：軟體0701姓名：周璐萍學號：0120710680129
序號 評分項目 滿分 實得分
1 學習態度認真、遵守紀律 10
2 設計分析合理性 10
3 設計方案正確性、可行性、創造性 20
4 設計結果正確性 40
5 設計報告的規范性 10
6 設計驗收 10
總得分/等級
評語：

註：最終成績以五級分制記。優（90-100分）、良（80-89分）、中（70-79分）、
及格（60-69分）、60分以下為不及格
源程序
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>

char a[50],g[50][50];
char ch;
int n1,i1=0,i2=0;
int total=0;

void S();
void D();
void G();
void W();
void E();
void R();
void T();
void F();

void main()
{
int j=0;

printf("文法G(s)為:\n");
printf("s-->DGWE\n");
printf("G-->c=R\n");
printf("R-->dTe|d\n");
printf("T-->+|-|*|/\n");
printf("E-->aFb\n");
printf("F--> >|==|<\n");

printf("請輸入while-do語句(D代表do,W代表while),並以#結束:\n");
do{
scanf("%c",&ch);
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=a[0];

S();
printf("\n");

if (ch=='#')
{ printf("輸出四元式為：\n");
printf("100 (<,a,b,102)\n");
printf("101 (j,_,_,105)\n");
printf("102 (+,a,b,n)\n");
printf("103 (=,n,_,a)\n");
printf("104 (j,_,_,100)\n");
printf("105 \n");

}

else {

printf("error\n");

printf("press any key to continue..\n");

getchar();getchar();

return;

}

printf("\n");

printf("press any key to continue..\n");

getchar();
getchar();
}

/*出錯情況分析*/

void S()
{
printf("%d\tS-->WEDG\n",total);total++;
W();
E();
}

void W()
{

if(ch!='W')
{
printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
}

void E()
{
ch=a[++i1];
if(ch!='a')
{
printf("有非法字元%c %c請按回車返回!!",ch);
getchar();
getchar();
exit(1);
}
printf("%d\tE-->aFb\n",total);total++;
F();
}

void F()
{
int i;
ch=a[++i1];
i=i1+1;
if(a[i]!='b')
{
printf("有非法字元%c請按回車返回!!",a[i]);
getchar();
getchar();
exit(1);
}
switch(ch)
{
case '>':
printf("%d\tF-->>\n",total);total++;

break;
case '==':
printf("%d\tF-->==\n",total);total++;

break;
default:
printf("%d\tF--><\n",total);total++;

break;

}
D();
G();
}

void D()
{ ++i1;
ch=a[++i1];
if(ch!='D')
{ printf("有非法字元%c請按回車返回!!",ch);
getchar();
getchar();
exit(1);}
ch=a[++i1];

}

void G()
{ int i=i1+1;

if(ch!='c'&&a[i]!='=')
{ printf("有非法字元%c %c請按回車返回!!",ch,a[i]);
getchar();
getchar();
exit(1);}
printf("%d\tG-->c=R\n",total);total++;
R();
}

void R()
{
int i;
i=i1+1;
i1=i1+2;
ch=a[i1];
if(a[i]!='='&&ch!='d')
{
printf("有非法字元%c %c請按回車返回!!",a[i],ch);
getchar();
getchar();
exit(1);
}
else
{
if((a[i1+1]=='+')||(a[i1+1]=='-')||(a[i1+1]=='*')||(a[i1+1]=='/'))
{
printf("%d\tR-->dTe\n",total);total++;

T();

}
else
{
printf("%d\tR-->d\n",total);total++;

W();
E();
}
}

}

void T()
{
ch=a[++i1];
switch(ch)
{
case '+':
printf("%d\tT-->+\n",total);total++;

break;
case '-':
printf("%d\tT-->-\n",total);total++;

break;
case '*':
printf("%d\tT-->*\n",total);total++;

break;

default:
printf("%d\tT-->/\n",total);total++;

break;
}
ch='#';

}

指導教師簽名：
2010 年月日

⑵ TextCNN演算法分析

TextCNN

什麼是卷積

如上圖所示，這其實是一個動圖，黃色的 3*3 的方格在 不斷滑動 ，其就是一個圖像 過濾器 的圖示，但是這個是針對於圖像的。如果說對文本進行過濾器處理的話，過濾器是不能橫向滑動的，因為你不能把一個字或者說一個單詞從中間分開來進行訓練。圖像可以一個圖像經過處理之後你應該還會認識這個圖片，但是當文字從中間分開之後，相當於單詞的一半或者說是一個偏旁，這個時候你有可能就不會理解這個文字想要表達什麼意思了。

以下是博客作業給出的一個圖像濾波器處理的一個例子。是使用其相鄰值對每個像素求平均值，這樣會得到一個模糊的圖像。方格中 為1的就乘以1，為0的就乘以0 ，這樣可以將 5*5的像素 合並為一個像素值，得出一個較為模糊的圖像。

經過濾波器處理之後你是完全可以知道這個圖片代表什麼的，不同的一點就是模糊了一點而已。

下面介紹一個利用卷積 檢測邊緣 的例子，圖示如下所示，其計算和上面那個計算方法是一樣的，其思想是取像素及其鄰居之間的差異來檢測邊緣。

什麼是卷積神經網路(CNN)

CNN基本上只是幾層卷積，其中 非線性激活函數   如ReLU或tanh應用於結果。在傳統的 前饋神經網路 中，我們將每個輸入神經元連接到下一層中的每個輸出神經元。這也稱為 完全連接層 或 仿射層 。在CNN中我們不這樣做。相反，我們在輸入層上使用 卷積 (這個在上面講到過)來計算輸出。這導致局部連接，其中輸入的每個區域連接到輸出中的神經元。 每一層都應用 不同 的過濾器，通常是數百或數千，如上所示，並結合其結果。還有一些叫做池（子采樣）層的東西。在訓練階段， CNN 會根據您要執行的任務 自動學習其過濾器的值 。例如，在圖像分類中，CNN可以學習從第一層中的原始像素檢測邊緣，然後使用邊緣檢測第二層中的簡單形狀，然後使用這些形狀來阻止更高級別的特徵，例如面部形狀在較高層。最後一層是使用這些高級功能的分類器。

這個計算有兩個方面值得關註： 位置不變性 和 組合性 。假設您想要對圖像中是否有大象進行分類。因為你在整個圖像上滑動你的過濾器，你真的不關心那裡的大象發生。實際上， 池化 還可以為您提供平移，旋轉和縮放的不變性。第二個關鍵方面是（本地）組合性。每個過濾器 組成 將較低級別功能的本地補丁轉換為更高級別的表示。這就是CNN在計算機視覺領域如此強大的原因。直觀地說，您可以從像素，邊緣形狀和形狀中更復雜的對象構建邊緣。

TextCNN簡介

是CNN的一種變形，CNN(2011)主要運用於圖片分類，而TextCNN主要用於文本分類(2014)，其對於字的表示方式為：使用一個k維向量來表示在句子中的詞。

代替圖像像素，大多數NLP任務的輸入是表示為矩陣的句子或文檔。矩陣的每一行對應一個標記，通常是一個單詞，但它可以是一個字元。也就是說，每行是表示單詞的向量。通常，這些向量是 word嵌入   （低維表示），如 word2vec 或 GloVe ，但它們也可以是將單詞索引為詞彙表的單熱向量。對於使用100維嵌入的10個單詞的句子，我們將使用10×100矩陣作為輸入。這是我們的「形象」。

這里對上面那段話做一些解釋，在文本輸入之前，要先根據這些句子中包含的字做一個詞典，每個詞對應一個序號，假如一個句子有十個單詞，那麼就將這些單詞轉換為數字，作為矩陣數據到CNN中，這就類似於圖片CNN處理，因為圖片本來就是有一個個像素值組成的，輸入到CNN中的本來就是像素值，處理圖像也比處理文本更加的方便一些。

在視覺中，我們的濾鏡會滑過圖像的局部色塊，但在NLP中，我們通常使用在矩陣的整行上滑動的濾鏡（單詞）。因此，我們的濾波器的「寬度」通常與輸入矩陣的寬度相同。高度或 區域大小 可以變化，但是通常一次滑動超過2-5個單詞的窗口。將上述所有內容放在一起，NLP的卷積神經網路可能看起來像這樣

在之前 什麼是卷積 的介紹中的第一張圖片我們可以看到，過濾器是上下左右滑動的，從而來提取特徵值，最終獲得特徵矩陣，但是文本的話稍有不同，他不能左右滑動，只能上下滑動，原因很簡單，不能將一個單詞分開來進行訓練，如果非要這樣的話，卷積之後獲得的數據將會沒有什麼意義，所以過濾器在進行文本處理的時候只能上下滑動，下面來看一下這個圖片。

用於句子分類的卷積神經網路（CNN）架構的例證。這里我們描述了三個濾波器區域大小：2,3和4，每個都有2個濾波器。每個濾波器對句子矩陣執行卷積並生成（可變長度）特徵映射。然後在每個地圖上執行1最大合並，即，記錄來自每個特徵地圖的最大數量。因此，從所有六個圖生成單變數特徵向量，並且這六個特徵被連接以形成倒數第二層的特徵向量。最後的softmax圖層然後接收該特徵向量作為輸入並使用它來對句子進行分類; 這里我們假設二元分類，因此描述了兩種可能的輸出狀態。

過濾器生成的特徵向量是由上下滑動產生的，具體的過程可以參照下面這張圖片。

參考

理解NLP的卷積神經網路

Text-CNN文本分類

在TensorFlow中實現CNN進行文本分類

理解卷積

keras指南

Tensorflow簡介

Scrapy框架入門簡介

⑶ NLP第九篇-句法分析

句法分析的基本任務是確定句子的 語法結構 或句子中 詞彙之間的依存關系 。句法分析不是一個自然語言處理任務的最終目標，但它往往是實現最終目標的關鍵環節。

句法分析分為 句法結構分析 和 依存關系分析 兩種。以獲取整個句子的句法結構為目的的稱為 完全句法分析 ，而以獲得局部成分為目的的語法分析稱為 局部分析 ，依存關系分析簡稱 依存分析 。

一般而言，句法分析的任務有三個：

判斷輸出的字元串是否屬於某種語言

消除輸入句子中詞法和結構等方面的歧義

分析輸入句子的內部結構，如成分構成、上下文關系等。

第二三個任務一般是句法分析的主要任務。

一般來說，構造一個句法分析器需要考慮兩部分工作：一部分是語法的形式化表示和詞條信息描述問題，形式化的語法規則構成了規則庫，詞條信息等由詞典或同義詞表等提供，規則庫與詞典或同義詞表構成了句法分析的知識庫；另一部分就是基於知識庫的解析演算法了。

語法形式化屬於句法理論研究的范疇，目前在自然語言處理中廣泛使用的是上下文無關文法（CFG）和基於約束的文法，後者又稱合一文法。

簡單的講，句法結構分析方法可以分為基於規則的分析方法和基於統計的分析方法兩大類。

基於規則的句法結構分析方法的基本思路是，由人工組織語法規則，建立語法知識庫，通過條件約束和檢查來實現句法結構歧義的消除。

根據句法分析樹形成方向的區別，人們通常將這些方法劃分為三種類型：自頂向下的分析方法，自底向上的分析方法和兩者相結合的分析方法。自頂向下分析演算法實現的是規則推導的過程，分析樹從根結點開始不斷生長，最後形成分析句子的葉結點。而自底向上分析演算法的實現過程恰好想法，它是從句子符號串開始，執行不斷規約的過程，最後形成根節點。

基於規則的語法結構分析可以利用手工編寫的規則分析出輸入句子所有可能的句法結構；對於特定領域和目的，利用有針對性的規則能夠較好的處理句子中的部分歧義和一些超語法（extra-grammatical）現象。

但對於一個中等長度的輸入句子來說，要利用大覆蓋度的語法規則分析出所有可能的句子結構是非常困難的，而且就算分析出來了，也難以實現有效的消歧，並選擇出最有可能的分析結果；手工編寫的規則帶有一定的主觀性，還需要考慮到泛化，在面對復雜語境時正確率難以保證；手工編寫規則本身就是一件大工作量的復雜勞動，而且編寫的規則領域有密切的相關性，不利於句法分析系統向其他領域移植。

基於規則的句法分析演算法能夠成功的處理程序設計語言的編譯，而對於自然語言的處理卻始終難以擺脫困境，是因為程序設計語言中使用的知識嚴格限制的上下文無關文法的子類，但自然語言處理系統中所使用的形式化描述方法遠遠超過了上下文無關文法的表達能力；而且人們在使用程序設計語言的時候，一切表達方式都必須服從機器的要求，是一個人服從機器的過程，這個過程是從語言的無限集到有限集的映射過程，而在自然語言處理中則恰恰相反，自然語言處理實現的是機器追蹤和服從人的語言，從語言的有限集到無限集推演的過程。

完全語法分析

基於PCFG的基本分析方法

基於概率上下文無關文法的短語結構分析方法，可以說是目前最成功的語法驅動的統計句法分析方法，可以認為是規則方法與統計方法的結合。

PCFG是CFG的擴展，舉個例子：

PCFG

當然，同一個符號不同生成式的概率之和為1。NP是名詞短語、VP是動詞短語、PP是介詞短語。

基於PCFG的句法分析模型，滿足以下三個條件：

位置不變性：子樹的概率不依賴於該子樹所管轄的單詞在句子中的位置

上下文無關性：子樹的概率不依賴於子樹控制范圍以外的單詞

祖先無關性：子樹的概率不依賴於推導出子樹的祖先節點

根據上述文法，『He met Jenny with flowers』有兩種可能的語法結構：

而且我們可以通過將樹中的所有概率相乘，得到兩棵子樹的整體概率，從中選擇概率更大的子樹作為最佳結構。

與HMM類似，PCFG也有三個基本問題：

給定一個句子W＝w1w2…wn和文法G，如何快速計算概率P(W|G)

給定一個句子W＝w1w2…wn和文法G，如何選擇該句子的最佳結構？即選擇句法結構樹t使其具有最大概率

給定PCFG G和句子W＝w1w2…wn，如何調節G的概率參數，使句子的概率最大

首先是第一個問題，HMM中我們用的是前向演算法和後向演算法來計算觀察序列O概率，相似的，這里我們用的是內向演算法和外向演算法來計算P(W|G) 。

首先我們定義內向變數αij(A)，與前向變數相似但又有不同，αij(A)即非終結符A推導出W中字串wiw(i+1)…wj的概率。那P(W|G)自然就等於α1n(S)了，S是起始符號，計算的就是由起始符號S推導出整個句子W=w1w2…wn的概率。

所以只要有αij(A)的遞歸公式就能計算出P(W|G)，遞歸公式如下：

根據定義，αii(A)自然就等同於符號A輸出wi的概率；而αij(A)的計算思路是，這個子串wiw(i+1)…wj可以被切成兩部分處理，前一部分wiw(i+1)…wk由非終結符號B生成，後一部分wkw(k+1)…wj由非終結符號C生成，而BC由A生成。這樣將概率依次相乘，即可將一個大問題劃分為兩個小問題處理，兩個小問題又可以進一步劃分直到不能劃分為止，然後遞歸回來得到結果。

這里給一張內向變數計算方法示意圖：

這個問題也可以用外向演算法來解決。

首先定義外向變數，βij(A)是，初始符號S在推導出語句W=w1w2…wn的過程中，產生符號串w1w2…w(i-1)Aw(j+1)…wn的概率（隱含著A會生成wiw(i+1)…wj）。也就是說βij(A)是S推導出除了以A節點為根節點的子樹以外的其他部分的概率。

《統計自然語言處理（第二版）》這本書里講錯了，這里我給出我自己的理解，書里給的演算法步驟如下：

很明顯的錯誤，初始化都把結果初始化了，那這個演算法還算什麼，直接等於1就完了唄。

這是作者對外向變數定義理解模糊的問題，上面給了外向變數的定義，裡面有一句話『隱含著A會生成wiw(i+1)…wj』，那問題在於，A會生成wiw(i+1)…wj，這到底算是條件還是推論。

看這個演算法的初始化的意思，說β1n(A)，在A=S的時候，為1，不等於S為0，意思是什麼？意思就是『隱含著A會生成wiw(i+1)…wj』這句話是條件，β1n(S)已經隱含了S生成W＝w1w2…wn了，所謂的w1w2…w(i-1)Aw(j+1)…wn也就不存在了，只剩下一個S->S了，所以概率自然為1。

但是在第三步這個地方，作者理解成什麼意思了呢？作者又把『隱含著A會生成wiw(i+1)…wj』這句話當成推論了，認為在β1n(S)，里S會生成W＝w1w2…wn是推論，那真是就正好了，要求的結果就是S生成W＝w1w2…wn，這不就結束了嗎，結果就導致了這個演算法第一步初始化都把結果初始化了。

那我的理解是什麼呢，通過這個公式計算出來的β1n(S)，確實是正確的，意義實際上也是包含了『隱含著A會生成wiw(i+1)…wj』這句話是推論，但是右側式子里由於不斷遞歸而產生的β1n(S)，是把『隱含著A會生成wiw(i+1)…wj』這句話當條件的，所以計算上沒有問題。

我傾向於為第三步中的β1n(S)加一個星號，以表明意義的不同。

書中還給了個外向變數的計算方法示意圖，我覺得也是莫名其妙：

他說βij(A)是這兩種情況的概率和，這我們知道j比i大，那這圖里這個k既比i小又比j大，這不是搞笑嗎。只能說圖上這倆C就不是一個C，k也不是一個k。

那我為什麼會理解成一個呢，除了字母相同，他前面還這么講『必定運用了形如B->AC或者B->CA的規則』、『運用B->AC或者B->CA兩種規則的情況』，這明顯就是給人以順序交換的誤解。

另外，還在內向變數的使用上前後不一，可以說這本書里對外向演算法的講解是非常失敗的。而且對外向演算法的計算仍然需要用到內向演算法的遞歸，那真的直接用內向演算法就好了，外向演算法還要多定義變數。

然後是第二個問題，選擇句子的最佳結構，也即給定一個句子W＝w1w2…wn和文法G，

選定擁有最大概率的語法結構樹。這一問題與HMM中類似，仍然採用動態規劃的思想去解決。最後利用CYK演算法去生成擁有最大概率的語法結構樹。

第三個問題是給定PCFG G和句子W＝w1w2…wn，如何調節G的概率參數，使句子的概率最大，與HMM相對的，PCFG這里採用的演算法名叫內外向演算法。與前後向演算法相同，也屬於一種EM演算法，其基本思想是，首先給G的產生式隨機地賦予一個概率值（滿足歸一化條件），得到文法G0，然後根據G0和訓練數據，可以計算出每條規則使用次數的期望值，用期望值進行最大似然估計，得到語法G的新參數值，新的語法記作G1，然後循環執行該過程，G的參數概率將收斂於最大似然估計值。

PCFG只是一種特殊的上下文無關文法模型，根據PCFG的模型和句子，具體去對句子做語法分析，生成語法結構樹，靠的是還是CYK演算法。CYK演算法是一個用來判定任意給定的字元串W是否屬於一個上下文無關文法的演算法。

基於PCFG的句法分析模型存在有許多問題，比如因為PCFG沒有對詞彙進行建模，所以存在對詞彙信息不敏感的問題。因此人們提出了詞彙化的短語結構分析器，有效的提升了基於PCFG的句法分析器的能力。

而且，我們上面也提到了PCFG的三個獨立性假設，這也導致了規則之間缺乏結構依賴關系（就像HMM的三個假設也不完全合理一樣），而在自然語言中，生成每個非終結符的概率往往是與其上下文結構有關系的，所以有人提出了一種細化非終結符的方法，為每個非終結符標註上其父節點的句法標記信息。

D. Klein提出了帶有隱含標記的上下文無關文法（PCFG with latent annotations，PCFG-LA），使得非終結符的細化過程可以自動進行，並且在使用EM演算法優化時，為避免到達局部最優，對其進行了改進，提出了一種層次化的『分裂-合並』策略，以期獲取一個准確並且緊湊的PCFG-LA模型。基於PCFG-LA的Berkeley Parser作為非詞彙化句法分析器的代表，無論是性能表現還是運行速度，都是目前開源的短語結構分析器中最好的。其語法樹如下圖：

普通句法樹與PCFG-LA句法樹對照實例

這個x就是隱含標記，xi的取值范圍一般是人為設定的，一般取1~16之間的整數。而且PCFG-LA也類似於HMM模型，原始非終結符對應HMM模型中的觀察輸出，而隱含標記對應HMM模型中的隱含狀態。

淺層語法分析（局部語法分析）

由於完全語法分析要確定句子所包含的全部句法信息，並確定句子中各成分之間的關系，這是一項十分苦難的任務。到目前為止，句法分析器的各方面都難以達到令人滿意的程度，為了降低問題的復雜度，同時獲得一定的句法結構信息，淺層句法分析應運而生。

淺層語法分析只要求識別句子中的某些結構相對簡單的獨立成為，例如非遞歸的名詞短語、動詞短語等，這些被識別出來的結構通常稱為語塊（chunk）。

淺層句法分析將句法分析分解為兩個主要子任務，一個是語塊的識別和分析，另一個是語塊之間的依附關系分析。其中，語塊的識別和分析是主要任務。在某種程度上說，淺層句法分析使句法分析的任務得到了簡化，同時也有利於句法分析系統在大規模真實文本處理系統中迅速得到應用。

基本名詞短語（base NP）是語塊中的一個重要類別，它指的是簡單的、非嵌套的名詞短語，不含有其他子項短語，並且base NP之間結構上是獨立的。示例如下：

base NP識別就是從句子中識別出所有的base NP，根據這種理解，一個句子中的成分和簡單的分為baseNP和非base NP兩類，那麼base NP識別就成了一個分類問題。

base NP的表示方法有兩種，一種是括弧分隔法，一種是IOB標注法。括弧分隔法就是將base NP用方括弧界定邊界，內部的是base NP，外部的不屬於base NP。IOB標注法中，字母B表示base NP的開端，I表示當前詞語在base NP內，O表示詞語位於base NP之外。

基於SVM的base NP識別方法

由於base NP識別是多值分類問題，而基礎SVM演算法解決的是二值分類問題，所以一般可以採用配對策略（pairwise method）和一比其餘策略（one vs. other method）。

SVM一般要從上下文的詞、詞性、base NP標志中提取特徵來完成判斷。一般使用的詞語窗口的長度為5（當前詞及其前後各兩個詞）時識別的效果最好。

基於WINNOW的base NP識別方法

WINNOW是解決二分問題的錯誤驅動的機器學習方法，該方法能從大量不相關的特徵中快速學習。

WINNOW的稀疏網路（SNoW）學習結構是一種多類分類器，專門用於處理特徵識別領域的大規模學習任務。WINNOW演算法具有處理高維度獨立特徵空間的能力，而在自然語言處理中的特徵向量恰好具有這種特點，因此WINNOW演算法也常用於詞性標注、拼寫錯誤檢查和文本分類等等。

簡單WINNOW的基本思想是，已知特徵向量和參數向量和實數閾值θ，先將參數向量均初始化為1，將訓練樣本代入，求特徵向量和參數向量的內積，將其與θ比較，如果大於θ，則判定為正例，小於θ則判定為反例，將結果與正確答案作比較，依據結果來改變權值。

如果將正例估計成了反例，那麼對於原來值為1的x，把它的權值擴大。如果將反例估計成了正例，那麼對於原來值為1的x，把它的權值縮小。然後重新估計重新更改權重，直到訓練完成。

這其實讓我想到了LR演算法，因為LR演算法也是特徵向量與參數向量的內積，最後將其送到Sigmoid函數中去拿到判定結果，然後大於0.5的為正例，小於0.5的為反例，實際上只要反過來，Sigmod函數輸出0.5時候的輸入就是WINNOW演算法里的那個實數閾值θ。但是區別在於WINNOW演算法只判定大小，不判定概率，而LR利用Sigmoid函數給出了概率。LR利用這給出的概率，通過使訓練集的生成概率最大化來調整參數，而WINNOW則是直接樸素的錯誤情況來增大或縮小相關參數。目測LR因為使用了梯度下降，它的收斂速度要快於WINNOW，而WINNOW的優勢則在於可以處理大量特徵。

基於CRF的base NP識別方法

基於CRF的base NP識別方法擁有與SVM方法幾乎一樣的效果，優於基於WINNOW的識別方法、基於MEMM的識別方法和感知機方法，而且基於CRF的base NP識別方法在運行速度上較其他方法具有明顯優勢。

依存語法理論

在自然語言處理中，我們有時不需要或者不僅僅需要整個句子的短語結構樹，而且要知道句子中 詞與詞之間的依存關系 。用詞與詞之間的依存關系來描述語言結構的框架成為依存語法，又稱從屬關系語法。利用依存語法進行句法分析也是自然語言理解的重要手段之一。

有人認為，一切結構語法現象可以概括為關聯、組合和轉位這三大核心。句法關聯建立起詞與詞之間的從屬關系，這種從屬關系由 支配詞 和 從屬詞 聯結而成， 謂語中的動詞是句子的中心並支配別的成分，它本身不受其他任何成分支配 。

依存語法的本質是一種結構語法，它主要研究以謂詞為中心而構句時由深層語義結構映現為表層語法結構的狀況及條件，謂詞與體詞之間的同現關系，並據此劃分謂詞的詞類。

常用的依存於法結構圖示有三種：

計算機語言學家J. Robinson提出了依存語法的四條公理：

一個句子只有一個獨立的成分

句子的其他成分都從屬於某一成分

任何一個成分都不能依存於兩個或兩個以上的成分

如果成分A直接從屬於成分B，而成分C在句子中位於A和B之間，那麼，成分C或者屬於成分A，或者從屬於B，或者從屬於A和B之間的某一成分。

這四條公理相當於對依存圖和依存樹的形式約束：單一父節點、連通、無環和可投射，由此來保證句子的依存分析結果是一棵有根的樹結構。

這里提一下可投射，如果單詞之間的依存弧畫出來沒有任何的交叉，就是可投射的（參考上面的兩個有向圖）。

為了便於理解，我國學者提出了依存結構樹應滿足的5個條件：

單純結點條件：只有終結點，沒有非終結點

單一父結點條件：除根節點沒有父結點外，所有的結點都只有一個父結點

獨根結點條件：一個依存樹只能有一個根結點，它支配其他結點

非交條件：依存樹的樹枝不能彼此相交

互斥條件：從上到下的支配關系和從左到右的前於關系之間是相互排斥的，如果兩個結點之間存在著支配關系，它們就不能存在於前於關系

這五個條件是有交集的，但它們完全從依存表達的空間結構出發，比四條公理更直觀更實用。

Gaifman 1965年給出了依存語法的形式化表示，證明了依存語法與上下文無關文法沒有什麼不同..

類似於上下文無關文法的語言形式對被分析的語言的投射性進行了限制，很難直接處理包含非投射現象的自由語序的語言。20世紀90年代發展起來了約束語法和相應的基於約束滿足的依存分析方法，可以處理此類非投射性語言問題。

基於約束滿足的分析方法建立在約束依存語法之上，將依存句法分析看做可以用約束滿足問題來描述的有限構造問題。

約束依存語法用一系列形式化、描述性的約束將不符合約束的依存分析去掉，直到留下一棵合法的依存樹。

生成式依存分析方法、判別式依存分析方法和確定性依存分析方法是數據驅動的統計依存分析中具有代表性的三種方法。

生成性依存分析方法

生成式依存分析方法採用聯合概率模型生成一系列依存語法樹並賦予其概率分值，然後採用相關演算法找到概率打分最高的分析結果作為最後輸出。

生成式依存分析模型使用起來比較方便，它的參數訓練時只在訓練集中尋找相關成分的計數，計算出先驗概率。但是，生成式方法採用聯合概率模型，再進行概率乘積分解時做了近似性假設和估計，而且，由於採用全局搜索，演算法的復雜度較高，因此效率較低，但此類演算法在准確率上有一定優勢。但是類似於CYK演算法的推理方法使得此類模型不易處理非投射性問題。

判別式依存分析方法

判別式依存分析方法採用條件概率模型，避開了聯合概率模型所要求的獨立性假設（考慮判別模型CRF舍棄了生成模型HMM的獨立性假設），訓練過程即尋找使目標函數（訓練樣本生成概率）最大的參數θ（類似Logistic回歸和CRF）。

判別式方法不僅在推理時進行窮盡搜索，而且在訓練演算法上也具有全局最優性，需要在訓練實例上重復句法分析過程來迭代參數，訓練過程也是推理過程，訓練和分析的時間復雜度一致。

確定性依存方法

確定性依存分析方法以特定的方向逐次取一個待分析的詞，為每次輸入的詞產生一個單一的分析結果，直至序列的最後一個詞。

這類演算法在每一步的分析中都要根據當前分析狀態做出決策（如判斷其是否與前一個詞發生依存關系），因此，這種方法又稱決策式分析方法。

通過一個確定的分析動作序列來得到一個唯一的句法表達，即依存圖（有時可能會有回溯和修補），這是確定性句法分析方法的基本思想。

短語結構與依存結構之間的關系

短語結構樹可以被一一對應地轉換成依存關系樹，反之則不然。因為一棵依存關系樹可能會對應多棵短語結構樹。

⑷ 編譯原理-句型、句子、短語、直接短語、句柄、素短語、最左素短語

在進行語法分析的時候，有時候會對這些詞語的概念不清晰，這里我們就詳細歸納總結一下。

可以看出這個裡面，最需要理解的概念就是短語，其他大部分概念都是在短語基礎上延伸的，從概念上可以看出：

假設有一個文法

針對文法的一個特定句型 (Sd(T)db) , 其推導過程如下:

這個句型 (Sd(T)db) 對應的 CFG 分析樹如下：

那個這個句型 (Sd(T)db) 有多少個短語呢？

還記得短語的定義么， S ⇒* αβδ ， αβδ 代表句型就是這里的 (Sd(T)db) 。

因此這個句型 (Sd(T)db) :

演算法非常簡單，就是通過分析樹的後序遍歷，先將子樹的葉節點從左到右排合並成字元串(即一個短語)，然後用它代表子樹的根節點的值，再和與子樹根節點同一層節點值合並，得到新的短語。就這樣從分析樹的最底層，一路合並到分析樹的根節點，就能得到所有的短語了。

通過遞歸的方法，獲取短語列表 phraseList , 直接短語列表 directPhraseList 和 素短語列表 plainPhraseList 。

運行結果:

⑸ 怎樣通過句法分析分析句子情感演算法例子

怎樣通過句法分析分析句子情感演算法例子？現階段主要的情感分析方法主要有兩類：
基於詞典的方法
基於機器學習的方法
基於詞典的方法主要通過制定一系列的情感詞典和規則，對文本進行段落拆借、句法分析，計算情感值，最後通過情感值來作為文本的情感傾向依據。
基於機器學習的方法大多將這個問題轉化為一個分類問題來看待，對於情感極性的判斷，將目標情感分類2類：正、負。對訓練文本進行人工標標注，然後進行有監督的機器學習過程。例如想在較為常見的基於大規模語料庫的機器學習等。

⑹ 如何用語句和演算法寫程序

演算法步驟:第一步，要確定表示和的變數s和計數變數i，並賦值，一般情況下，賦s=0 i=0;第二步，確定使用哪種循環結構，本題使用當型循環結構，確定判斷條件i≤9 滿足條件時，執行第三步，不滿足條件時，執行第四步；第三步：執行，i=i+1;第四步：輸出s；程序結束.程序如下:S=0i=0WHILE i<=9 S=S+1/2^i i=i+1ENDPRINT SEND運行該程序，輸出:S=1.9980. 解析 分 析： 演算法分析: 第一步 選擇一個變數S表示和，並賦給初值0 再選取一個循環變數i，並賦值為0；第二步 開始進入WHILE循環語句，首先判斷i是否小於9；第三步 為循環表達式(循環體) 用WEND來控制循環；第四步 用END來結束程序． 根據演算法語句編寫相應的程序語言，見參考答案.試題 解析： 演算法步驟:第一步，要確定表示和的變數s和計數變數i，並賦值，一般情況下，賦s=0 i=0;第二步，確定使用哪種循環結構，本題使用當型循環結構，確定判斷條件i≤9 滿足條件時，執行第三步，不滿足條件時，執行第四步；第三步：執行，i=i+1;第四步：輸出s；程序結束.可寫出程序如下:S=0i=0WHILE i<=9 S=S+1/2^i i=i+1ENDPRINT SEND運行該程序，輸出:S=1.9980． （12分） 考點： 程序語言.

⑺ if語句中含有for循環語句的演算法復雜度分析

一樓的回答是sb，希望那些沒好好學演算法的人就別在這里禍害學生。
時間復雜度很好算，實際上它是一個1+2+3.....+m=n的過程。等於n後循環終止。m好算吧？m=根號下（2n+1/4）-1/2.
所以時間復雜度是o(根號n).

⑻ 數據結構與演算法中分析語句的執行次數怎麼算

1）時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句數據結構與演算法中分析語句的執行次數怎麼算