！！编译原理DFA和NFA

DFA或NFA是对计档模算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1 程序： if(a==1) b=1 这个程序对应了一个自动机。

对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)

比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就侍衡是(1,1)。

画图出来就是 这4个状态作为顶点，并且有下面几条边

(0,0) -->(0,0)（自环）,(1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环

存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。

最经典体现自动机思想的算法就是KMP算法，你肯定学老蠢做过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。

既然你都知道它们是码销宏怎么回事儿了，怎么会不明白它们和词法分析程序的关系呢？

简单点儿说，词法分析就是进行迟册正则表达式匹配斗稿。词法分析程序就是根据要匹配的正则表达式生成它的NFA或者DFA，再将待匹配的字符串放到这些NFA或者DFA中进行处理，从而分析出输入字符串是否匹配给定的正则表达式。

#include <iostream>

#include <string>

using namespace std

string key[6] = {"begin", "if", "then", "while", "do", "end"}

//关键字

bool isKey( string str, int &syn) //判断是否为关键字，若是传虚雀回相

应关键码的种别名

{

int i

for(i=0i<6i++)

{

if(str == key[i])

{

syn = i + 1

return true

}

}

return false

}

bool isLetter(char c) //是否为字母

{

if((c >= 'A' &&c <= 'Z') || (c >= 'a' &&c <= 'z'))

return true

else

return false

}

bool isDigit(char c) //是否为数字

{

if(c >= '0' &&c <= '9')

return true

else

return false

}

void analyse(FILE *fileP)

{

int n

char c

string str = ""

while((c = fgetc(fileP)) != EOF)

{

if(c == ' ' || c == '\n' || c == '\t')

continue

else if(isDigit(c)) //数字

{

while(isDigit(c))

{

str += c

c = fgetc(fileP)

}

fseek(fileP, -1, SEEK_CUR)

cout <<"(11, " <<str <瞎誉嫌<")" <<endl

str = ""

}

else if(isLetter(c)) //字母开头的

{

while(isDigit(c) || isLetter(c))

{

str += c

c = fgetc(fileP)

}

fseek(fileP, -1, SEEK_CUR)

if(isKey(str, n))

cout <<"(" <<n <<", " <<str <<")" <<endl//关键码

else

cout <<"(10, " <<"\'"<<str <<"\'" <<")" <<endl//标志符

str = ""

}

else // *** 作符等

{

switch(c)

{

case '+':

cout <<"(13, +)" <<endl

break

case '-':

cout <<"(14, -)" <<endl

break

case '*':

cout <<"(15, *)" <<endl

break

case '/':

cout <<"(16, /)" <<endl

break

case ':':

{

if(c=fgetc(fileP) == '=')

cout <磨手<"(18, :=)" <<endl

else

{

cout <<"(17, :)" <<endl

fseek(fileP, -1, SEEK_CUR)

}

break

}

case '<':

{

c=fgetc(fileP)

if(c == '=')

cout <<"(22, <=)" <<endl

else if(c == '>')

cout <<"(21, <>)" <<endl

else

{

cout <<"(20, <)" <<endl

fseek(fileP, -1, SEEK_CUR)

}

break

}

case '>':

{

c=fgetc(fileP)

if(c == '=')

cout <<"(24, >=)" <<endl

else

{

cout <<"(23, >)" <<endl

fseek(fileP, -1, SEEK_CUR)

}

break

}

case '=':

cout <<"(25, =)" <<endl

break

case '':

cout <<"(26, )" <<endl

break

case '(':

cout <<"(27, ()" <<endl

break

case ')':

cout <<"(28, ))" <<endl

break

case '#':

cout <<"(0, #)" <<endl

break

}

}

}

}

int main()

{

FILE *fileP

fileP = fopen("test.txt", "r")

cout <<"------词法分析如下------" <<endl

analyse(fileP)

return 0

}

---