사용자 프로그래밍 언어 용 문맥 자유 문법

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 { $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/reduce 및 reduce/갈등을 줄이십시오. 출력은 또한 Exp : ID 규칙이 절대로 줄어들지 않는다고 알려줍니다.

아무도 내가이 문법을 명확하게 만들 수 있도록 도와 줄 수 있습니까?

Answer 1

Index은 비어 있습니다.

지금 생각해

이

Exp : ID 
    | ID Index 

사람들의 어떤이 적용? Index은 비워 둘 수 있으므로 그 중 하나만 적용 할 수있는 컨텍스트가 없습니다. 사용중인 파서 생성기는 INDEX 빈을 줄이고 Exp : ID을 사용할 수 없게 만들고 많은 충돌을 생성하는 경향이 있습니다.

I가 Index 변경 제안했던 :

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

장기적으로, 당신은 lvalue이 ID 및 lvalue [ Exp ] 및 rvalue을 포함하는 더 전통적인 "좌변 /를 rvalue"문법과 더 나을 수도 있지만 lvalue을 포함합니다. (ID [ Exp ] [ Exp ]에 대해서는 더 자세한 정교한 구문 분석 트리를 제공하지만 명백한 동질주의가 있습니다.)