实验1  词法分析

1. 1. 实验目的

（1）理解有穷自动机及其应用。

（2）掌握 NFA 到 DFA 的等价变换方法、DFA 最小化的方法。

（3）掌握设计、编码、调试词法分析程序的技术和方法。

1.2 实验任务

编写一个 PL/0 词法分析程序，使用java语言。

1.3实验内容

1）算法描述：

1. 读取指定文件路径的文本文件。
2. 逐行分析文件内容。
3. 对每行内容进行词法分析。
4. 根据词法规则判断每个词法单元的类型，如关键字、标识符、常数等。
5. 输出词法单元的类型和对应的内容。
6. 若某个词法单元不符合任何词法规则，则输出错误信息。

2）程序结构

1. 主函数 main()：程序的入口，负责读取指定文件并逐行调用 analyzeLine() 进行词法分析。
2. 函数 analyzeLine()：对每行内容进行词法分析。将每行内容按照空格分割成词法单元，并逐个判断其类型。
3. 函数 isKeyword()：判断一个词法单元是否为关键字。
4. 函数 isIdentifier()：判断一个词法单元是否为标识符。
5. 函数 isNumber()：判断一个词法单元是否为数字。

3）主要变量说明：

1. filePath：指定的文本文件路径。
2. line：当前读取的行内容。
3. lineNumber：当前行号。
4. tokens：根据空格分割后的词法单元数组。
5. keywords：关键字数组，用于判断词法单元是否为关键字。

4）程序

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

public class LexicalAnalyzer1 {

    public static void main(String[] args) {

        String filePath = "C:\\Users\\dell\\Desktop\\input.txt"; // 请将 "YourUserName" 替换为您的计算机用户名

        try (BufferedReader reader = new BufferedReader(new FileReader(filePath))) {

            String line;

            int lineNumber = 1;

            while ((line = reader.readLine()) != null) {

                analyzeLine(line, lineNumber);

                lineNumber++;

            }

        }

        catch (IOException e) {

            System.out.println("文件读取失败");

            e.printStackTrace();

        }

    }

    private static void analyzeLine(String line, int lineNumber) {

        String[] tokens = line.split("\\s+");

        for (String token : tokens) {

            if (token.isEmpty()) {

                continue;

            }

            if (isKeyword(token)) {

                System.out.println("关键字: " + token);

            }

            else if (isIdentifier(token)) {

                System.out.println("标识符: " + token);

            }

            else if (isNumber(token)) {

                System.out.println("常数: " + token);

            }

            else {

                System.out.println("错误词法: " + token + " (第 " + lineNumber + " 行)");

            }

        }

    }

    private static boolean isKeyword(String token) {

        String[] keywords = { "const", "var", "main","procedure", "begin", "end", "if", "then", "else", "while", "do", "call", "read", "write", "int", "char", "bool", "float", "double", "long", "short", "unsigned", "signed", "void", "return" };

        for (String keyword : keywords) {

            if (keyword.equals(token)) {

                return true;

            }

        }

        return false;

    }

    private static boolean isIdentifier(String token) {

        return token.matches("[a-zA-Z{}\\(\\)=;][a-zA-Z0-9{}\\(\\)=;]*");

    }

    private static boolean isNumber(String token) {

        return token.matches("[0-9]+");

    }

}

1. 调试情况

能够正常运行

6）程序截图

1.4心得体会

通过编写这段词法分析器的代码，我加深了对词法分析的理解，掌握了字符串处理和正则表达式的应用技巧。

1.5 参考资料

清华大学课本LR（0）文法知识

csdn博主杨戬的博客

  

实验2  自顶向下的语法分析程序

2.1 实验目的

（1）熟练掌握 LL(1)分析表的构造方法。

（2）掌握设计、编制和调试典型的语法分析程序，进一步掌握常用的语法分析方法

2.2 实验任务

根据 LL(1)分析法自己编写一个语法分析程序，使用c++语言。

2.3 实验内容

1）算法描述：实现了一个基于LL(1)文法的语法分析器。它通过输入一个字符串，使用LL(1)文法规则对字符串进行分析，判断输入的字符串是否符合给定文法的规则。

2）程序结构：

在主函数中，首先输出提示信息，然后读取输入的字符串。

调用analyze函数进行语法分析，传入输入的字符串和字符串长度。在analyze函数中，使用循环进行语法分析的过程：初始化计数器cnt和分析位置i，以及栈cmp。定义一个字符数组p，用于存储分析过程中的产生式。输出分析过程的表头信息。在循环中，首先获取栈顶符号ch。如果ch是非终结符，则根据LL1文法规则查找产生式，并进行相应的处理。

如果分析过程正常结束，即字符串被接受，输出接受信息。

3）主要变量说明

LL1：二维字符串数组，存储了LL(1)文法的产生式规则。

H：字符串常量，表示非终结符的集合。

L：字符串常量，表示终结符的集合。

cmp：栈，用于存储分析过程中的符号。

str：字符数组，存储输入的字符串。

len：整数，表示输入字符串的长度。

p：字符数组，用于存储分析过程中的产生式。

pindex：整数，表示字符数组p的索引位置。

4）程序内容：

#include <iostream>

#include <cstring>

#include <stack>

using namespace std;

const string LL1[5][6] = {

    { "->AT", "->AT", "null", "null", "null", "null"},

    { "->BU", "->BU", "null", "null", "null", "null"},

    { "null", "null", "->$", "->+AT", "null", "->$"},

    { "null", "null", "->$", "->$", "->*BU", "->$"},

    { "->m", "->(S)", "null", "null", "null", "null"}

};

const string H = "SATUB";

const string L = "m()+*#";

stack<char> cmp;

int findH(char a) {

    size_t pos = H.find(a);

    if (pos != string::npos) {

        return static_cast<int>(pos);

    }

    return -1;

}

int findL(char a) {

    size_t pos = L.find(a);

    if (pos != string::npos) {

        return static_cast<int>(pos);

    }

    return -1;

}

int error(int i, int cnt, int len, const char p[], const char str[]) {

    cout << cnt << '\t' << p << '\t';

    for (int q = i; q < len; q++) {

        cout << str[q];

    }

    cout << "\t报错" << endl;

    return len;

}

void analyze(const char str[], int len) {

    int cnt = 1;

    int i = 0;

    stack<char> cmp;

    cmp.push('#');

    cmp.push('S');

    char p[2000] = "#S";

    int pindex = 2;

    cout << "Step\tStack\tString\tRule" << endl;

    while (i < len) {

        char ch = cmp.top();

        if (ch >= 'A' && ch <= 'Z') {

            cmp.pop();

            int x = findH(ch);

            int y = findL(str[i]);

            if (x != -1 && y != -1) {

                string rule = LL1[x][y];

                if (rule == "null") {

                    i = error(i, cnt, len, p, str);

                    continue;

                }

                cout << cnt << '\t' << p << '\t';

                if (p[pindex - 1] != '#') {

                    p[pindex] = '\0';

                    pindex--;

                }

                if (rule[2] != '$') {

                    for (int q = static_cast<int>(rule.length()) - 1; q > 1; q--) {

                        p[pindex++] = rule[q];

                        cmp.push(rule[q]);

                    }

                }

                else {

                    pindex--;

                }

                for (int q = i; q < len; q++) {

                    cout << str[q];

                }

                cout << '\t' << ch << rule << endl;

            }

            else {

                i = error(i, cnt, len, p, str);

                continue;

            }

        }

        else {

            if (ch == str[i]) {

                cmp.pop();

                cout << cnt << '\t' << p << '\t';

                if (ch == '#' && str[i] == '#') {

                    cout << "#\t接受" << endl;

                    return;

                }

                for (int q = i; q < len; q++) {

                    cout << str[q];

                }

                cout << '\t' << ch << "匹配" << endl;

                pindex--;

                i++;

            }

            else {

                i = error(i, cnt, len, p, str);

                continue;

            }

        }

        cnt++;

    }

}

int main() {

    cout << "请输入一个字符串" << endl;

    char str[200];

    cin >> str;

    int len = strlen(str);

    cmp.push('#');

    cmp.push('S');

    analyze(str, len + 1);

    return 0;

}

5）调试情况：

运行一切正常

6）运行截图：

2.4 心得体会

通过分析该代码，我对LL(1)语法分析的原理和实现有了更深入的理解。这样的语法分析器在编译器和解释器等领域有广泛的应用，能够帮助我们验证和分析输入的程序是否符合给定的文法规则，从而提高程序的正确性和可靠性。

2.5 参考资料

清华大学课本LL(1)文法知识

csdn博主杨戬的博客

  

实验3基于 LR(0)方法的语法分

3.1 实验目的

（1）掌握 LR(0)分析表的构造方法。

（2）掌握设计、编制和调试典型的语法分析程序，进一步掌握常用的语法分析方法。

（3）理解语法分析在编译程序中的作用

3.2 实验任务

自己编写一个基于 LR(0)方法的语法分析程序。语言不限，文法不限。 此时可根据自己的实际情况，选择以下一项实现分析算法中分析表的构造： （1）直接输入根据已知文法构造的 LR(0)分析表；

（2）输入已知文法的项目集规范族和转换函数，由程序自动生成 LR(0)分析表；

（3）输入已知文法，由程序自动生成 LR(0)分析表

3.3 实验内容

1）算法描述

读入一个带有结束符#的输入串。使用LR(0)分析表进行分析，根据当前状态和输入符号进行查表操作，得到相应的动作。如果是移入动作，则将输入符号移入符号栈和输入串，并切换到下一个状态。如果是规约动作，则根据产生式将符号栈中的符号规约为非终结符，并进行状态转换。如果是接受动作，则分析成功，结束分析过程。如果在查表过程中遇到空白或错误情况，则报错。

2）程序结构

1.程序主要包含一个analyze函数和主函数main。

2.analyze函数用于进行LR(0)语法分析，根据输入串和LR(0)分析表进行分析过程，并输出每一步的状态栈、符号栈、输入串、动作和转移状态。

3.主函数main中首先定义了LR(0)分析表LR0、输入符号集合L、产生式头部集合head以及其他辅助变量。

4.然后通过输入字符串，调用analyze函数进行LR(0)语法分析。

3）主要变量说明

1. LR0: LR(0)分析表，存储了每个状态和输入符号所对应的动作或转移状态。
2. L: 输入符号集合，用于确定输入符号在LR(0)分析表中的列索引。
3. head: 产生式头部集合，用于进行规约操作时确定规约的产生式。
4. del: 每个产生式的长度，用于进行规约操作时弹出对应数量的符号。
5. cnt: 步骤计数器，用于输出分析过程的步骤数。
6. LR: 输入串的当前位置，用于指示下一个待处理的输入符号。
7. cindex: 输出数组cod的当前索引，用于记录输出结果。
8. sindex: 符号栈sti的当前索引，用于记录符号栈的内容。
9. cod: 输出数组，用于存储每一步的状态栈和符号栈的内容。
10. sti: 符号栈，用于存储当前的符号栈内容。
11. now: 状态栈，用于存储状态的栈结构。
12. cmp: 符号栈，用于存储符号的栈结构。

4）程序

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <stack>

using namespace std;

///表格数组      a       b        c       d       #      E      A       B

char LR0[50][50][100] = {

{"S2", "S3", "", "", "", "1", "", ""},

{"", "", "", "", "acc", "", "", ""},

{"", "", "S4", "S10", "", "", "6", ""},

{"", "", "S5", "S11", "", "", "", "7"},

{"", "", "S4", "S10", "", "", "8", ""},

{"", "", "S5", "S11", "", "", "", "9"},

{"r1", "r1", "r1", "r1", "r1", "", "", ""},

{"r2", "r2", "r2", "r2", "r2", "", "", ""},

{"r3", "r3", "r3", "r3", "r3", "", "", ""},

{"r5", "r5", "r5", "r5", "r5", "", "", ""},

{"r4", "r4", "r4", "r4", "r4", "", "", ""},

{"r6", "r6", "r6", "r6", "r6", "", "", ""}

};

char L[200] = "abcd#EAB",  head[20] = { 'S', 'E', 'E', 'A', 'A', 'B', 'B' };   ///列判断依据

int del[10] = { 0, 2, 2, 2, 1, 2, 1 }; //0-6号文法每个文法长

int cnt = 1, LR = 0, cindex = 0, sindex = 0;

char cod[300] = "0",  sti[300] = "#"; ///初始符号栈对应输出数组

stack<int> now;      ///状态栈

stack<char> cmp;     ///符号栈

void error(int x, int y) ///报错输出

{

cout << "error:第" << x << "行" << L[y] << "列为空!" << endl;

}

int find(char a) ///对应列寻找

{

int i = 0;

while(i<=7){

if (a == L[i])

{

return i;

}

i++;

}

return -1;

}

int cal(int l, char s[])

{

int num = 0,i=1;

while (i < l) {

num = num * 10 + (s[i] - '0');

i++;

}

return num;

}

void analyze(char str[], int len) ///分析主体过程

{

cout<<"步骤      状态栈    符号栈    输入串    ACTION    GOTO"<<endl;

for(;LR <= len;)

{

printf("(%d)       %-10s%-10s", cnt, cod, sti); ///步骤，状态栈，符号栈输出

cnt++;

for (int i = LR; i < len; i++) ///输入串输出

{

cout<<str[i];

}

for (int i = len - LR; i < 10; i++)

cout<<" ";

int x = now.top();      ///状态栈栈顶

int y = find(str[LR]); ///待判断串串首

if (strcmp(LR0[x][y], "null") != 0)

{

int l = strlen(LR0[x][y]); ///当前Ri或Si的长度

if (LR0[x][y][0] == 'S') ///Si  

{

int t = cal(l, LR0[x][y]); ///整数  

printf("%-10s \n", LR0[x][y]);   ///ACTION与GOTO  

now.push(t);

sindex++;

sti[sindex] = str[LR];

cmp.push(str[LR]);

if(t>=10)

{

int k = 1;

cod[++cindex] = '(';

while (k < l)

{

cod[++cindex] = LR0[x][y][k];

k++;

if (k < l)

{

cod[++cindex] = ')';}

}

}

else

{

cod[++cindex] = LR0[x][y][1];

}

LR++;

}

else if (LR0[x][y][0] == 'r') ///ri,退栈，ACTION和GOTO

{

printf("%-10s", LR0[x][y]);

int t = cal(l, LR0[x][y]);

int g = del[t];

while (g--)

{

now.pop();

cmp.pop();

sti[sindex] = '\0';

sindex--;

}

g = del[t];

while (g > 0)

{

if (cod[cindex] == ')')

{

cod[cindex--] = '\0';

for (;;)

{

cod[cindex--] = '\0';

if (cod[cindex] == '(')

{

break;

}

}

}

else

{

cod[cindex--] = '\0';

}

g--;

}

cmp.push(head[t]);

sindex++;

sti[sindex] = head[t];

x = now.top();

y = find(cmp.top());

t = LR0[x][y][0] - '0';

now.push(t);

cindex++;

cod[cindex] = LR0[x][y][0];

cout << t << endl;

}

else if (LR0[x][y][0] == 'a')   ///acc

{

cout << "acc        \n"; ///ACTION与GOTO

return;

}

else

{

int t = LR0[x][y][0] - '0';

char ch = ' ';

printf("%-10c%-10d\n", ch, t);

now.push(t);

cod[cindex++] = LR0[x][y][0];

LR++;

}

}

else

{

error(x, y);

return; ///报错

}

}

}

void chart() ///测试表函数

{

printf("-\ta\tb\tc\td\t#\tE\tA\tB\n");

for (int i = 0; i <= 11; i++)

{

printf("%d", i);

for (int j = 0; j <= 8; j++)

printf("\t%s", LR0[i][j]);

cout << endl;

}

cout << endl;

}

int main()

{

chart();

now.push(0);

cmp.push('#');

char str[200]; ///输入串

cout << "请输入字符串（带#）：" << endl;

cin >> str;

int len = strlen(str);

analyze(str, len);

system("pause");

return 0;

}

5）调试情况：

一切调试正常

6）运行截图：

3.4 心得体会

编写LR(0)分析器的代码需要对LR(0)分析表和分析过程有深入的理解，并且需要仔细处理产生式、状态栈、符号栈和输入串的操作。通过编写这段代码，我加深了对LR(0)语法分析的理解，并提高了对语法分析算法的实现能力。

3.5 参考资料

清华大学课本LR（0）文法知识

csdn博主杨戬的博客

实验4  语义分析和中间代码生成

4.1 实验目的

（1）熟悉语义分析和中间代码生成过程。

（2）加深对语义翻译的理解

4.2 实验任务

在词法分析、语法分析和语义分析程序的基础上，将输入源代码翻译成中间代码。编写一个中间代码生成程序，能将算术表达式等翻译成逆波兰形式.

4.3 实验内容

1）算法描述

1. 输入一个中缀表达式。
2. 首先检查表达式的语法是否正确，主要检查括号是否匹配。
3. 将中缀表达式转换为逆波兰表达式（后缀表达式）。
4. 使用逆波兰表达式计算器对逆波兰表达式进行求值，得到计算结果。

2）程序结构

1. 主函数 main()：程序的入口，负责读取用户输入的中缀表达式，并进行语法检查、转换和计算。
2. 函数 isOperator()：判断一个字符是否为运算符。
3. 函数 isDigit()：判断一个字符是否为数字。
4. 函数 calculate()：逆波兰表达式计算器，对逆波兰表达式进行求值。
5. 函数 getPrecedence()：获取运算符的优先级。
6. 函数 convertToRPN()：将中缀表达式转换为逆波兰表达式。
7. 函数 isValidExpression()：检查中缀表达式的语法是否正确。

3）主要变量说明

1. ch：当前读取的字符。
2. top：运算符栈顶指针。
3. length：中缀表达式的长度。
4. t：逆波兰表达式的长度。
5. ex[100]：逆波兰表达式存储数组。
6. str[100]：中缀表达式存储数组。
7. stack[100]：运算符栈。

4）程序

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

char ch;

int top, length, t;

char ex[100];

char str[100];

bool isOperator(char c)

{

    if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^') {

        return true;

    }

    else {

        return false;

    }

}

bool isDigit(char c)

{

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

        return true;

    }

    else {

        return false;

    }

}

double calculate()

{

    double stack[100];

    int top = -1;

    int t = 0;

    int length = strlen(ex);

    while (t < length)

    {

        char ch = ex[t];

        if (isOperator(ch))

        {

            if (top < 1)

            {

                printf("\n\t表达式错误！\n");

                return 0.0; // Return 0 for expression error

            }

            double operand2 = stack[top];

            top--;

            double operand1 = stack[top];

            double result; // Move the declaration here

            switch (ch)

            {

            case '+':

                result = operand1 + operand2;

                break;

            case '-':

                result = operand1 - operand2;

                break;

            case '*':

                result = operand1 * operand2;

                break;

            case '/':

                if (operand2 != 0)

                    result = operand1 / operand2;

                else

                {

                    printf("\n\t除零错误！\n");

                    return 0.0; // Return 0 for division by zero error

                }

                break;

            case '^':

                result = 1.0;

                for (int i = 0; i < operand2; i++)

                {

                    result *= operand1;

                }

                break;

            default:

                printf("\n\t运算符错误！\n");

                return 0.0; // Return 0 for invalid operator error

            }

            top++;

            stack[top] = result;

            t++;

        }

        else if (isDigit(ch) || ch == '-')

        {

            // Remaining code remains the same

        }

        else

        {

            t++; // Skip unknown characters

        }

    }

    if (top != 0)

    {

        printf("\n\t表达式错误！\n");

        return 0.0; // Return 0 for expression error

    }

    return stack[0];

}

int getPrecedence(char c)

{

    if (c == '^')

        return 3;

    if (c == '*' || c == '/')

        return 2;

    if (c == '+' || c == '-')

        return 1;

    return 0;

}

void convertToRPN()

{

    char stack[100];

    top = -1;

    t = 0;

    for (int i = 0; i < length;)

    {

        ch = str[i];

        if (isDigit(ch))

        {

            while (ch == '@' || isDigit(ch) || ch == '.')

            {

                ex[t] = ch;

                t++;

                i++;

                ch = str[i];

            }

            ex[t] = '&';

            t++;

        }

        else if (isOperator(ch))

        {

            while (top >= 0 && stack[top] != '(' && getPrecedence(stack[top]) >= getPrecedence(ch))

            {

                ex[t] = stack[top];

                top--;

                t++;

            }

            top++;

            stack[top] = ch;

            i++;

        }

        else if (ch == '(')

        {

            top++;

            stack[top] = ch;

            i++;

        }

        else if (ch == ')')

        {

            while (top >= 0 && stack[top] != '(')

            {

                ex[t] = stack[top];

                top--;

                t++;

            }

            if (top >= 0 && stack[top] == '(')

                top--;

            i++;

        }

        else

        {

            i++;

        }

    }

    while (top >= 0)

    {

        ex[t] = stack[top];

        t++;

        top--;

    }

    ex[t] = '\0';

}

bool isValidExpression()

{

    int parenthesesCount = 0;

    for (int i = 0; i < length; i++)

    {

        if (str[i] == '(')

        {

            parenthesesCount++;

        }

        else if (str[i] == ')')

        {

            parenthesesCount--;

            if (parenthesesCount < 0)

            {

                return false;

            }

        }

    }

    return (parenthesesCount == 0);

}

int main()

{

    char stack[100];

    memset(stack, 0, sizeof(stack));

    length = 0;

    while (true)

    {

        cin >> ch;

        if (ch == '#')

        {

            break;

        }

        str[length++] = ch;

    }

    str[length] = '\0';

    printf("原式：%s\n", str);

    if (!isValidExpression())

    {

        printf("语法错误！\n");

        return 0;

    }

    convertToRPN();

    printf("逆波兰：%s\n", ex);

    length = t;

    printf("得出：%f\n", calculate());

    return 0;

5）调试情况

调试一切正常

6）运行截图

4.4 心得体会

我对逆波兰表达式的转换和计算有了更深入的理解，同时也加强了对栈这种数据结构的应用。

4.5 参考资料

清华大学课本语义分析知识

csdn博主杨戬的博客