递归下降解析

Question

我正在寻找有关我的作业的一些建议/帮助。由于这是一门课程，我并不要求任何人从字面上为我写出答案，但我确实需要帮助进行实际编码。

问题：

考虑以下 BNF 语法：

<前><代码>A -> I=EE->时间 + 时间 | T - E | TT-> F * T |时间/时间 | FF-> P ^ F | PP->我|左 | （五） 我->一个 |乙| ... | y | z L-> 0 | 1 | ... | 8 | 9

使用课堂上描述的技术实现递归下降 识别该语言中的字符串的解析器。输入应该来自 一个名为 input.dat 的文件，输出应该到控制台。一个 示例会话可能如下所示：

从文件中读取的字符串：a=a+bc*d 字符串“a=a+bc*d”位于 语言。从文件读取的字符串：a=a**b++c 字符串 “a=a**b++c”不在该语言中。

您必须使用 Java 和 C++ 实现该项目！实施 不包含两种语言的解决方案充其量， 获得一半学分。为了简化你不必处理的事情 解析字符串时的空格，即“”和类似的 该语言中的非法字符。

具有不同语法的正确相关示例：

// * <分配> =>  = <表达式>;
// * ; =>一个 |乙| c
// * <表达式>; => <点亮> + <点亮> | <点亮> - <点亮>
// * <点燃>; => 0 | ... | 9 | (<表达式>)

#include ;

使用 std::cout；
使用 std::endl；

布尔分配（无效）；
布尔 ID（无效）；
布尔表达式（无效）；
布尔点亮（无效）；

字符*c；

int main(int argc, char *argv[]) {

    c = argc == 2 ？ argv[1] : (char *)"";

    if (分配() && *c == '\0') {
        计算<< “字符串 \”“ << argv[1] << “\” 位于该语言中。” <<结束；
    }
    别的 {
        计算<< “字符串 \”” << argv[1] << “\” 不在该语言中。” <<结束；
    }

    返回0；
}

布尔分配（无效）{

    如果（id（））{
        如果（*c == '='）{
            ++c；
            如果 (expr()) {
                返回真；
            }
        }
    }

    返回假；
}

布尔 ID（无效）{

    if (*c >= 'a' && *c <= 'c') {
        ++c；
        返回真；
    }

    返回假；
}

布尔表达式（无效）{

    如果（点燃（））{
        if (*c == '+' || *c == '-') {
            ++c；
            如果（点燃（））{
                返回真；
            }
        }
    }

    返回假；
}

布尔点燃（无效）{

    if (*c >= '0' && *c <= '9') {
        ++c；
        返回真；
    }
    别的 {
        如果 (*c == '(') {
            ++c；
            如果 (expr()) {
                如果 (*c == ')') {
                    ++c；
                    返回真；
                }
            }
        }
    }

    返回假；
}

到目前为止我的实际工作：（我暂时省略了 txt 文件的阅读，希望首先让语法工作） edit1：问题是没有一个字符串显示为该语言中的有效字符串。不幸的是，即使像 a=b 这样的简单字符串也必须遍历几乎所有的生产规则，所以我无法指出哪里出错了

//A -> I = E 
//E -> T + E | T - E | T 
//T -> F * T | F / T | F 
//F -> P ^ F | P 
//P -> I | L | (E) 
//I -> a | b | ... | y | z 
//L -> 0 | 1 | ... | 8 | 9 

#include <iostream>

using namespace std;

bool A(void);
bool E(void);
bool T(void);
bool F(void);
bool P(void);
bool I(void);
bool L(void);

char *c;

int main(int argc, char *argv[]){

     c = argc == 2 ? argv[1] : (char *)"";

    if (A() && *c == '\0') {
        cout << "The string \"" << argv[1] << "\" is in the language." << endl;
    }
    else {
        cout << "The string \"" << argv[1] << "\" is not in the language." << endl;
    }

    return 0;
}

bool A(void){

    if( I() )
    {
        if ( *c == '=' ){
            ++c;
            if ( E() )
            return true;
        }
    }

    return false;
}

bool E(void){

    if( T() ){
        if ( *c == '+' || *c == '-' ){
                ++c;
                if ( E() )
                return true;
        }
    }
    else
    if ( T() ){
        ++c;
        return true;
    }

    return false;
}

bool F(void){

    if( P() ){
        if( *c == '^')
        ++c;
        if( F() )
        return true;
    }
    else
    if ( P() ){
        ++c;
        return true;
    }

    return false;

}

bool I(void){

    if ( *c >= 'a' && *c <= 'z'){
        ++c;
        return true;
    }

    return false;

}

bool L(void){

    if ( *c >= '0' && *c <= '9' ){
    ++c;
    return true;
    }

    return false;
}

bool P(void){

    if ( I() ){
        ++c;
        return true;
    }
    else
    if ( L() ){
        ++c;
        return true;
    }
    else
    if ( *c == '(' ){
            ++c;
            if ( E() ){
                    if ( *c == ')' ){
                        ++c;
                        return true;
                    }
            }
    }

    return false;
}

bool T(void){

    if( F() ){
        if ( *c == '*' || *c == '/' ){
                ++c;
                if ( T() )
                return true;
        }
    }
    else
    if ( F() ){
        ++c;
        return true;
    }

    return false;
}

Answer 1

遇到的普遍问题

E = T + E | T - E | T

我认为您在检测诸如当您查找 T() 时 ，但您尝试再次查找 T() 失败。
您在大多数其他函数中也犯过这个错误。

E() 的正确实现是（在 Chris 评论后更新）：

if (T())
{
   if (c == '+' || c == '-')
   {  
      ++c;
      return E();
   }
   return true;
}
return false;

让我们练习一个示例：“a=(3)”

A()-> I() 返回 true -> c == '=' -> E() ->在调用 P() 后解析 3 时，T() 返回 true，最终调用 E()再次->现在 c == ')' 所以我们需要在 E() 中返回 true，否则如果我们在这里返回 false，解析将在 P() 中停止code>

我希望它不会太混乱，但这里很难表达。最好的方法是在一张纸上写下解析树以使其可视化。

再次更新：您在T()和F()中也有类似的情况