Flex/Bison 미니 C 컴파일러 어휘 및 의미 분석 이동/축소 충돌

Question

flex 및 bison을 사용하여 mini C 언어 용 컴파일러를 작성하고 싶습니다. 여기

/* This is an example uC program. */ 
int fac(int n) 
{ 
    if (n < 2) 
     return n; 
    return n * fac(n - 1); 
} 

int sum(int n, int a[]) 
{ 
    int i; 
    int s; 

    i = 0; 
    s = 0; 
    while (i < n) { 
     s = s + a[i]; 
     i = i + 1; 
    } 
    return s; 
} 

int main(void) 
{ 
    int a[2]; 

    a[0] = fac(5); 
    a[1] = 27; 
    return 0; 
} 

언어의 이런 종류의 구문 분석하는 내 문법입니다 : 내 언어의 예는 다음과 같을 것이다

program   ::= topdec_list 
topdec_list  ::= /empty/ | topdec topdec_list 
topdec   ::= vardec ";" 
        | funtype ident "(" formals ")" funbody 
vardec   ::= scalardec | arraydec 
scalardec  ::= typename ident 
arraydec  ::= typename ident "[" intconst "]" 
typename  ::= "int" | "char" 
funtype   ::= typename | "void" 
funbody   ::= "{" locals stmts "}" | ";" 
formals   ::= "void" | formal_list 
formal_list  ::= formaldec | formaldec "," formal_list 
formaldec  ::= scalardec | typename ident "[" "]" 
locals   ::= /empty/ | vardec ";" locals 
stmts   ::= /empty/ | stmt stmts 
stmt   ::= expr ";" 
        | "return" expr ";" | "return" ";" 
        | "while" condition stmt 
        | "if" condition stmt else_part 
        | "{" stmts "}" 
        | ";" 
else_part  ::= /empty/ | "else" stmt 
condition  ::= "(" expr ")" 
expr   ::= intconst 
        | ident | ident "[" expr "]" 
        | unop expr 
        | expr binop expr 
        | ident "(" actuals ")" 
        | "(" expr ")" 
unop   ::= "-" | "!" 
binop   ::= "+" | "-" | "*" | "/" 
        | "<" | ">" | "<=" | ">=" | "!=" | "==" 
        | "&&" 
        | "=" 
actuals   ::= /empty/ | expr_list 
expr_list  ::= expr | expr "," expr_list 

플렉스 모듈이 잘 작동을하고 원하는대로 값을 반환하지만 들소는 유지 문법 오류가 잘못되었음을 나타내는 이상한 오류를줍니다 (그렇지 않습니다). 여기 내 들소 파일입니다

%{ 
#include <stdio.h> 
#include <stdlib.h> 

extern int yylex(); 
extern int yyparse(); 
FILE* yyin; 
extern int lineNumber; 

void yyerror(const char* s); 
%} 

%union { 
    int intvalue; 
} 

%token<intvalue> INTCONST 
%token IDENT 
%token CHARK 
%token ELSEK 
%token IFK 
%token INTK 
%token RETURNK 
%token VOIDK 
%token WHILEK 
%token NOTK 
%token ANDK 
%token COMMAK 
%token DIVIDEK 
%token MULTIPLYK 
%token MINUSK 
%token PLUSK 
%token SEMICOLONK 
%token NEQUALK 
%token EQUALK 
%token ASSIGNMENTK 
%token RECOMPARATORK 
%token LECOMPARATORK 
%token RCOMPARATORK 
%token LCOMPARATORK 
%token RPARANTESESK 
%token LPARANTESESK 
%token RBRACKETK 
%token LBRACKETK 
%token RCURLY 
%token LCURLY 

%right ASSIGNMENTK 
%left ANDK 
%left EQUALK NEQUALK 
%left LCOMPARATORK RCOMPARATORK LECOMPARATORK RECOMPARATORK 
%left PLUSK 
%left MULTIPLYK DIVIDEK 
%left MINUSK NOTK 

%start program 

%% 

program: topdec_list 
     ; 
topdec_list: /*empty*/ 
        | topdec topdec_list 
       ; 
topdec: vardec SEMICOLONK 
      | funtype IDENT LPARANTESESK formals RPARANTESESK funbody 
     ; 
vardec: scalardec 
      | arraydec 
     ; 
scalardec: typename IDENT 
       ; 
arraydec: typename IDENT LBRACKETK INTCONST RBRACKETK 
       ; 
typename: INTK 
       | CHARK 
       ; 
funtype: typename 
      | VOIDK 
     ; 
funbody: LCURLY locals stmts RCURLY 
      | SEMICOLONK 
     ; 
formals: VOIDK 
      | formal_list 
     ; 
formal_list: formaldec 
        | formaldec COMMAK formal_list 
       ; 
formaldec: scalardec 
     | typename IDENT LBRACKETK RBRACKETK 
      ; 
locals: /*empty*/ 
     | vardec SEMICOLONK locals 
     ; 
stmts: /*empty*/ 
    | stmt stmts 
    ; 
stmt: expr SEMICOLONK 
    | RETURNK expr SEMICOLONK 
     | RETURNK SEMICOLONK 
     | WHILEK condition stmt 
     | IFK condition stmt else_part 
     | LCURLY stmts RCURLY 
     | SEMICOLONK 
     ; 
else_part: /*empty*/ | ELSEK stmt 
       ; 
condition: LPARANTESESK expr RPARANTESESK 
       ; 
expr: INTCONST 
     | IDENT 
     | IDENT LBRACKETK expr RBRACKETK 
     | unop expr 
     | expr binop expr 
     | IDENT LPARANTESESK actuals RPARANTESESK 
     | LPARANTESESK expr RPARANTESESK 
     ; 
unop: MINUSK | NOTK 
    ; 
binop: PLUSK 
    | MINUSK 
     | MULTIPLYK 
     | DIVIDEK 
     | LCOMPARATORK 
     | RCOMPARATORK 
    | LECOMPARATORK 
     | RECOMPARATORK 
     | NEQUALK 
     | EQUALK 
     | ANDK 
     | ASSIGNMENTK 
    ; 
actuals: /*empty*/ 
      | expr_list 
      ; 
expr_list: expr 
       | expr COMMAK expr_list 
       ; 

%% 

int main(int argc, char **argv) 
{ 
    yyin = fopen("input.c", "r"); 
    do 
    { 
     yyparse(); 
    } while (!feof(yyin)); 
    fclose(yyin); 
    return 0; 
} 

void yyerror(const char* error) 
{ 
    fprintf(stderr, "Parse error in line %d: %s\n", lineNumber, error); 
} 

이 입력에 대한 예 :

int i; 
i = 0; 

내가 구문 오류가 두 번째 i가 (난 내 플렉스에서 토큰을 인쇄 구별 직후에 일어난 오류가 파일 그래서 할당 문자에 도달 할 때까지 아무런 문제가 없다는 것을 압니다.)

또는 다른 예로서

이 광고 통과했을 때

int fac(int n); 

난이 구문 오류와 제 int을 보는 것을 의미 오른쪽 제 paranteses 후 (정확하게 Parse error in line 1: syntax error 임) 동일한 구문 오류를 그것은 내 문법이 잘 보이기 때문에해서는 안됩니다. 다음

는 또한 들소 의해 생성 된 경고는 (플렉스 GCC 괜찮지)

semantic_analyzer.y: warning: 26 shift/reduce conflicts [-Wconflicts-sr] 
semantic_analyzer.y:78.10-17: warning: rule useless in parser due to conflicts [-Wother] 
funtype: typename 
      ^^^^^^^^ 

제안이나 수정은 미리 감사 :) 이해된다.

Answer 1

int i; 
i = 0; 

은 유효한 C 프로그램이 아니며 문법이이를 올바르게 거부합니다. (문법 알 수 있듯이 프로그램은, 선언 및 i = 10;의 순서가 선언되지 않습니다.) 당신이 언급 두 번째 문제는 첫 번째 주장 문법에 의한 시프트 감소 갈등과 관련이

int (int fac(int n))은 funtype으로, int (int ;)은 typename으로 줄여야합니다. 구문 분석기가 IDENT을 전환할지 또는 typename을 funtype으로 줄이는 지 결정해야하는 시점에서 하나의 미리보기 토큰 (IDENT) 만 볼 수 있고 두 번째는 초에 달려 있기 때문에 수행 할 작업을 알 수 없습니다. 다음 lookahead 토큰 (열린 괄호 일 수도 있고 아닐 수도 있음). 기본적으로 yacc/bison은 이동을 통해 shift-reduce 충돌을 해결합니다. 즉 에 대한 int fac은 두 번째 생산의 접두어가 될 수 없습니다. 따라서 (은 오류를 유발합니다.