LL(1)语法转换报错求助：在线Parser Generator生成失败

问题1：产生式语法书写错误 #

RETURNST的定义多了一个冗余分号，原代码：

RETURNST ;:= return RETURNEXPR

修复为：

RETURNST ::= return RETURNEXPR

问题2：间接左递归（FLIST'） #

原FLIST'产生式调用FLIST，而FLIST又依赖FLIST'，形成循环依赖的间接左递归，违反LL(1)语法规则：

FLIST ::= FDEF FLIST'
FLIST' ::= FLIST | ""

修复为右递归形式：

FLIST ::= FDEF FLIST'
FLIST' ::= FDEF FLIST' | ""

问题3：间接左递归（VARLIST'） #

原VARLIST'调用VARLIST，VARLIST又依赖VARLIST'，存在循环依赖：

VARLIST ::= id VARLIST'
VARLIST' ::= , VARLIST | ""

修复为：

VARLIST ::= id VARLIST'
VARLIST' ::= , id VARLIST' | ""

问题4：间接左递归（PARLISTCALL'） #

原PARLISTCALL'调用PARLISTCALL，PARLISTCALL又依赖PARLISTCALL'，存在循环依赖：

PARLISTCALL ::= id PARLISTCALL'
PARLISTCALL' ::= , PARLISTCALL | ""

修复为：

PARLISTCALL ::= id PARLISTCALL'
PARLISTCALL' ::= , id PARLISTCALL' | ""

问题5：语法符号格式问题 #

FACTOR产生式中括号与非终结符之间的多余空格可能导致工具识别异常，原代码：

FACTOR ::= ( NUMEXPR) 

修复为：

FACTOR ::= (NUMEXPR)

修复后的完整LL(1)语法 #

MAIN ::= STMT
MAIN ::= FLIST 
MAIN ::= ""

FLIST ::= FDEF FLIST'
FLIST' ::= FDEF FLIST' | ""

FDEF ::= def id ( PARLIST ) { STMTLIST }

PARLIST ::= int id PARLIST'
PARLIST' ::= , int id PARLIST' | ""

VARLIST ::= id VARLIST'
VARLIST' ::= , id VARLIST' | ""

STMT ::= int VARLIST ;
STMT ::= ATRIBST ;
STMT ::= PRINTST ;
STMT ::= RETURNST ;
STMT ::= IFSTMT ;
STMT ::= { STMTLIST } ;
STMT ::= ; 

ATRIBST ::= id := ATREXPR
ATREXPR ::= EXPR | FCALL

FCALL ::= id ( PARLISTCALL )

PARLISTCALL ::= id PARLISTCALL'
PARLISTCALL' ::= , id PARLISTCALL' | ""

PRINTST ::= print EXPR

RETURNST ::= return RETURNEXPR
RETURNEXPR ::= id | ""

IFSTMT ::= if ( EXPR ) STMT IFSTMT'
IFSTMT' ::= else STMT | ""

STMTLIST ::= STMT STMTLIST'
STMTLIST' ::= STMT STMTLIST' | ""

EXPR ::= NUMEXPR EXPR'
EXPR' ::= < NUMEXPR | <= NUMEXPR | > NUMEXPR | >= NUMEXPR | == NUMEXPR | <> NUMEXPR | ""

NUMEXPR ::= TERM NUMEXPR'
NUMEXPR' ::= + TERM NUMEXPR' | - TERM NUMEXPR' | ""

TERM ::= FACTOR TERM'
TERM' ::= * FACTOR TERM' | / FACTOR TERM' | ""

FACTOR ::= num | (NUMEXPR) | id

验证说明 #

将修复后的语法输入LL(1)解析器生成工具即可消除解析表冲突，核心修复点是消除所有左递归和修正语法书写错误，这是LL(1)语法的硬性要求。

内容的提问来源于stack exchange，提问作者Lucas Broering