语法分析 | LIU-ADFPGA

26 May 2020 4875字 17分次编译原理
如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）

文法推导

Time Limit: 1sec Memory Limit: 256MB

Description

E\to TE' \\ E'\to +TE' \vert \epsilon \\ T\to FT' \\ T'\to *FT' \vert \epsilon \\ F\to (E) \vert \mathbf{id}

依据教材第 4.4 节文法 4.28，将其中的 id 替换为 0 到 9 的数字，对于输入的字符串，输出其最左推导的过程。如果输入的字符串不符合文法的定义，则输出”Syntax Error”。

Input

有多组测试数据，每组数据一行，包含一个字符串，字符串只包含有文法中的终端符号。字符串长度不超过 100。

输入以#号结束。

Output

对于每组数据，如果输入字符串符合文法的定义，输出其最左推导的过程，每步推导占一行；否则，输出“Syntax Error”。每组数据输出结束后再输出一个空行。

Sample Input

3+5*0
1*2*
#

Sample Output

E
TE'
FT'E'
3T'E'
3E'
3+TE'
3+FT'E'
3+5T'E'
3+5*FT'E'
3+5*0T'E'
3+5*0E'
3+5*0

Syntax Error

Solution

因为看漏了文法中的括号，导致无限 WA、RE、TLE…老年人该看看眼睛了。

#include <bits/stdc++.h>
#define SE "Syntax Error\n"
using namespace std;
struct Rule
{
    char prefix, eps, id;
    string lc, rc;
};
string work(const char *b, const char *e, string r)
{
    static map<string, Rule> mp{
        {"E", {0, 0, 0, "T", "E'"}},
        {"E'", {'+', 1, 0, "T", "E'"}},
        {"T", {0, 0, 0, "F", "T'"}},
        {"T'", {'*', 1, 0, "F", "T'"}},
        {"F", {0, 0, 1, "E", "E"}}};
    if (mp[r].id)
    {
        if (e - b == 1 && isdigit(*b))
            return r + "\n" + string(1, *b) + "\n";
        if (e - b < 2 || *b != '(' || *(e - 1) != ')')
            return SE;
        string s = work(b + 1, e - 1, mp[r].lc);
        if (s == SE)
            return SE;
        string ans = r + "\n";
        for (int p = 0, q = 0; q < s.size(); ++q)
            if (s[q] == '\n')
            {
                ans += "(" + s.substr(p, q - p) + ")\n";
                p = q + 1;
            }
        return ans;
    }
    if (e - b == 0 && mp[r].eps)
        return r + "\n\n";
    if (e - b == 0 && mp[r].prefix)
        return SE;
    if (e - b && mp[r].prefix && mp[r].prefix != *b)
        return SE;
    for (int i = (mp[r].prefix ? 1 : 0); i <= e - b; ++i)
    {
        string lc = work(mp[r].prefix ? b + 1 : b, b + i, mp[r].lc);
        if (lc == SE)
            continue;
        string rc = work(b + i, e, mp[r].rc);
        if (rc == SE)
            continue;
        string ans = (mp[r].prefix ? string(1, mp[r].prefix) : "") + r + "\n", last;
        for (int p = 0, q = 0; q < lc.size(); ++q)
            if (lc[q] == '\n')
            {
                last = (mp[r].prefix ? string(1, mp[r].prefix) : "") + lc.substr(p, q - p);
                ans += last + mp[r].rc + "\n";
                p = q + 1;
            }
        for (int p = 0, q = 0, first = 0; q < rc.size(); ++q)
            if (rc[q] == '\n')
            {
                if (first)
                    ans += last + rc.substr(p, q - p) + "\n";
                else
                    first = 1;
                p = q + 1;
            }
        return ans;
    }
    return SE;
}
int main()
{
    for (char s[127]; scanf("%s", s) != EOF && strcmp("#", s);)
        cout << work(s, s + strlen(s), "E") << "\n";
}

中缀转后缀

Time Limit: 1sec Memory Limit: 256MB

Description

输入一个中缀算术表达式 S，S 中的操作数为 0 到 9，只含+，-和*，/运算，也可能含有括号()，运算符的计算顺序和实际四则运算的计算顺序相同. 请输出与 S 等价的后缀表达式，注意输出结果不要含有多余的括号或空格.

Input

输入有多组数据.

每组数据是一个中缀表达式 S，S 的长度不超过 50. 输入的 S 保证合法，而且不包含多余的空格或制表符.

输入以#号结束.

Output

对于每个中缀表达式，输出转换后的后缀表达式，每个输出占一行.

Sample Input

1
1+2*3
(1-2)/3
#

Sample Output

1
123*+
12-3/

Solution

#include <bits/stdc++.h>
using namespace std;
vector<string> s_to_infix(const string &s)
{
	vector<string> ans;
	for (int i = 0; i < s.size(); ++i)
	{
		ans.push_back("");
		if (isdigit(s[i]))
		{
			for (; i < s.size() && isdigit(s[i]); ++i)
				ans.back() += s[i];
			--i;
			continue;
		}
		ans.back() += s[i];
	}
	return ans;
}
vector<string> infix_to_suffix(const vector<string> &v)
{
	vector<string> ans, op;
	for (auto &s : v)
	{
		if (isdigit(s.back()))
			ans.push_back(s);
		else if (op.empty() || s == "(")
			op.push_back(s);
		else if (s == ")")
		{
			for (; op.back() != "("; op.pop_back())
				ans.push_back(op.back());
			op.pop_back();
		}
		else
		{
			for (; !op.empty() && op.back() != "(" && (op.back() != "+" && op.back() != "-" || s != "*" && s != "/"); op.pop_back())
				ans.push_back(op.back());
			op.push_back(s);
		}
	}
	ans.insert(ans.end(), op.rbegin(), op.rend());
	return ans;
}
int main()
{
	for (string s; cin >> s && s != "#"; cout << "\n")
		for (auto &t : infix_to_suffix(s_to_infix(s)))
			cout << t;
}

表达式求值

Time Limit: 1sec Memory Limit: 256MB

Description

输入中缀算术表达式 S，S 中的操作数为非负整数，只含+，-和*，/运算，也可能含有括号()，运算符的计算顺序和实际四则运算的计算顺序相同. 输出表达式 S 的值. 注意除法运算只取整数部分，例如 1/2=0.

Input

输入有多组数据.

每组数据是一个算术表达式 S，S 的长度不超过 100. 输入的 S 保证合法，而且不包含多余的空格或制表符. S 的操作数、中间结果和最终结果都不会超过 int 类型的范围，也不会出现除数为 0 的情况.

输入以#号结束.

Output

对于每个算术表达式 S，输出 S 的值，每个输出占一行.

Sample Input

1
478+522
(478+522)*10
1/2-1
#

Sample Output

Solution

代码复用

#include <bits/stdc++.h>
using namespace std;
vector<string> s_to_infix(const string &s)
{
	vector<string> ans;
	for (int i = 0; i < s.size(); ++i)
	{
		ans.push_back("");
		if (isdigit(s[i]))
		{
			for (; i < s.size() && isdigit(s[i]); ++i)
				ans.back() += s[i];
			--i;
			continue;
		}
		ans.back() += s[i];
	}
	return ans;
}
vector<string> infix_to_suffix(const vector<string> &v)
{
	vector<string> ans, op;
	for (auto &s : v)
	{
		if (isdigit(s.back()))
			ans.push_back(s);
		else if (op.empty() || s == "(")
			op.push_back(s);
		else if (s == ")")
		{
			for (; op.back() != "("; op.pop_back())
				ans.push_back(op.back());
			op.pop_back();
		}
		else
		{
			for (; !op.empty() && op.back() != "(" && (op.back() != "+" && op.back() != "-" || s != "*" && s != "/"); op.pop_back())
				ans.push_back(op.back());
			op.push_back(s);
		}
	}
	ans.insert(ans.end(), op.rbegin(), op.rend());
	return ans;
}
int postfix_to_int(const vector<string> &v)
{
	vector<int> stak;
	for (auto &s : v)
	{
		if (isdigit(s[0]))
		{
			stak.push_back(stoi(s));
			continue;
		}
		int b = stak.back();
		stak.pop_back();
		int a = stak.back();
		stak.back() = s == "+" ? a + b : s == "-" ? a - b : s == "*" ? a * b : a / b;
	}
	return stak.back();
}
int main()
{
	for (string s; cin >> s && s != "#";)
		cout << postfix_to_int(infix_to_suffix(s_to_infix(s))) << "\n";
}