編譯詞語分析器下載

1. 編譯原理語法分析器程序設計，用C語言或C++，哪裡有這個程序

我寫好的.
scan.h

/*
* scan.h
* ccompiler
*
* Created by on 09-10-12.
* Copyright 2009 __MyCompanyName__. All rights reserved.
*
*/

#ifndef _SCAN_H_
#define _SCAN_H_

#include <string>
#include <fstream>
using namespace std;

typedef enum
{
ENDFILE,ERROR,
ELSE,IF,INT,RETURN,VOID,WHILE,
ID,NUM,
ASSIGN,EQ,LT,GT,LE,GE,NE,ADD,SUB,MUL,DIV,SEMI,LPAREN,RPAREN,LZK,RZK,LDK,RDK,COMMA
}
TokenType;

class Scan
{
private:
string tokenStr;
string linebuffer;
ifstream * in;
int linepos;
int lineno;
bool EOF_Flag;
bool traceScan;
void printToken(TokenType tt,const string &tok);
public:
Scan(ifstream * in)
{
this->in=in;
linepos=0;
linebuffer="";
lineno=0;
EOF_Flag=false
traceScan=true;
}
char getNextChar();

void ungetNextChar();

TokenType reservedLookup(string &s);

void setTraceScan(bool f);

bool getTraceScan();

TokenType getToken();

string getTokenStr();

};
#endif

scan.cpp

/*
* scan.cpp
* ccompiler
*
* Created by on 09-10-12.
* Copyright 2009 __MyCompanyName__. All rights reserved.
*
*/

#include <string>
#include <fstream>
#include <iostream>
using namespace std;

#include "scan.h"

typedef enum
{START,INNUM,INID,INNOTEQ,TEMPE,TEMPG,TEMPL,SLASH,INCOMMENT1,INCOMMENT2,DONE}
StateType;

static struct
{
string str;
TokenType tok;
} reservedWords[6]
={{"else",ELSE},{"if",IF},{"int",INT},{"return",RETURN},{"void",VOID},{"while",WHILE}};

char Scan::getNextChar()
{
if(linepos>=linebuffer.size())
{
if(getline(*in,linebuffer))
{
linebuffer+="\n";
lineno++;
linepos=0;
return linebuffer[linepos++];
}
else
{
EOF_Flag=true;
return EOF;
}
}
else
return linebuffer[linepos++];
}

void Scan::ungetNextChar()
{
if(!EOF_Flag) linepos--;
}

TokenType Scan::reservedLookup(string &s)
{
for(int i=0;i<6;i++)
if(s==reservedWords[i].str)
return reservedWords[i].tok;
return ID;
}

void Scan::setTraceScan(bool f)
{
traceScan=f;
}

bool Scan::getTraceScan()
{
return traceScan;
}

TokenType Scan::getToken()
{
tokenStr="";
TokenType currentToken;
StateType state=START;

while(state!=DONE)
{
bool save=false;
char c=getNextChar();
switch (state) {
case START:
if(c>='0'&&c<='9'){
state=INNUM;
save=true;
}
else if((c>='a'&&c<='z')||(c>='A'&&c<='Z')){
state=INID;
save=true;
}
else if(c==' '||c=='\t'||c=='\n')
{
state=START;
}
else if(c=='/'){
state=SLASH;
}
else if(c=='='){
state=TEMPE;
}
else if(c=='>')
state=TEMPG;
else if(c=='<')
state=TEMPL;
else if(c=='!')
state=INNOTEQ;
else
{
state=DONE;
switch (c) {
case EOF:
currentToken=ENDFILE;
break;
case '+':
currentToken=ADD;
break;
case '-':
currentToken=SUB;
break;
case '*':
currentToken=MUL;
break;
case '(':
currentToken=LPAREN;
break;
case ')':
currentToken=RPAREN;
break;
case '[':
currentToken=LZK;
break;
case ']':
currentToken=RZK;
break;
case '{':
currentToken=LDK;
break;
case '}':
currentToken=RDK;
break;
case ';':
currentToken=SEMI;
break;
case ',':
currentToken=COMMA;
break;
default:
currentToken=ERROR;
break;
}
}
break;
case INNUM:
if(c<'0'||c>'9')
{
ungetNextChar();
state=DONE;
currentToken=NUM;
}
else
save=true;
break;
case INID:
if(!((c>='a'&&c<='z')||(c>='A'&&c<='Z')))
{
ungetNextChar();
state=DONE;
currentToken=ID;
}
else
save=true;
break;
case SLASH:
if (c!='*')
{
state=DONE;
currentToken=DIV;
}
else
state=INCOMMENT1;
break;
case INCOMMENT1:
if (c!='*')
state=INCOMMENT1;
else if(c==EOF){
state=DONE;
currentToken=ENDFILE;
}
else
state=INCOMMENT2;
break;
case INCOMMENT2:
if (c=='*') {
state=INCOMMENT2;
}else if(c=='/'){
state=START;
}else if(c==EOF){
state=DONE;
currentToken=ENDFILE;
}else {
state=INCOMMENT1;
}
break;
case TEMPE:
if (c=='=') {
state=DONE;
currentToken=EQ;
}else{
state=DONE;
ungetNextChar();
currentToken=ASSIGN;
}
break;
case TEMPG:
if (c=='=') {
state=DONE;
currentToken=GE;
}else{
state=DONE;
ungetNextChar();
currentToken=GT;
}
break;
case TEMPL:
if (c=='=') {
state=DONE;
currentToken=LE;
}else{
state=DONE;
ungetNextChar();
currentToken=LT;
}
break;
case INNOTEQ:
if (c=='=') {
state=DONE;
currentToken=NE;
}else {
state=DONE;
ungetNextChar();
currentToken=ERROR;
}
break;

default:
cerr<<"Scanner Bug: state= "<<state<<endl;
state=DONE;
currentToken=ERROR;
break;
}
if(save){
string newChar(1,c);
tokenStr+=newChar;
}
if (state==DONE&¤tToken==ID)
currentToken=reservedLookup(tokenStr);
}
if (traceScan) {
cout<<"Scan at line "<<lineno<<" token: ";
printToken(currentToken, tokenStr);
cout<<endl;
}
return currentToken;
}

string Scan::getTokenStr()
{
return tokenStr;
}

void Scan::printToken(TokenType tt,const string &tok)
{
string type;
switch (tt) {
case ENDFILE:
type="EOF";
break;
case ERROR:
type="ERROR";
break;
case ELSE:
case IF:
case INT:
case RETURN:
case VOID:
case WHILE:
type="reserved word";
break;
case ID:
type="ID";
break;
case NUM:
type="NUM";
break;
case ASSIGN:
type="=";
break;
case EQ:
type="==";
break;
case LT:
type="<";
break;
case GT:
type=">";
break;
case LE:
type="<=";
break;
case GE:
type=">=";
break;
case NE:
type="!=";
break;
case ADD:
type="+";
break;
case SUB:
type="-";
break;
case MUL:
type="*";
break;
case DIV:
type="/";
break;
case SEMI:
type=";";
break;
case LPAREN:
type="(";
break;
case RPAREN:
type=")";
break;
case LZK:
type="[";
break;
case RZK:
type="]";
break;
case LDK:
type="{";
case RDK:
type="}";
break;
case COMMA:
type=",";
break;
default:
break;
}
cout << type<<": "<<tok;
}

main.cpp

#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#include "scan.h"

int main (int argc, char * const argv[]) {
string fileName="/Users/huanglongyin/scan_in.txt";
//cout<< "File name: ";
//cin>>fileName;
ifstream in(fileName.c_str());
if(!in){
cerr<<"Error occurs when openning file "<<fileName<<endl;
return -1;
}
Scan scan(&in);
while(scan.getToken()!=ENDFILE);
return 0;
}

2. 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）。

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

確定性依存方法

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

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

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

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

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

3. 編譯原理中的詞法分析器的輸入與輸出是什麼

編譯原理中的詞法分析器的輸入是源程序，輸出是識別的記號流。

詞法分析器編制一個讀單詞的程序，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數、運算符和分隔符五大類。並依次輸出各個單詞的內部編碼及單詞符號自身值。（遇到錯誤時可顯示「Error」，然後跳過錯誤部分繼續顯示）。

(3)編譯詞語分析器下載擴展閱讀

詞法分析器的作用：

1、與符號表進行交互，存儲和讀取符號表中的標識符的信息。

2、讀入源程序的輸入字元，將他們組成詞素，生成並輸出一個詞法單元序列，每個詞法單元序列對應一個於一個詞素。

3、過濾掉程序中的注釋和空白。

4、將編譯器生成的錯誤消息與源程序的位置聯系起。

4. 有沒有Lazada平台好的關鍵詞軟體

電霸Lazada是針對Lazada的數據分析軟體，他們有關鍵詞功能，可以看到熱度高的關鍵詞排 名，優化標題。

5. 英語Compiled怎麼翻譯

compiled這個單詞的意思是，編輯的，編譯的。這是一個過去分詞。動詞原形是compile。可以當形容詞使用。例如可以說片語，compiled language意思是編譯語言。

6. 我國編程語言倉頡首發，以後是否就不會用英文寫代碼了

我國編程語言倉頡首發，以後肯定就不會用英文寫代碼了，只要開發工具和編譯器可以准確解析編譯中文關鍵字，就可以研發出來的，這只不過是需要一個時間和過程而已，讓我們拭目以待吧！

為了讓中國用上自己的漢字編程，華為發布鴻蒙編程語言『倉頡』，用漢字編程語言。那麼以「倉頡」命名，主要因為中國方塊字、象形字創造者是「倉頡」，有很多人因為這個名字對這門編程語言進行推測的，認為很有可能是純漢字和純中文的編程，假如真的是全漢字，就會解決對很多英語並不熟練的認識。又想入門編程的需求，也有人推測真的是漢字編程，那肯定使用華為方舟編譯器來進行的中文字元的編譯。

4，中文編程語言是封閉的，絕對不是華為世界級高科技公司的主要選擇，與華為愛國與否根本沒有必然聯系，更與我們國家持續加大改革，開放力度和構建人類命運共同體趨勢不合拍！

我以為以上的言論不足以為道，當然還有不同的觀點。但很多人都人認為：我國編程語言倉頡首發，以後就不會用英文寫代碼了。最後我用一個網友的發表的評論作為結束語吧！編程只是用關鍵字遵循一定格式，組織邏輯，為什麼不能用中文？只要開發工具和編譯器可以准確解析編譯中文關鍵字，各種符號和格式，最終解析出來的還是機器碼！為什麼不能用中文？

7. 編譯原理詞法分析程序

（一）Block子程序分析

procere enter(k: object1); //填寫符號表
begin {enter object into table}
tx := tx + 1; //下標加1，tx的初始值為零，零下標不地址不填寫標志符，用於查找失敗使用
with table[tx] do //填入內容，保存標志符名和類型
begin name := id; kind := k;
case k of //根據類型判斷是否正確
constant: begin if num > amax then //如果是常量，判斷是否大於最大值，若是則報30號錯
begin error(30); num :=0 end;
val := num //否則保存數值
end;
varible: begin level := lev; adr := dx; dx := dx + 1; //如果是變數，填寫變數內部表示，LEVEl是變數的層次，adr為地址
end;
proc: level := lev //如果是過程，保存過程的層次
end
end
end {enter};

//查找符號表的位置
function position(id: alfa): integer;
var i: integer;
begin {find indentifier id in table} //從後向前查找
table[0].name := id; i := tx; //找到保存類型
while table[i].name <> id do i := i-1;
position := i //返回標志符在符號表中的位置
end {position};

procere block(lev,tx: integer; fsys: symset);
var dx: integer; {data allocation index} //數據分配索引
tx0: integer; {initial table index} //初始符號表索引
cx0: integer; {initial code index} //初始代碼索引
procere enter(k: object1); //填寫符號表，下次分析
begin {enter object into table}
tx := tx + 1;
with table[tx] do
begin name := id; kind := k;
case k of
constant: begin if num > amax then
begin error(30); num :=0 end;
val := num
end;
varible: begin level := lev; adr := dx; dx := dx + 1;
end;
proc: level := lev
end
end
end {enter};

function position(id: alfa): integer; //查找符號表，下次分析
var i: integer;
begin {find indentifier id in table}
table[0].name := id; i := tx;
while table[i].name <> id do i := i-1;
position := i
end {position};

procere constdeclaration; //常量聲明
begin if sym = ident then //如果是標志符，讀入一個TOKEN
begin getsym;
if sym in [eql, becomes] then //讀入的是等號或符值號繼續判斷
begin if sym = becomes then error(1); //如果是「=」報1號錯
getsym; //讀入下一個TOKEN
if sym = number then //讀入的是數字，填寫符號表
begin enter(constant); getsym
end
else error(2) //如果不是數字，報2號錯
end else error(3) //不是等號或符值號，報3號錯
end else error(4) //如果不是標志符，報4號錯
end {constdeclaration};

procere vardeclaration; //變數聲明
begin if sym = ident then //讀入的是標志符，填寫符號表
begin enter(varible); getsym
end else error(4) //不是標志符，報4號錯
end {vardeclaration};

procere listcode;
var i: integer;
begin {list code generated for this block}
for i := cx0 to cx-1 do
with code[i] do
writeln(i:5, mnemonic[f]:5, 1:3, a:5)
end {listcode};

procere statement(fsys: symset);
var i, cx1, cx2: integer;
procere expression(fsys: symset); //表達式分析
var addop: symbol;
procere term(fsys: symset); //項分析
var mulop: symbol;
procere factor(fsys: symset); //因子分析
var i: integer;
begin test(facbegsys, fsys, 24); //讀入的是「（」，標志符或數字
while sym in facbegsys do
begin
if sym = ident then //是標志符，查表
begin i:= position(id);
if i = 0 then error(11) else //未找到，報11號錯
with table[i] do //找到，讀入標志符類型
case kind of
constant: gen(lit, 0, val); //寫常量命令
varible: gen(lod, lev-level, adr);//寫變數命令
proc: error(21) //過程名，報21號錯
end;
getsym //讀入下一個TOKEN
end else
if sym = number then //讀入的是數字
begin if num > amax then //如果數字大於最大數，報30號錯誤
begin error(30); num := 0
end;
gen(lit, 0, num); getsym //調用數字命令，讀入下一個TOKEN
end else
if sym = lparen then //讀入的是「（」
begin getsym; expression([rparen]+fsys); //調用表達式分析函數
if sym = rparen then getsym else error(22) //如果「（」後無「）」，報22號錯
end;
test(fsys, [lparen], 23)
end
end {factor};//因子分析結束

//項分析
begin {term} factor(fsys+[times, slash]); //調用因子分析程序
while sym in [times, slash] do //取得是乘、除號循環
begin mulop:=sym;getsym;factor(fsys+[times,slash]); //記錄符號，調用因子分析
if mulop=times then gen(opr,0,4) else gen(opr,0,5) //寫乘除指令
end
end {term};
begin {expression}
if sym in [plus, minus] then //如果是加減號
begin addop := sym; getsym; term(fsys+[plus,minus]); //記錄符號，調用項分析程序
if addop = minus then gen(opr, 0,1) //寫加減指令
end else term(fsys+[plus, minus]);
while sym in [plus, minus] do //如果是加減號循環
begin addop := sym; getsym; term(fsys+[plus,minus]);
if addop=plus then gen(opr,0,2) else gen(opr,0,3)
end
end {expression};

//條件過程
procere condition(fsys: symset);
var relop: symbol;
begin
if sym = oddsym then //如果是判奇符
begin getsym; expression(fsys); gen(opr, 0, 6) //取下一個TOKEN，調用expression，填指令
end else
begin expression([eql, neq, lss, gtr, leq, geq]+fsys);
if not(sym in [eql, neq, lss, leq, gtr, geq]) then //如果不是取到邏輯判斷符號，出錯.20
error(20) else
begin relop := sym; getsym; expression(fsys);
case relop of
eql: gen(opr, 0, 8); // =，相等
neq: gen(opr, 0, 9); // #，不相等
lss: gen(opr, 0, 10); // <，小於
geq: gen(opr, 0, 11); // ]，大於等於
gtr: gen(opr, 0, 12); // >，大於
leq: gen(opr, 0, 13); // [，小於等於
end
end
end
end {condition};

begin {statement}
if sym = ident then //如果是標識符
begin i := position(id); //查找符號表
if i = 0 then error(11) else //未找到，標識符未定義，報11號錯
if table[i].kind <> varible then //如果標識符不是變數，報12號錯
begin {assignment to non-varible} error(12); i := 0
end;
getsym; if sym = becomes then getsym else error(13); //如果是變數讀入下一個TOKEN，不是賦值號，報13好錯；是則讀入一個TOKEN
expression(fsys); //調用表達是過程
if i <> 0 then //寫指令
with table[i] do gen(sto, lev-level, adr)
end else
if sym = callsym then //如果是過程調用保留字，讀入下一個TOKEN
begin getsym;
if sym <> ident then error(14) else //不是標識符報14號錯
begin i := position(id);
if i = 0 then error(11) else //是標識符，未定義，報13號錯
with table[i] do // 已定義的標識符讀入類型
if kind=proc then gen(cal, lev-level, adr) //是過程名寫指令
else error(15); //不是過程名，報15號錯
getsym
end
end else
if sym = ifsym then //如果是IF
begin getsym; condition([thensym, dosym]+fsys); //讀入一個TOKEN,調用條件判斷過程
if sym = thensym then getsym else error(16); //如果是THEN,讀入一個TOKEN，不是，報16號錯
cx1 := cx; gen(jpc, 0, 0); //寫指令
statement(fsys); code[cx1].a := cx
end else
if sym = beginsym then //如果是BEGIN
begin getsym; statement([semicolon, endsym]+fsys); //讀入一個TOKEN
while sym in [semicolon]+statbegsys do
begin
if sym = semicolon then getsym else error(10); //如果讀入的是分號
statement([semicolon, endsym]+fsys)
end;
if sym = endsym then getsym else error(17) //如果是END 讀入一個TOKEN，不是，報17號錯
end else
if sym = whilesym then //如果是WHILE
begin cx1 := cx; getsym; condition([dosym]+fsys); //調用條件過程
cx2 := cx; gen(jpc, 0, 0); //寫指令
if sym = dosym then getsym else error(18); //如果是DO讀入下一個TOKEN，不是報18號錯
statement(fsys); gen(jmp, 0, cx1); code[cx2].a := cx
end;
test(fsys, [], 19)
end {statement};

begin {block}
dx:=3;
tx0:=tx;
table[tx].adr:=cx;
gen(jmp,0,0);
if lev > levmax then error(32);
repeat
if sym = constsym then //如果是CONST
begin getsym; //讀入TOKEN
repeat constdeclaration; //常量聲明
while sym = comma do
begin getsym; constdeclaration
end;
if sym = semicolon then getsym else error(5) //如果是分號讀入下一個TOKEN，不是報5號錯
until sym <> ident //不是標志符常量聲明結束
end;
if sym = varsym then 如果是VAR
begin getsym; 讀入下一個TOKEN
repeat vardeclaration; //變數聲明
while sym = comma do
begin getsym; vardeclaration
end;
if sym = semicolon then getsym else error(5) //如果是分號讀入下一個TOKEN，不是報5號錯
until sym <> ident; //不是標志符常量聲明結束
end;
while sym = procsym do //過程聲明
begin getsym;
if sym = ident then
begin enter(proc); getsym
end
else error(4); //不是標志符報4號錯
if sym = semicolon then getsym else error(5); //如果是分號讀入下一個TOKEN，不是報5號錯
block(lev+1, tx, [semicolon]+fsys);
if sym = semicolon then //如果是分號，取下一個TOKEN，不是報5號錯
begin getsym;test(statbegsys+[ident,procsym],fsys,6)
end
else error(5)
end;
test(statbegsys+[ident], declbegsys, 7)
until not(sym in declbegsys); //取到的不是const var proc結束
code[table[tx0].adr].a := cx;
with table[tx0] do
begin adr := cx; {start adr of code}
end;
cx0 := 0{cx}; gen(int, 0, dx);
statement([semicolon, endsym]+fsys);
gen(opr, 0, 0); {return}
test(fsys, [], 8);
listcode;
end {block};

8. 編譯原理 詞法分析程序的設計與實現實驗題

說他像蒼蠅，是罵蒼蠅呢還是罵他呢？

9. 想要自學編譯原理，需要先學好哪些先修課給點好的學習建議。

首先要弄清楚編譯原理的本質。

編譯本質上就是翻譯，將一種語言翻譯成另一種語言，並且保證含義不變。

而編譯軟體大致分為
詞語分析、語法分析、語義分析以及其他部分。

詞語分析就分析一串串字母哪些屬於一個詞。
語法分析就是分析一串串詞哪些符合語法規則， 哪些不符合語法規則。
語義分析就是分析符合語法規則的詞，在特定語法規則下表達了什麼含義。

這是編譯軟體的前端，後端就是將這些含義轉換相應的機器指令。

10. 語料庫常用分析軟體 主要用來分析詞頻、詞語搭配、錯誤分析 如果有好幾個的話 請做一下橫向功能對比

用antconc 軟體