编译词语分析器下载

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 软件