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

Question

在我大学完成编译器设计课程后，我一直在尝试为一种简单的编程语言制作编译器，但我在解析器方面遇到了麻烦。我在 mosml 中制作编译器并使用其内置解析器 mosmlyac 来构建解析器。这是我的解析器的摘录，显示了语法和关联性+优先级。

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

FunDecs : Fun FunDecs   {  ::  }
        |               { [] }
;

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

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

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

StmtBlock : LCURLY StmtList RCURLY  {  }
;

StmtList : Stmt StmtList    {  ::  }
         |                  { [] }
;

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

Exps : Exp COMMA Exps   {  ::  }
     | Exp              { [] }
;

Index : LBRACKET Exp RBRACKET Index     {  ::  }
      |                                 { [] }
;

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

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

我遇到的问题是这个语法似乎有歧义，并且在语法上查看运行 mosmlyac -v 的输出似乎是包含令牌 ID 的规则问题并造成 shift/reduce 和 reduce/reduce 冲突。输出还告诉我规则 Exp : ID 永远不会减少。

谁能帮我把这个语法弄清楚？

Answer 1

Index 产生式为空。

现在考虑：

Exp : ID
    | ID Index

哪些适用？由于 Index 允许为空，因此不存在仅其中一个适用的上下文。您正在使用的解析器生成器显然更喜欢减少空 INDEX，使 Exp : ID 无法使用并产生大量冲突。

我建议将 Index 更改为：

Index : LBRACKET Exp RBRACKET Index     {  ::  }
      | LBRACKET Exp RBRACKET           { [  ] }

尽管在长运行中，使用更传统的 "lvalue/rvalue" 语法可能会更好，其中 lvalue 包括 ID 和 lvalue [ Exp ] rvalue 包括 lvalue。（这将为 ID [ Exp ] [ Exp ] 提供更精细的解析树，但存在明显的同态。）

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

Context-Free Grammar for Custom Programming Language

grammar

parsing

yacc

sml

context-free-grammar