StudyNote/山东理工大学/编译原理/编译原理.md

# 知识点

好的，我将为你系统整理这四章的全部知识点，按章节顺序分解并整合核心内容、定义、图示、流程图，并汇总例题。对于每章内容，我也会根据重点举一反三地出一些典型练习题并附上解析，帮助你理解和练习。
 我完成后会通知你查看结果。





# 编程题

## A

```c++
#include <bits/stdc++.h>
using namespace std;
string S[]={"main","if","else","for","while","int"};
void show(string s){
    if(s[0]>='0'&&s[0]<='9')
        cout << "(integer," << s << ")" << endl;
        else{
            int flag=0;
            for(int i=0;i<6;i++){
                if(s==S[i]){
                    flag=1;
                cout<<"(keyword,"<<s<<")"<<endl;
                }
            }
            if(flag==0)
            cout<<"(identifier,"<<s<<")"<<endl;
        }
}
int main()
{
    string s;
    while (cin >> s)
    {
        int len = s.length();
        string a = "";
        for (int i = 0; i < len; i++)
        {
            if (s[i] == '=' || s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '<' || s[i] == '>' || s[i] == '!')  
            {
                if (a.length())
                    show(a);
                a = "";
                if (i + 1 < len && s[i + 1] == '=')
                {
                    cout << "(operator," << s[i] << s[i + 1] << ")" << endl;
                    i++; // i+1,否则下次循环会重复判断
                }
                else
                    cout << "(operator," << s[i] << ")" << endl;
            }else if(s[i]=='('||s[i]==')'||s[i]=='{'||s[i]=='}'||s[i]==','||s[i]==';'){
                if(a.length())
                show(a);
                a="";
                cout << "(boundary," << s[i] << ")" << endl;
            }else
            a+=s[i];
        }
        if(a.length())
        show(a);
    }
}
```

两个特殊点 

- 就是分类要分好
- 通过show()函数来将a给打印出来 这样打印其他（operator||boundary）的时候能打印干净



## B

```C++
#include <bits/stdc++.h>
#include <regex>
using namespace std;
int main()
{
    string s;
    cin >> s;

    regex pattern(R"(^[+-]?((\d+\.\d+)([eE][+-]?\d+)?|(\d+)[eE][+-]?\d+)$)");
    cout << (regex_match(s, pattern) ? "YES\n" : "NO\n");
    return 0;
}
//  R"(^[\t]*[+-]?)"
// 1) 小数（两侧有数字）^[\t]* [+-]?((\d\.\d)   + 可选指数  ([eE][+-]?\d)?)
// 2) 整数 + 必须指数
// R"( ^[+-]?  ( (\d+\.\d+) ([eE][+-]?\d+)? |  (\d+)([eE][+-]?\d+) )$ )"    //^[+-]?可选正负号
    //(\d+\.\d+)任意小数
    //([eE][+-]?\d+)?可选指数
    //(\d+)任意整数
    //[eE][+-]?\d+ 必须整数

//R"(^[+-]?( (\d+\.\d+)([eE][+-]?\d+)? | (\d+)[eE][+-]?\d+ )   )"
```



## C

```c++
#include <bits/stdc++.h>
using namespace std;

struct Node {
    string s1, s2;
};

Node p[101];
int var[26];
int expression(const string& s) {
    if (s.length() >= 3 && (s[1] == '+' || s[1] == '>')) {
        int a = s[0] - 'A';
        int b = s[2] - 'A';
        if (s[1] == '+') return var[a] + var[b];
        else return var[a] > var[b];
    }
    if (s[0] == '-') return -stoi(s.substr(1));
    return stoi(s);
}
int main() {
    int n, max_line = 0;
    string s1, s2;
    memset(var, 0, sizeof(var));
    while (cin >> n) {
        cin >> s1;
        p[n].s1 = s1;
        if (s1 != "STOP") {
            cin >> s2;
            p[n].s2 = s2;
        }
        max_line = max(max_line, n);  // 记录最大行号
    }
    for (int i = 1; i <= max_line; i++) {
        if (p[i].s1.empty()) continue;
        string cmd = p[i].s1, arg = p[i].s2;
        if (cmd == "LET") {
            int idx = arg[0] - 'A';
            var[idx] = expression(arg.substr(2));
        } else if (cmd == "PRINT") {
            int idx = arg[0] - 'A';
            cout << arg[0] << "=" << var[idx] << endl;
        } else if (cmd == "GOTO") {
            i = expression(arg) - 1;
        } else if (cmd == "IF") {
            if (!expression(arg)) i++;
        } else if (cmd == "STOP") {
            break;
        }
    }
}

```



## D

```c++
#include <bits/stdc++.h>
using namespace std;
/*
    E→TG
    G→+TG | ε
    T→FS
    S→*FS | ε
    F→(E) | i
*/
void E();
void G();
void T();
void S();
void F();
int num = 0;
int idx = 0;
string s;
void E()
{
    if (s[idx] == '(' || s[idx] == 'i')
    {
        cout << num++ << " E-->TG" << endl;
        T();
        G();
    }
    else
    {
        puts("error");
        exit(0);
    }
}
void G()
{
    if (s[idx] == '+')
    {
        cout << num++ << " G-->+TG" << endl;
        idx++;
        T();
        G();
    }
    else
    {
        cout << num++ << " G-->&" << endl;
    }
}
void T()
{
    if (s[idx] == '(' || s[idx] == 'i')
    {
        cout << num++ << " T-->FS" << endl;
        F();
        S();
    }
    else
    {
        puts("error");
        exit(0);
    }
}
void S()
{ //    S→*FS | ε
    if (s[idx] == '*')
    {
        cout << num++ << " S-->*FS" << endl;
        idx++;
        F();
        S();
    }
    else
    {
        cout << num++ << " S-->&" << endl;
    }
}
void F()
{
    if (s[idx] == '(')
    {
        cout << num++ << " F-->(E)" << endl;
        idx++;
        E();
        if (s[idx] == ')')
            idx++;
        else
        {
            cout << "error" << endl;
            exit(0);
        }
    }
    else if (s[idx] == 'i')
    {
        cout << num++ << " F-->i" << endl;
        idx++;
    }
    else
    {
        puts("error");
        exit(0);
    }
}
int main()
{
    cin >> s;
    E();
    if (s[idx] == '#')
        cout << "accept" << endl;
    else
        cout << "error" << endl;
}
```

## E

```C++
#include <bits/stdc++.h>
using namespace std;
char s[100];
int c = 0;
int num = 1;
void E();
void T();
void G();
void F();
void S();
void E() // E→TG
{
    if (s[c] == 'i' || s[c] == '(')
    {
        cout << num++ << " E->TG" << endl;
        T();
        G();
    }
    else
    {
        puts("error!");
        exit(0);
    }
}
// G→+TG | ε
void G()
{
    if (s[c] == '+')
    {
        cout << num++ << " G->+TG" << endl;
        c++; // 注意这里因为一s[c]一定是+ 那么下一次判断也就是
        // T() 和G()判断的时候 就应该从s[c++]开始 所以c++
        T();
        G();
    }
    else if (s[c] == ')' || s[c] == '#')
    {
        cout << num++ << " G->^" << endl; // 只有在 FOLLOW(G) 才能走 ε
    }
    else
    {
        puts("error!");
        exit(0);
    }
}
void T() // T→FS
{
    if (s[c] == 'i' || s[c] == '(')
    {
        cout << num++ << " T->FS" << endl;
        F();
        S();
    }
    else
    {
        cout << "error!" << endl;
        exit(0);
    }
}
void S() // S→*FS | ε
{
    if (s[c] == '*')
    {
        cout << num++ << " S->*FS" << endl;
        c++;
        F();
        S();
    }
    else if (s[c] == '+' || s[c] == ')' || s[c] == '#')
    {
        cout << num++ << " S->^" << endl; // 只有在 FOLLOW(S) 才能走 ε
    }
    else
    {
        puts("error!");
        exit(0);
    }
}
void F()
{
    if (s[c] == 'i')
    {
        cout << num++ << " F->i" << endl;
        c++;
    }
    else if (s[c] == '(')
    {
        cout << num++ << " F->(E)" << endl;
        c++;
        E();
        if (s[c] == ')')
            c++;
        else
        {
            cout << "error!" << endl;
            exit(0);
        }
    }
    else
    {
        cout << "error!" << endl;
        exit(0);
    }
}
int main()
{
    cin >> s;
    E();
    if (s[c] != '#')
        cout << "error!" << endl;
    else
        cout << "acc!" << endl;
}
```