自定义编程语言的上下文无关语法

Question

在我的大学完成了编译器设计课程之后，我一直在为一种简单的编程语言制作编译器，但我在语法分析器方面遇到了麻烦。我正在用mosml编写编译器，并使用它的内置解析器mosmlyac来构造解析器。下面是我的解析器中显示语法和associativity+precedence的摘录。

...
%right ASSIGN
%left OR
%left AND
%nonassoc NOT
%left EQUAL LESS
%left PLUS MINUS
%left TIMES DIVIDE
%nonassoc NEGATE
...
Prog : FunDecs EOF  { $1 }
;

FunDecs : Fun FunDecs   { $1 :: $2 }
        |               { [] }
;

Fun : Type ID LPAR TypeIds RPAR StmtBlock   { FunDec (#1 $2, $1, $4, $6, #2 $2) }
    | Type ID LPAR RPAR StmtBlock           { FunDec (#1 $2, $1, [], $5, #2 $2) }
;

TypeIds : Type ID COMMA TypeIds     { Param (#1 $2, $1) :: $4 }
        | Type ID                   { [Param (#1 $2, $1)] }
;

Type : VOID                     { Void }
     | INT                      { Int }
     | BOOL                     { Bool }
     | CHAR                     { Char }
     | STRING                   { Array (Char) }
     | Type LBRACKET RBRACKET   { Array ($1) }
;

StmtBlock : LCURLY StmtList RCURLY  { $2 }
;

StmtList : Stmt StmtList    { $1 :: $2 }
         |                  { [] }
;

Stmt : Exp SEMICOLON                    { $1 }
     | IF Exp StmtBlock                 { IfElse ($2, $3, [], $1) }
     | IF Exp StmtBlock ELSE StmtBlock  { IfElse ($2, $3, $5, $1) }
     | WHILE Exp StmtBlock              { While ($2, $3, $1) }
     | RETURN Exp SEMICOLON             { Return ($2, (), $1) }
;

Exps : Exp COMMA Exps   { $1 :: $3 }
     | Exp              { [$1] }
;

Index : LBRACKET Exp RBRACKET Index     { $2 :: $4 }
      |                                 { [] }
;

Exp : INTLIT                    { Constant (IntVal (#1 $1), #2 $1) }
    | TRUE                      { Constant (BoolVal (true), $1) }
    | FALSE                     { Constant (BoolVal (false), $1) }
    | CHRLIT                    { Constant (CharVal (#1 $1), #2 $1) }
    | STRLIT                    { StringLit (#1 $1, #2 $1) }
    | LCURLY Exps RCURLY        { ArrayLit ($2, (), $1) }
    | ARRAY LPAR Exp RPAR       { ArrayConst ($3, (), $1) }
    | Exp PLUS Exp              { Plus ($1, $3, $2) }
    | Exp MINUS Exp             { Minus ($1, $3, $2) }
    | Exp TIMES Exp             { Times ($1, $3, $2) }
    | Exp DIVIDE Exp            { Divide ($1, $3, $2) }
    | NEGATE Exp                { Negate ($2, $1) }
    | Exp AND Exp               { And ($1, $3, $2) }
    | Exp OR Exp                { Or ($1, $3, $2) }
    | NOT Exp                   { Not ($2, $1) }
    | Exp EQUAL Exp             { Equal ($1, $3, $2) }
    | Exp LESS Exp              { Less ($1, $3, $2) }
    | ID                        { Var ($1) }
    | ID ASSIGN Exp             { Assign (#1 $1, $3, (), #2 $1) }
    | ID LPAR Exps RPAR         { Apply (#1 $1, $3, #2 $1) }
    | ID LPAR RPAR              { Apply (#1 $1, [], #2 $1) }
    | ID Index                  { Index (#1 $1, $2, (), #2 $1) }
    | ID Index ASSIGN Exp       { AssignIndex (#1 $1, $2, $4, (), #2 $1) }
    | PRINT LPAR Exp RPAR       { Print ($3, (), $1) }
    | READ LPAR Type RPAR       { Read ($3, $1) }
    | LPAR Exp RPAR             { $2 }
;

Prog是%start符号，我故意遗漏了%token和%type声明。

我遇到的问题是，这个语法似乎不明确，并且考虑到在语法上运行mosmlyac -v的输出，似乎是包含令牌ID的规则才是问题所在，并且会创建shift/还原和减少/减少冲突。输出还告诉我，规则Exp : ID从未减少。

有人能帮我把这个语法弄清楚吗？

Answer 1

Index有一个空的产品。

现在考虑：

Exp : ID
    | ID Index

其中哪一个适用？由于Index被允许为空，因此不存在只适用其中一个的上下文。您使用的解析器生成器显然更倾向于减少空的INDEX，使Exp : ID不可用，并造成大量冲突。

我建议将Index改为：

Index : LBRACKET Exp RBRACKET Index     { $2 :: $4 }
      | LBRACKET Exp RBRACKET           { [ $2 ] }

尽管从长远来看，您可能会更好地使用一种更传统的"lvalue/rvalue“语法，其中lvalue包括ID和lvalue [ Exp ]，rvalue包含lvalue。(这将为ID [ Exp ] [ Exp ]提供更详细的解析树，但存在明显的同构关系。)