c++ - 为什么我的程序不读消除左递归文法规则？ C++

Question

它基于正则表达式编程，所以在详细介绍之前，这是我消除的左递归语法规则 -

RE -> S RE2
RE2 -> S RE2
     | EMPTY

S -> E S2
S2 -> '|' E S2
    | EMPTY

E -> F E2
E2 -> '*' E2
    | EMPTY

F -> a
   | b
   | c
   | d
   | '('RE')'

好吧，当我输入诸如 a、ab、abc、a|c、ab* 等。我的程序将无法读取超过一个字母。你知道这是怎么回事吗？

#include <iostream>
#include <string>

using namespace std;

string input;
int index;

int nextChar();
void consume();
void match();
void RE();
void RE2();
void S();
void S2();
void E();
void E2();
void F();

int nextChar()
{
    return input[index];
}

void consume()
{
    index++;
}

void match(int c)
{
    if (c == nextChar())
        consume();
    else
        throw new exception("no");
}

void RE()
{
    S();
    RE2();
}

void RE2()
{
    if (nextChar() == 'a' || nextChar() == 'b' || nextChar() == 'c' || nextChar() == 'd' || nextChar() == '|' || nextChar() == '*' || nextChar() == '(' || nextChar() == ')')
    {
        S();
        RE2();
    }
    else
        ;
}

void S()
{
    E();
    S2();
}

void S2()
{
    if (nextChar() == 'a' || nextChar() == 'b' || nextChar() == 'c' || nextChar() == 'd' || nextChar() == '|' || nextChar() == '*' || nextChar() == '(' || nextChar() == ')')
    {
        match('|');
        E();
        S2();
    }
    else
        ;
}

void E()
{
    F();
    E2();
}

void E2()
{
    if (nextChar() == 'a' || nextChar() == 'b' || nextChar() == 'c' || nextChar() == 'd' || nextChar() == '|' || nextChar() == '*' || nextChar() == '(' || nextChar() == ')')
    {
        match('*');
        E2();
    }
    else
        ;
}

void F()
{
    if (nextChar() == 'a')
    {
        match('a');
    }
    else if (nextChar() == 'b')
    {
        match('b');
    }
    else if (nextChar() == 'c')
    {
        match('c');
    }
    else if (nextChar() == 'd')
    {
        match('d');
    }
    else if (nextChar() == ('(' && ')'))
    {
        match('(');
        RE();
        match(')');
    }
}

int main()
{
    cout << "Please enter a regular expression: ";
    getline(cin, input);

    input = input + "$";
    index = 0;

    try
    {
        RE();
        match('$');

        cout << endl;
        cout << "** Yes, this input is a valid regular expression. **";
        cout << endl << endl;
    }
    catch (...)
    {
        cout << endl;
        cout << "** Sorry, this input isn't a valid regular expession. **";
        cout << endl << endl;
    }

    return 0;
}

Answer 1

我强烈建议您学习如何使用调试器。然后您可以逐行查看您的程序在做什么，甚至可以在 throw 调用上放置一个断点并查看堆栈跟踪。

在这种情况下，E2 中的 if 测试会检查大量字符，如果不是 * 则抛出错误。

if (nextChar() == 'a' || nextChar() == 'b' || nextChar() == 'c' || nextChar() == 'd' || nextChar() == '|' || nextChar() == '*' || nextChar() == '(' || nextChar() == ')')
{
    match('*');

这应该只是

if (nextChar() == '*')
{
    match('*');

您的代码中多次出现此问题。