LL(1)数学表达式解析器语法合规性修正咨询

问题背景 #

开发LL(1)数学表达式解析器时，已完成左递归消除与左公因子提取，但ANTLR4的-Xlog检测显示math_expression_e_dash、math_expression_t_dash、math_expression_f_dash规则存在前瞻符号冲突，不符合LL(1)规范。

现有ANTLR4语法 #

grammar test;

NUM: LEFT_PAR? NEG? INT (DOT INT)? EXP? RIGHT_PAR? ;
fragment INT: [1-9][0-9]* | '0' ;
fragment EXP: [eE][+\-]? INT ;
fragment NEG: '-' ;
fragment DOT: '.' ;

FACTORIAL: '^' ;
ADD: '+' ;
SUB: '-' ;
MUL: '*' ;
DIV: '/' ;
MODULUS: '%' ;
LOGICAL_NEG: '!' ;
LEFT_PAR: '(' ;
RIGHT_PAR: ')' ;
COMMA: ',' ;
VAR_NAME: [A-Za-z0-9_.]+ ;
CEIL : 'CEIL' ;
FLOOR: 'FLOOR' ;
TRUNC: 'TRUNC' ;
SQRT: 'SQRT' ;
ABS: 'ABS' ;
EXP_FUNC: 'EXP' ;
LOG: 'LOG' ;
SIN: 'SIN' ;
COS: 'COS' ;
TAN: 'TAN' ;
MIN: 'MIN' ;
MAX: 'MAX' ;
WS: [ \t\r\n]+ -> channel(HIDDEN) ;

math_expression:
math_expression_t math_expression_e_dash ;

math_expression_t:
math_expression_f math_expression_t_dash ;

math_expression_e_dash : 
 ( ADD | SUB ) math_expression_t math_expression_e_dash | /*epsilon*/ ;

math_expression_f:
math_expression_n math_expression_f_dash ;

math_expression_t_dash:
( MUL | DIV | MODULUS ) math_expression_f math_expression_t_dash | /*epsilon*/ ;

math_expression_n:
LEFT_PAR math_expression RIGHT_PAR | LOGICAL_NEG math_expression | NUM | SUB? VAR_NAME ;

math_expression_f_dash:
FACTORIAL math_expression_f | /*epsilon*/ ;

ANTLR4 -Xlog检测日志 #

2022-11-08 16:57:33:896 semantics LogManager.java:25 tokens={EOF=-1, NUM=1, FACTORIAL=2, ADD=3, SUB=4, MUL=5, DIV=6, MODULUS=7, LOGICAL_NEG=8, LEFT_PAR=9, RIGHT_PAR=10, COMMA=11, VAR_NAME=12, CEIL=13, FLOOR=14, TRUNC=15, SQRT=16, ABS=17, EXP_FUNC=18, LOG=19, SIN=20, COS=21, TAN=22, MIN=23, MAX=24, WS=25}

2022-11-08 16:57:33:896 semantics LogManager.java:25 strings={'^'=2, '+'=3, '-'=4, '*'=5, '/'=6, '%'=7, '!'=8, '('=9, ')'=10, ','=11, 'CEIL'=13, 'FLOOR'=14, 'TRUNC'=15, 'SQRT'=16, 'ABS'=17, 'EXP'=18, 'LOG'=19, 'SIN'=20, 'COS'=21, 'TAN'=22, 'MIN'=23, 'MAX'=24}

2022-11-08 16:57:33:899 LL1 LogManager.java:25 
DECISION 0 in rule math_expression_e_dash
2022-11-08 16:57:33:899 LL1 LogManager.java:25 look=[{3..4}, {2..7, 10}]
2022-11-08 16:57:33:899 LL1 LogManager.java:25 LL(1)? false
2022-11-08 16:57:33:899 LL1 LogManager.java:25 
 
DECISION 1 in rule math_expression_t_dash
2022-11-08 16:57:33:900 LL1 LogManager.java:25 look=[{5..7}, {2..7, 10}]
2022-11-08 16:57:33:900 LL1 LogManager.java:25 LL(1)? false
2022-11-08 16:57:33:900 LL1 LogManager.java:25 

DECISION 2 in rule math_expression_n
2022-11-08 16:57:33:900 LL1 LogManager.java:25 look=[4, 12]
2022-11-08 16:57:33:900 LL1 LogManager.java:25 LL(1)? true
2022-11-08 16:57:33:900 LL1 LogManager.java:25 

DECISION 3 in rule math_expression_n
2022-11-08 16:57:33:900 LL1 LogManager.java:25 look=[9, 8, 1, {4, 12}]
2022-11-08 16:57:33:900 LL1 LogManager.java:25 LL(1)? true
2022-11-08 16:57:33:900 LL1 LogManager.java:25 

DECISION 4 in rule math_expression_f_dash
2022-11-08 16:57:33:900 LL1 LogManager.java:25 look=[2, {2..7, 10}]
2022-11-08 16:57:33:900 LL1 LogManager.java:25 LL(1)? false

冲突原因分析 #

1. 一元运算符作用范围过大：LOGICAL_NEG math_expression允许逻辑非作用于整个表达式，导致表达式的FOLLOW集合包含当前层级的操作符（如ADD/SUB），与后缀规则的FIRST集合产生交集。
2. 后缀规则递归形式错误：如math_expression_f_dash: FACTORIAL math_expression_f | ε采用右递归，导致FOLLOW集合包含自身的FIRST符号（FACTORIAL），引发前瞻冲突。
3. NUM定义不合理：包含LEFT_PAR?和RIGHT_PAR?，会错误匹配带括号的表达式，干扰括号规则的解析。

修正后的LL(1)语法 #

grammar test;

// 修正NUM定义，移除括号（括号由primary规则处理）
NUM: NEG? INT (DOT INT)? EXP? ;
fragment INT: [1-9][0-9]* | '0' ;
fragment EXP: [eE][+\-]? INT ;
fragment NEG: '-' ;
fragment DOT: '.' ;

// 运算符与关键字
FACTORIAL: '^' ;
ADD: '+' ;
SUB: '-' ;
MUL: '*' ;
DIV: '/' ;
MODULUS: '%' ;
LOGICAL_NEG: '!' ;
LEFT_PAR: '(' ;
RIGHT_PAR: ')' ;
COMMA: ',' ;
// 修正VAR_NAME，符合常规标识符规则（不能以数字开头）
VAR_NAME: [A-Za-z_][A-Za-z0-9_.]* ;
CEIL : 'CEIL' ;
FLOOR: 'FLOOR' ;
TRUNC: 'TRUNC' ;
SQRT: 'SQRT' ;
ABS: 'ABS' ;
EXP_FUNC: 'EXP' ;
LOG: 'LOG' ;
SIN: 'SIN' ;
COS: 'COS' ;
TAN: 'TAN' ;
MIN: 'MIN' ;
MAX: 'MAX' ;
WS: [ \t\r\n]+ -> channel(HIDDEN) ;

// 起始规则：加法级表达式
expr
    : term expr_dash
    ;

// 加减后缀（左结合）
expr_dash
    : (ADD | SUB) term expr_dash
    | /* epsilon */
    ;

// 乘法级表达式
term
    : factor term_dash
    ;

// 乘除模后缀（左结合）
term_dash
    : (MUL | DIV | MODULUS) factor term_dash
    | /* epsilon */
    ;

// 阶乘级表达式
factor
    : primary factor_dash
    ;

// 阶乘后缀（左结合）
factor_dash
    : FACTORIAL factor_dash
    | /* epsilon */
    ;

// 原子表达式：包含一元运算符与基础元素
primary
    : NUM
    | VAR_NAME
    | LEFT_PAR expr RIGHT_PAR
    | LOGICAL_NEG primary
    | SUB primary
    ;

// 补充函数调用规则（原语法定义了关键字但未处理调用）
function_call
    : (CEIL | FLOOR | TRUNC | SQRT | ABS | EXP_FUNC | LOG | SIN | COS | TAN) LEFT_PAR expr RIGHT_PAR
    | (MIN | MAX) LEFT_PAR expr (COMMA expr)+ RIGHT_PAR
    ;

修正说明 #

1. 限制一元运算符作用范围：将LOGICAL_NEG math_expression改为LOGICAL_NEG primary，确保一元运算符仅作用于原子表达式，避免表达式嵌套导致FOLLOW集合污染。
2. 修正后缀规则递归形式：将右递归的后缀规则改为左结合的迭代形式（如factor_dash: FACTORIAL factor_dash | ε），确保FIRST集合与FOLLOW集合无交集。
3. 修复NUM与VAR_NAME定义：移除NUM中的括号匹配，修正VAR_NAME为合法标识符格式，避免语法歧义。
4. 补充函数调用规则：完善原语法中未实现的函数调用逻辑，符合表达式解析的完整性。

修正后的语法满足LL(1)规范：所有非终结符的产生式FIRST集合无交集，含ε产生式的规则其FIRST集合与FOLLOW集合也无交集。

内容的提问来源于stack exchange，提问作者Delta Striker