无扫描器算术递归下降解析器未检测语法错误问题排查

问题概述 #

开发无扫描器递归下降解析器时，输入如**5这类存在语法错误的算术表达式，程序未输出任何语法错误提示，需排查BNF语法定义与代码转换环节的问题。

原BNF语法 #

<expr>   ::= <term> "\"+\"" <expr>   | 
             <term> "\"-\"" <expr>   | 
             <term>

<term>   ::= <factor> "\"*\"" <term> | 
             <factor> "\"/\"" <term> | 
             <factor>

<factor> ::= <number> <factor>   | 
             "\"(\"" <expr> "\")\""      | 
             "\"-\"" <factor>       

<number> ::= <digit> <number>    |
             <digit> 

<digit> ::= "\"0\"" | "\"1\"" | "\"2\"" | "\"3\"" | 
            "\"4\"" | "\"5\"" | "\"6\"" | "\"7\"" | 
            "\"8\"" | "\"9\""

原JavaScript实现代码 #

let input = '**5', 
    index = 0, 
    char = input[index];

function match(c) { 
    if(char === c) {
        index++;
        char = input[index];

        if(index >= input.length) {
            char = '$';
        }
    }
    else {
        throw new Exception('Syntax error.');
    }
}

function digit() {
    if(char === '0') match('0');
    else if(char === '1') match('1');
    else if(char === '2') match('2');
    else if(char === '3') match('3');
    else if(char === '4') match('4');
    else if(char === '5') match('5');
    else if(char === '6') match('6');
    else if(char === '7') match('7');
    else if(char === '8') match('8');
    else if(char === '9') match('9');
}

function number() {
    digit();
    if('0123456789'.includes(char)) {
        number();
    }
}

function factor() {
    if('0123456789'.includes(char)) {
        number();
        factor();
    }
    else if(char === '(') {
        match('(');
        expression();
        match(')');
    }
    else if(char === '-') {
        match('-');
        factor();
    }
}

function term() {
    factor();
    if(char === '*') {
        match('*');
        term();
    }
    else if(char === '/') {
        match('/');
        term();
    }
}

function expression() {
    term();
    if(char === '+') {  
        match('+');
        expression();
    }
    else if(char === '-') {
        match('-');
        expression();
    }
}

expression();

问题定位 #

1. BNF语法错误 #

<factor>的第一个产生式<number> <factor>是冗余且错误的：

• 该定义会导致无限递归风险（数字后可无限嵌套factor），且与<number>的递归定义重复；
• 不符合算术表达式语法逻辑：数字本身就是合法的factor，无需后续再拼接factor。

2. 代码逻辑缺陷 #

• factor函数无错误分支：当字符不匹配数字、(或-时，函数直接返回，未抛出错误，导致解析器错误地认为factor匹配完成，继续处理后续符号（如输入**5时，第一个*被跳过，term函数错误地匹配该符号）；
• 未检查输入完全匹配：解析完成后未验证是否处理完所有输入字符，存在残留非法字符时无法报错；
• 异常类型错误：JavaScript中不存在Exception类型，应使用Error。

修复方案 #

修正后的BNF语法 #

<expr>   ::= <term> "+" <expr> | 
             <term> "-" <expr> | 
             <term>

<term>   ::= <factor> "*" <term> | 
             <factor> "/" <term> | 
             <factor>

<factor> ::= <number> | 
             "(" <expr> ")" | 
             "-" <factor>

<number> ::= <digit> <number> |
             <digit> 

<digit> ::= "0" | "1" | "2" | "3" | 
            "4" | "5" | "6" | "7" | 
            "8" | "9"

修正后的JavaScript代码 #

let input = '**5', 
    index = 0, 
    char = input[index];

function match(c) { 
    if(char === c) {
        index++;
        char = input[index];

        if(index >= input.length) {
            char = '$';
        }
    }
    else {
        throw new Error('Syntax error.');
    }
}

function digit() {
    if('0123456789'.includes(char)) {
        match(char);
    } else {
        throw new Error('Syntax error: expected digit.');
    }
}

function number() {
    digit();
    if('0123456789'.includes(char)) {
        number();
    }
}

function factor() {
    if('0123456789'.includes(char)) {
        number();
    }
    else if(char === '(') {
        match('(');
        expression();
        match(')');
    }
    else if(char === '-') {
        match('-');
        factor();
    }
    else {
        throw new Error('Syntax error: expected factor (number, "(", or "-").');
    }
}

function term() {
    factor();
    if(char === '*') {
        match('*');
        term();
    }
    else if(char === '/') {
        match('/');
        term();
    }
}

function expression() {
    term();
    if(char === '+') {  
        match('+');
        expression();
    }
    else if(char === '-') {
        match('-');
        expression();
    }
}

try {
    expression();
    // 检查是否处理完所有输入字符
    if(char !== '$') {
        throw new Error('Syntax error: unexpected characters at end of input.');
    }
    console.log('Expression is valid.');
} catch (e) {
    console.error(e.message);
}

修复说明 #

1. 修正factor定义：移除冗余的<number><factor>分支，确保factor仅包含合法的算术因子类型；
2. 添加错误分支：factor函数在字符不匹配任何分支时直接抛出错误，避免非法字符被跳过；
3. 输入完整性检查：解析完成后验证是否处理到输入末尾，捕获残留非法字符；
4. 修正异常类型：将Exception改为JavaScript标准的Error类型；
5. 简化digit函数：用includes替代多分支if，逻辑更简洁且易维护。

内容的提问来源于stack exchange，提问作者ayman benyahia