Note：

这学期修了严厉的Mr.J的编译原理，不定期更新笔记！
欢迎指正！

Github:

TEST 语言的词法规:

  • 标识符：字母打头，后接任意字母或数字

  • 保留字：标识符的子集，包括：if,else,for,while,do, int,write,read，

  • 无符号整数：由数字组成，但最高位不能为0，允许一位的0，

  • 分界符：(、)、;、{、}

  • 运算符：+、-、*、/、=、<、>、>=、<=、!=、==

  • 注释符：/ /

正则表达式：

  • 标识符：        ( a|b|……|z|A|B……|Z )( 0|1|……|9| a|b|……|z|A|B……|Z )*

  • 保留字：        标识符的子集

  • 无符号整数： ( (1……|9 )( 0|1|……|9)* )|0

  • 分界符：        ( | ) | ; | { | }

  • 运算符：        + | - | * | / | = | < | > | >= | <= | != | ==

  • 注释符：        /* (other)* */

NFA

不确定的有穷自动机

DFA

将NFA确定化之后得到的DFA

确定的有穷自动机

程序测试

依据DFA编写词法分析程序

  • 测试数据:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /*This a test program.*/
    int abc;
    int 123;
    int A$@;
    int i;
    int n;
    int b,c;
    int 2a;
    int a2;
    read n;
    n = 012345;
    for (i=1;i<=n; i= i+1)
    { 
    abc=abc+i;
    }
    if (!n) b = b+c;
    /*The loop ended
    write abc;
    }

  • 测试结果:

  • 分词结果：

SourceCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#define sum 8
FILE *fin, *fout;
char Dword[10] = "!><=";
char Infile[300], Outfile[300];
char Sword[50] = "+-*(){};";
char *keyword[sum] = { "if", "else", "for", "while", "do", "int", "read", "write" };
int test()
{
    char ch, Buff[40];
    int flag = 0, n, line = 1;
    int m = 0;
    printf("Name of Pro:");
    scanf("%s", Infile);
    printf("Name of Outfile:");
    scanf("%s", Outfile);
    if ((fin = fopen(Infile, "r")) == NULL)
    {
        printf("\nPro file open error！\n");
        return (1);
    }
    if ((fout = fopen(Outfile, "w")) == NULL)
    {
        printf("\nOutfile open error！\n");
        return (2);
    }
    ch = getc(fin);
    while (ch != EOF)
    {
        m = 0;
        memset(Buff, 0, 40);

        while (ch == ' ' || ch == '\n' || ch == '\t')
        {
            if (ch == '\n')
            {
                line++;
            }
            ch = getc(fin);
        }
        if (isalpha(ch))
        {
            while (isalpha(ch) || isdigit(ch))
            {
                Buff[m] = ch;
                m++;
                ch = getc(fin);
            }
            n = 0;
            while ((n < sum) && strcmp(Buff, keyword[n]))
            {
                n++;
            }
            if (n < sum)
            {
                fprintf(fout, "%s\t%s\n", "ID", Buff);
            }
            else
            {
                fprintf(fout, "%s\t%s\n", Buff, Buff);
            }
        } 
         else if (isdigit(ch))
        {
            if (ch == '0')
            {
                Buff[0] = '0';
                Buff[1] = '\0';
                fprintf(fout, "%s\t%s\n", "NUM", Buff);
                ch = getc(fin);
            }
            else
            {
                while (isdigit(ch))
                {
                    Buff[m] = ch;
                    m++;
                    ch = getc(fin);
                }
                Buff[m] = '\0';
                fprintf(fout, "%s\t%s\n", "NUM", Buff);
            }
        }
        else if (strchr(Sword, ch) > 0)
        {
            Buff[0] = ch;
            Buff[1] = '\0';
            ch = getc(fin);
            fprintf(fout, "%s\t%s\n", Buff, Buff);
        }
        else if (strchr(Dword, ch) > 0)
        {
            Buff[0] = ch;
            ch = getc(fin);
            if (ch == '=')
            {
                Buff[1] = ch;
                Buff[2] = '\0';
                ch = getc(fin);
                fprintf(fout, "%s\t%s\n", Buff, Buff);
            }
            else
            {
                Buff[1] = '\0';
                if (Buff[0] == '!')
                {
                    printf("Line %d\t%s\t%s\n", line, "ERROR:", Buff);
                }
                else
                {
                    fprintf(fout, "%s\t%s\n", Buff, Buff);
                }
            }
        }
        else if (ch == '/')
        {
            ch = getc(fin);
            if (ch == '*')
            {
                char ch1;
                ch1 = getc(fin);
                while (true)
                {
                    if (ch1 == EOF)
                    {
                        printf("Line %d\t%s\tNote does't match!\n", line,"ERROR:" );
                        
                        break;
                    }
                    ch = ch1;
                    ch1 = getc(fin);
                    if (ch == '*'&&ch1 == '/')
                    {
                        break;
                    }
                }
                ch = getc(fin);
            }
            else
            {
                Buff[0] = '/';
                Buff[1] = '\0';
                fprintf(fout, "%s\t%s\n", Buff, Buff);
            }
        }
        else
        {
            Buff[0] = ch;
            Buff[1] = '\0';
            ch = getc(fin);
            flag = 3;
            printf("Line %d\t%s\t%s\n", line, "ERROR:", Buff);
        }
    }
    fclose(fin);
    fclose(fout);
    return(flag);
}

void main()
{
    int flag = 0;
    flag = test();
    if (flag > 0)
    {
        printf("Compile Error\n");
    }
    else
    {
        printf("No Error\n");
    }
}