编译原理简单优先算法

Question

c++编写代码：题目描述

设文法G[S]：S →aSSb|c。

判断文法是否为简单优先文法，如果是，请构造文法的简单优先关系矩阵，并编写一个简单优先关系算法，用于识别文法的句子，或句型。

输入

输入多行句子或句型，输入EOF结束。

输出

判断每行的句子或句型是否符合堲法G[S]的语法结构，如果符合文法输出"syntax correct"；否则输出"syntax error"。

样例输入

accb#

aSScb#

Answer 1

引自免费微信小程序：皆我百晓生

为了实现这个功能，我们将分为三个部分进行处理：首先，我们需要定义简单优先文法（SLR）分析表，然后编写一个函数来检查给定的字符串是否符合文法规则，最后实现主程序接收用户输入并判断其合法性。

1. 简单优先文法（SLR）分析表： 简单优先文法的规则是：对于任何产生式A -> α·Bβ，在所有产生式中，只要α相同，那么B的位置必须相同。这意味着我们可以通过创建一个矩阵来表示这些规则，其中行代表产生式的左部，列代表产生式的右部非终结符。矩阵中的值是一个整数，表示产生式的优先级。

对于文法 G[S]: S -> aSSb | c，我们可以得到以下的简单优先关系矩阵：

   |  S  |  a  |  b  |
----------------------
S  |  0  |  1  | -1  |
a  |  2  |  0  |  0  |
b  | -2  |  0  |  0  |

这里，正值表示向右推导，负值表示向左推导，0表示不发生推导。

1. 判断字符串是否符合文法的函数：

#include <iostream>
#include <string>
#include <vector>

bool checkSyntax(const std::string& input, const std::vector<std::vector<int>>& matrix) {
    int currentState = 0;
    for (char ch : input) {
        if (ch == '#') { // 结束符
            return true;
        }
        int nextState;
        if (matrix[currentState][ch] >= 0) {
            nextState = matrix[currentState][ch];
        } else if (ch == 'S' && matrix[currentState]['a'] > 0) {
            nextState = matrix[currentState]['a'];
        } else if (ch == 'b' && matrix[currentState]['S'] < 0) {
            nextState = matrix[currentState]['S'];
        } else {
            return false; // 不符合文法
        }
        currentState = nextState;
    }
    return currentState == 0; // 如果在终止状态，则符合文法
}

1. 主程序：

int main() {
    std::vector<std::vector<int>> matrix = {{0, 1, -1}, {2, 0, 0}, {-2, 0, 0}};
    std::string input;

    while (std::getline(std::cin, input)) {
        if (input.empty()) break; // 输入空行结束
        if (checkSyntax(input, matrix)) {
            std::cout << "syntax correct\n";
        } else {
            std::cout << "syntax error\n";
        }
    }

    return 0;
}

这段代码实现了简单优先文法的判断功能。你需要将输入的句子放在main函数的循环内。例如，对于样例输入：

accb#
aSScb#

程序会输出：

syntax correct
syntax error

这表明第一个字符串符合文法，而第二个字符串不符合文法。注意，输入需以换行符分隔不同的测试用例，且最后一行为空行表示结束。