LL(1) 语法转换问题 – 解析器生成器错误

Question

我正在努力将语法转换为 LL(1) 形式，但是当我尝试使用在线 LL(1) 解析器生成器时，它报告错误。我已经按照标准的转换程序进行了操作，但我似乎找不到问题所在。这是我正在使用的语法：

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

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

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

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

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

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

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

FCALL ::= id ( PARLISTCALL )

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

PRINTST ::= print EXPR

RETURNST ;:= return RETURNEXPR
RETURNEXPR ::= id
RETURNEXPR ::= "

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

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

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

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

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

FACTOR ::= num 
FACTOR ::= ( NUMEXPR) 
FACTOR ::= id

我使用这个解析器：https://www.cs.princeton.edu/courses/archive/spring20/cos320/LL1/

此错误出现在表中。

我希望解析器能够工作。

Answer 1

EXPR

和

FCALL

都可以以

id

开头。因此，语法不是 LL(1)，解析器生成器无法决定是否应该尝试解析

EXPR

或

FCALL

。这是说明同一问题的最小语法：

A ::= id ( )
A ::= id

修改这种情况有三种可能性：引入符号表、利用特殊的词汇约定或重新表述语法。

1. 使用符号表，您可以使用包含迄今为止在源代码中定义的所有变量的名称和类型的表来区分函数名称和变量名称（例如

   func_id

   与

   var_id

   ）；这在其他地方有相当广泛的讨论。
2. 或者，您可以为函数或变量名称建立（词汇）要求，以将它们彼此区分开来，例如所有变量都带有前缀

   $

   .
3. 最后一个选项是删除有问题的

   ATREXPR ::= FCALL

   和/或

   FACTOR ::= id

   规则，并以明确的方式重新实施它们。一个可能的例子如下：它大致相当于示例代码，但表达式中允许函数调用。

FACTOR ::= id OPTPARLISTCALL
OPTPARLISTCALL ::= ( PARLISTCALL )
OPTPARLISTCALL ::= ''