1. 홈
  2. 질의 응답
  3. 간단한 c 문법에서 시프트/감소 충돌이 발생했습니다.

간단한 c 문법에서 시프트/감소 충돌이 발생했습니다.

2016-12-27 22 views
0

간단한 C로 컴파일러 용 파서를 작성하고 있는데 이유가 무엇인지 이해하려고합니다.
yacc : 22 시프트/줄이기 충돌, 15 줄이기/줄이기 충돌.간단한 c 문법에서 시프트/감소 충돌이 발생했습니다.

렉스 파일

letter  [a-zA-Z] 
Hexdigits [A-F|0-9] 
OctalDigit [0-7] 
digit  [0-9] 
digitMZ  [1-9] 
newline  (\n) 
integerNum "0"|{digitMZ}{digit}* 
HexNumber ("0X"|"0x"){Hexdigits}+ 
OctalNumber ["0"]{OctalDigit}+ 
BinaryNumber ["0"|"1"]+"b" 
identifier {letter}({letter}|{digit}|"_")* 
char  "'"."'" 
wordString \"[^\"]*\" 
Comment  "/%"[^"%/"]+"%/" 
StrDec  "["{integerNum}"]" 

%{ 

%} 

%option yylineno 

%% 
"string"" "*{StrDec} { return STRING_DECLERATION;} 
boolean  { return BOOLEAN; } 
else  { return ELSE; } 
if   { return IF; } 
integer  { return INTEGER; } 
procedure { return PROCEDURE; } 
char  { return CHAR; } 
string  { return STRING; } 
var   { return VAR; } 
intptr  { return INTPTR; } 
charptr  { return CHARPTR; } 
return  { return RETURN; } 
void  { return VOID; } 
while  { return WHILE; } 
"isprint()" { return IS_PRINT; } 

true|false { return BOOLCONSTANT; } 
":"   { return COLON; } 
"+"   { return PLUS; } 
"&"   { return ADDRESS; } 
"^"   { return DEREFERENCE; } 
"-"   { return MINUS; }    
"*"   { return MULTIPLICATION; } 
"&&"  { return AND; } 
"/"   { return DIVISION; } 
"<="  { return LESSEQUAL; } 
"<"   { return LESS; } 
">"   { return GREATER; } 
">="  { return GREATEREQUAL; } 
"=="  { return EQUAL; } 
"!="  { return NOTEQUAL; } 
"="   { return ASSIGN; } 
";"   { return SEMICOLON; } 
","   { return COMMA; } 
"("   { return LEFTPAREN; } 
")"   { return RIGHTPAREN; } 
"["   { return LEFTBRACKET; } 
"]"   { return RIGHTBRACKET; } 
"{"   { return LEFTBRACE; } 
"}"   { return RIGHTBRACE; } 
"||"  { return OR; } 
"!"   { return NOT; } 
" "+  { } 
"|"  {return ABS_LENGTH;} 
" "+ {} 

{newline}  { } 
{Comment} {} 
{wordString} {return WORDSTRING; } 
{integerNum} {return INTEGER_CONST; } 
{char}   {return CHAR_IDENTIFIER; } 
{identifier} {return IDENTIFIER; } 
{HexNumber}  {return HEX_NUMBER; } 
{OctalNumber} {return OCTAL_NUMBER; } 
{BinaryNumber} {return BINARY_NUMBER; } 
.    {return ERROR; } 

%%

은 yacc 파일

%{ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define YYDEBUG 1 
#define YYSTYPE struct node* 
int yyerror(char*); 
int yylex(); 
typedef struct node 
{ 
    char * rtoken; 
    struct node * left; 
    struct node * right; 
    char * ltoken; 
}node; 

node * mknode(char * ltoken, node * left, node * right,char * rtoken); 
void printtree(node * tree); 
char * getLT(node *); 

extern char *yytext; 



%} 

%token STRING_DECLERATION 
%token STRING 
%token WORDSTRING 
%token BOOLEAN 
%token BREAK 
%token ELSE 
%token IF 
%token IMPLEMENTS 
%token INTEGER 
%token PROCEDURE 
%token CHAR 
%token VAR 
%token INTPTR 
%token CHARPTR 
%token RETURN 
%token VOID 
%token WHILE 
%token IS_PRINT 
%token BOOLCONSTANT 
%token PLUS 
%token COLON 
%token ADDRESS 
%token DEREFERENCE 
%token MINUS 
%token MULTIPLICATION 
%token AND 
%token DIVISION 
%token LESS 
%token LESSEQUAL 
%token GREATER 
%token GREATEREQUAL 
%token EQUAL 
%token NOTEQUAL 
%token ASSIGN 
%token SEMICOLON 
%token COMMA 
%token LEFTPAREN 
%token RIGHTPAREN 
%token LEFTBRACKET 
%token RIGHTBRACKET 
%token LEFTBRACE 
%token RIGHTBRACE 
%token OR 
%token NOT 
%token ABS_LENGTH 
%token CHAR_IDENTIFIER 
%token HEX_NUMBER 
%token OCTAL_NUMBER 
%token BINARY_NUMBER 
%token ERROR 
%token INTEGER_CONST 
%token IDENTIFIER 
%% 

start: s{printtree($1);} 
     ; 

s:  expr {$$=$1;} 
     |expr s {node *yu = mknode("",$1,NULL,"\n");$$= mknode("",yu,$2,"");} 
     ; 

expr:  function {$$=$1;} 
     |assignment SEMICOLON {$$=$1;} 
     |decleration SEMICOLON {$$=$1;} 
     |condition {$$=$1;} 
     |BRACES {$$=$1;} 

     ; 

function: PROCEDURE iden LEFTPAREN argListOpt RIGHTPAREN RETURN identifiertype compondStmt 
     {node *z =mknode("RETURN:",$7,NULL,"\n");node *o =mknode(getLT($2),$4,z,""); $$ = mknode("(PROCEDURE",o,$8,"\n)\n");} 
     |PROCEDURE iden LEFTPAREN RIGHTPAREN RETURN identifiertype compondStmt 
     {node *z2 = mknode("",NULL,NULL,"");node *z1 =mknode("RETURN:",$6,NULL,"\n"); 
     node *o =mknode(getLT($2),z2,z1,""); $$ = mknode("(PROCEDURE",o,$7,"\n)\n");} 
     ; 

argListOpt: multidentifier COLON identifiertype SEMICOLON argListOpt 
     {node *fg =mknode("",$1,$3,""); $$ = mknode("recive:",fg,$5,"");} 
     |multidentifier COLON identifiertype{$$ = mknode("recive:",$1,$3,"");} 
     ; 

compondStmt: BRACES{$$=$1;} 
     |SEMICOLON{$$ = mknode("",NULL,NULL,"");} 
     ; 

functionCall: iden LEFTPAREN sendArgs RIGHTPAREN{node *Sgl = mknode("(",$3,NULL,")");$$= mknode("",$1,Sgl,"");} 
     |iden LEFTPAREN RIGHTPAREN {node *Sgg = mknode("(",NULL,NULL,")");$$= mknode("",$1,Sgg,"");} 
     ; 

sendArgs: return_val {$$=$1;} 
     |sendArgs COMMA return_val {node *SA = mknode("",$1,NULL,",");$$= mknode("",SA,$3,"");} 
     ; 


BRACES:  LEFTBRACE All RIGHTBRACE {$$ = mknode("\n{BRACES\n",$2,NULL,"\n}");} 
     |LEFTBRACE RIGHTBRACE{$$ = mknode("\n{BRACES\n",NULL,NULL,"\n}");} 
     |LEFTBRACE BRACES RIGHTBRACE{$$ = mknode("\n{BRACES\n",$2,NULL,"\n}");} 
     ; 


All:  RETURN return_val SEMICOLON{$$ = mknode("RETURN",$2,NULL,"\n");} 
     |All RETURN return_val SEMICOLON{node * K = mknode("RETURN",$2,NULL,"");$$ = mknode("",$1,K,"\n");} 
     |All function{$$ = mknode("",$1,$2,"\n");} 
     |function {$$=$1;} 
     |assignment {$$ = mknode("(",$1,NULL,")\n");} 
     |assignment SEMICOLON {$$ = mknode("(",$1,NULL,")\n");} 
     |decleration SEMICOLON{$$=$1;} 
     |decleration{$$=$1;} 
     |All decleration SEMICOLON {$$ = mknode("",$1,$2,"\n");} 
     |All assignment SEMICOLON {$$ = mknode("",$1,$2,"\n");} 
     |condition{$$=$1;} 
     |All condition{$$ = mknode("",$1,$2,"\n");} 
     |All BRACES {$$ = mknode("",$1,$2,"\n");} 
     |BRACES All {$$ = mknode("",$1,$2,"\n");} 
     ; 

return_val: int_num{$$=$1;} 
     |iden {$$=$1;} 
     |wstring{$$ = $1;} 
     |exp{$$=$1;} 
     |char_id{$$ = mknode(yytext,NULL,NULL,"");} 
     |bool{$$=$1;} 
     |wordlength{$$=$1;} 
     |absolute{$$=$1;} 
     |identifierabs{$$=$1;} 
     ; 

decleration: VAR multidentifier COLON identifiertype {$$ = mknode("",$2,$4,"\n");} 
     ; 

multidentifier: iden {$$=$1;} 
     | multidentifier COMMA iden{node *er = mknode("",$1,NULL,",");$$= mknode("",er,$3,"");} 
     ; 

bool: BOOLCONSTANT{$$ = mknode(yytext,NULL,NULL,"");} 
     ; 

assignment : iden ASSIGN functionCall {node *pop = mknode("=",$1,NULL,"");$$ = mknode("\t(",pop,$3,")");} 
     | iden ASSIGN exp {node *rop = mknode("=",$1,NULL,"");$$ = mknode("\t(",rop,$3,")");} 
     | iden ASSIGN bool{node *nop = mknode("=",$1,NULL,"");$$ = mknode("\t(",nop,$3,")");} 
     | iden ASSIGN pointeroperator iden 
     {node *gh= mknode("",$3,$4,"");node *e1 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e1,gh,")");} 
     | iden ASSIGN iden {node *e2 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e2,$3,")");} 
     | iden ASSIGN wstring {node *e3 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e3,$3,")");} 
     | iden ASSIGN char_id{node *e4 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e4,$3,")");} 
     | iden ASSIGN "null"{node *e5 = mknode("=",$1,NULL,"");$$ = mknode("\t(",e5,NULL,"NULL)");} 
     ; 
char_id: CHAR_IDENTIFIER {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 

exp:  int_num {$$=$1;} 
      |exp methoperator exp {node *y = mknode(getLT($2),$1,NULL,"");$$ = mknode("(",y,$3,")");} 
      |LEFTPAREN exp methoperator exp RIGHTPAREN {node *y = mknode(getLT($3),$2,NULL,"");$$ = mknode("(",y,$4,")");}/**/ 
     |iden {$$=$1;} 
     |LEFTPAREN exp RIGHTPAREN {$$ = mknode("(",$2,NULL,")");}/**/ 
      ; 

condition: whileCond{$$=$1;} 
     |ifCond{$$=$1;} 
     ; 

ifCond:  IF LEFTPAREN innercond RIGHTPAREN BRACES{$$ = mknode("(COND \n",$3,$5,"\n)\n");} 
     |IF LEFTPAREN innercond RIGHTPAREN BRACES ELSE BRACES{node *yk= mknode("ELSE",$7,NULL,""); 
     node *j= mknode("",$5,yk,"");$$ = mknode("(COND \n",$3,j,"\n)\n");} 
     ; 

whileCond: WHILE LEFTPAREN innercond RIGHTPAREN BRACES {$$ = mknode("(LOOP \n",$3,$5,"\n)\n");}  
     ; 

wstring: WORDSTRING{$$ = mknode(yytext,NULL,NULL,"");} 
     ; 
condexp: exp signoperator exp {$$ = mknode(getLT($2),$1,$3,"");} 
     |wstring IsEqual wstring {$$ = mknode(getLT($2),$1,$3,"");} 
     |iden signoperator exp{$$ = mknode(getLT($2),$1,$3,"");} 
     |bool{$$=$1;} 
     |iden IsEqual wstring {$$ = mknode(getLT($2),$1,$3,"");} 
     |wstring IsEqual iden{$$ = mknode(getLT($2),$1,$3,"");} 
     |char_id IsEqual char_id {$$ = mknode(getLT($2),$1,$3,"");} 
     |iden IsEqual char_id {$$ = mknode(getLT($2),$1,$3,"");} 
     |char_id IsEqual iden{$$ = mknode(getLT($2),$1,$3,"");} 
     |exp signoperator wordlength {$$ = mknode(getLT($2),$1,$3,"");} 
     |wordlength signoperator exp {$$ = mknode(getLT($2),$1,$3,"");} 
     |exp signoperator absolute{$$ = mknode(getLT($2),$1,$3,"");}  
     |absolute signoperator exp{$$ = mknode(getLT($2),$1,$3,"");} 
     |wordlength signoperator absolute{$$ = mknode(getLT($2),$1,$3,"");} 
     |absolute signoperator wordlength {$$ = mknode(getLT($2),$1,$3,"");} 
     |identifierabs signoperator exp {$$ = mknode(getLT($2),$1,$3,"");} 
     |identifierabs signoperator wordlength{$$ = mknode(getLT($2),$1,$3,"");} 
     |identifierabs signoperator absolute{$$ = mknode(getLT($2),$1,$3,"");} 
     |identifierabs signoperator identifierabs{$$ = mknode(getLT($2),$1,$3,"");} 
     ; 


wordlength: ABS_LENGTH wstring ABS_LENGTH {$$ = mknode("|",$2,NULL,"|");} 
     ; 

absolute : ABS_LENGTH int_num ABS_LENGTH{$$ = mknode("|",$2,NULL,"|");}  
     ; 

identifierabs: ABS_LENGTH iden ABS_LENGTH {$$ = mknode("|",$2,NULL,"|");} 
     ; 

innercond: condexp {$$=mknode("\t(",$1,NULL,")");} 
     |LEFTPAREN condexp RIGHTPAREN{$$ = mknode("(",$2,NULL,")");} 
     |LEFTPAREN condexp RIGHTPAREN condoperator innercond{node *t = mknode("",$4,$5,"");$$ = mknode("(",$2,t,")");} 
     |condexp condoperator innercond 
     {node *lolo = mknode("(",$1,NULL,"");node *Sr = mknode(getLT($2),lolo,NULL,")");$$= mknode(" ",Sr,$3,"");} 
     |LEFTPAREN condexp condoperator innercond RIGHTPAREN 
     {node *lili = mknode("(",$2,NULL,"");node *Sr = mknode(getLT($3),lili,NULL,",");$$= mknode(" ",Sr,$4,")");} 
     ; 


methoperator: PLUS {$$ = mknode(yytext,NULL,NULL,"");} 
     |MINUS {$$ = mknode(yytext,NULL,NULL,"");} 
     |MULTIPLICATION  {$$ = mknode(yytext,NULL,NULL,"");} 
     |DIVISION {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 

pointeroperator:ADDRESS {$$ = mknode(yytext,NULL,NULL,"");} 
     |DEREFERENCE {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 
identifiertype: STRING_DECLERATION {$$ = mknode(yytext,NULL,NULL,"");} 
     |BOOLEAN {$$ = mknode(yytext,NULL,NULL,"");} 
     |INTEGER {$$ = mknode(yytext,NULL,NULL,"");} 
     |CHAR {$$ = mknode(yytext,NULL,NULL,"");} 
     |INTPTR  {$$ = mknode(yytext,NULL,NULL,"");} 
     |CHARPTR {$$ = mknode(yytext,NULL,NULL,"");} 
     |int_num{$$=$1;} 
     ; 

iden :  IDENTIFIER {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 
signoperator: LESS {$$ = mknode(yytext,NULL,NULL,"");} 
     |LESSEQUAL {$$ = mknode(yytext,NULL,NULL,"");} 
     |GREATER {$$ = mknode(yytext,NULL,NULL,"");} 
     |GREATEREQUAL {$$ = mknode(yytext,NULL,NULL,"");} 
     |IsEqual {$$=$1;} 
     ; 

IsEqual: EQUAL {$$ = mknode(yytext,NULL,NULL,"");} 
     |NOTEQUAL {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 

condoperator: AND {$$ = mknode(yytext,NULL,NULL,"");} 
     |OR {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 

int_num: INTEGER_CONST {$$ = mknode(yytext,NULL,NULL,"");} 
     |BINARY_NUMBER {$$ = mknode(yytext,NULL,NULL,"");} 
     |OCTAL_NUMBER {$$ = mknode(yytext,NULL,NULL,"");} 
     |HEX_NUMBER {$$ = mknode(yytext,NULL,NULL,"");} 
     ; 

%% 

#include "lex.yy.c" 
int main() 
{ 
return yyparse(); 
} 
node* mknode(char * ltoken, node * left, node * right,char * rtoken) 
{ 
node * newnode = (node*)malloc(sizeof(node)); 
char * newstr = (char*)malloc(sizeof(ltoken)+1); 
strcpy(newstr, ltoken); 
char * newstrr = (char*)malloc(sizeof(rtoken)+1); 
strcpy(newstrr, rtoken); 
newnode->left = left; 
newnode->right = right; 
newnode->ltoken = newstr; 
newnode->rtoken = newstrr; 
return newnode; 
} 

void printtree(node * tree) 
{ 
printf("%s ", tree->ltoken); 
if (tree->left) 
    printtree(tree->left); 
if (tree->right) 
    printtree(tree->right); 
printf("%s ", tree->rtoken); 
} 
int yyerror(char* s) 
{ 
extern int yylineno; 
printf("yacc error: %s at line %d\n",s,yylineno); return 0; 
} 
char * getLT(node * s) 
{ 
return s->ltoken; 
}

내가 디버그를 실행하고 내가 왜이 모든 갈등을 알고 이해하지만 난 정말 무슨 뜻인지 이해하지 못하고있다. 내 디버그 출력의

은 기본적으로 파서 생성기 특정 단계에서 적용 할 규칙을 결정할 수 없음을 의미

debug output

출처

2016-12-27 Adir Zoari

답변

0

충돌 오류가없는 (이 긴 문서이기 때문에 내가 링크를 추가). 시프트/감소 충돌은 규칙을 완료 (감소)하거나 다음 토큰 (시프트)을 소비하고 그 상태에서 계속할 수있는 경우입니다. /이 문제를 줄일 일반적인 이동은 경우-else 문입니다 :

문 경우 다른 지점이 속한 않습니다 
if condition 
    if another condition 
     # Do something... 
    else 
     # Do something else

에? 이것 좀 봐 : 파서가 이동하기로 결정

IF <condition> <statement> IF <condition> <statement> ELSE <statement> 
            The parser is here^

경우, 다른 지점은 내부 문장의 일부가 될 것입니다하지만이 감소하는 경우, 외부 일이있을 것이다. 일반적으로 시프트 감소 충돌은 감소 대신 이동하여 처리됩니다.

이제 축소 감소 충돌은 2 개의 규칙이 동일한 입력에 적용되므로 문법에 치명적인 오류가있는 경우 발생합니다. 예 :

sequence: 
     %empty   { printf ("empty sequence\n"); } 
    | maybeword 
    | sequence word { printf ("added word %s\n", $2); } 
    ; 

maybeword: 
     %empty { printf ("empty maybeword\n"); } 
    | word  { printf ("single word %s\n", $1); } 
    ;

그래서 문법을보고 그 감소 감소 충돌을 찾아라!

파싱을 배우는 경우 고려해야 할 사항은 처음에 파서를 굴리다 (하향식 재귀 파생 파서처럼)! 그리 나쁘지는 않지만 사용하는 가장 복잡한 알고리즘은 수학 표현을위한 shunting-yard 알고리즘 일 것입니다. 또한 더 나은 오류 처리와 파서 생성기 (해킹없이)로 파싱 할 수없는 사용자 정의 문법의 이점을 누릴 수 있습니다.

출처

2016-12-27 19:38:30

+0

내 downvote에 대한 이유가있을 수 있습니까? –

 관련 문제

  • 관련 문제 없음^_^