[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Error in GLR parser

From: ihusar
Subject: Error in GLR parser
Date: Tue, 16 Mar 2010 10:48:49 +0100
User-agent: Opera Mail/10.01 (Linux)


  I am using bison with GLR parser to generate assembly language parser
which is then used in retargetable assembler.
For sources of parser in attachment, the GLR parser ends with an error.
There are 9 reduce-reduce collisions in the grammar.

Error occures while parsing following text:
"mov 4 , A \n"

scanner returns these tokens:

and the rules that should be matched are these (some names are automatically generated):

start: start ynt_gen_start T_NEWLINE
ynt_gen_start: instrbase_instr_set_0
instrbase_instr_set_0: instrbase2_instr_set_0
instrbase2_instr_set_0: ynt_aut__0__0
ynt_aut__0__0: ynt_aut_opc_badr2AR_C_0_439__0 expr T_DELIM YT_11_
ynt_aut_opc_dadr2AR_ACC_0_409__0: YT_0_

//expr is defined as this
expr: expr1
expr1: expr1 T_OP_BIN_OR expr2
| expr2
expr2: expr2 T_OP_BIN_XOR expr3
| expr3
expr3: expr3 T_OP_BIN_AND expr4
| expr4
expr4: expr4 T_OP_LSHIFT expr5
| expr4 T_OP_RSHIFT expr5
| expr5
expr5: expr5 T_OP_PLUS expr6
| expr5 T_OP_MINUS expr6
| expr6
expr6: expr6 T_OP_MULT expr7
| expr6 T_OP_DIV expr7
| expr6 T_OP_MOD expr7
| expr7
expr7: T_OP_NEG expr8
| T_OP_BIN_NEG expr8
| T_OP_PLUS expr8
| T_OP_MINUS expr8
| expr8
expr8: const_num
| id_token

const_num: T_NUM_PREFIX const_num_basic
| const_num_basic

        : T_DEC_CONST
        | T_HEX_CONST


The problem, at kleast what seems to me strange, is here:

Starting parse
Entering state 0
Reducing stack 0 by rule 4 (line 123):
-> $$ = nterm start ()
Entering state 1
Reading a token: Next token is token YT_0_ ()
Shifting token YT_0_ ()
Entering state 13
Reading a token: Next token is token T_DEC_CONST ()
Stack 0 Entering state 13 <<-------------------------------------we are in state 13
Next token is token T_DEC_CONST ()
Splitting off stack 1 from 0.
Reduced stack 1 by rule #131; action deferred. Now in state 56. <----------- here we get to states 56 and 54
Stack 1 Entering state 56
Next token is token T_DEC_CONST ()
Reduced stack 0 by rule #120; action deferred. Now in state 54. <-----------

However, there is no transition from state 13 to state 56 or 54:

state 13

   74 ynt_aut__0__0: YT_0_ . YT_17_ ynt_aut_Ri_0_397__0 T_DELIM expr
   75              | YT_0_ . ynt_aut_Rn_0_378__0 T_DELIM expr
   76              | YT_0_ . YT_11_ T_DELIM expr
   97              | YT_0_ . YT_17_ ynt_aut_Ri_0_397__0 T_DELIM YT_11_
   98              | YT_0_ . ynt_aut_Rn_0_378__0 T_DELIM YT_11_
   99              | YT_0_ . YT_11_ T_DELIM YT_17_ ynt_aut_Ri_0_397__0
  100              | YT_0_ . YT_11_ T_DELIM ynt_aut_Rn_0_378__0
  120 ynt_aut_opc_badr2AR_C_0_439__0: YT_0_ .
  124 ynt_aut_opc_badr2AR_0_420__0: YT_0_ . YT_3_ T_DELIM
  131 ynt_aut_opc_dadr2AR_ACC_0_409__0: YT_0_ .

    YT_3_   shift, and go to state 84
    YT_11_  shift, and go to state 85
    YT_15_  shift, and go to state 86
    YT_16_  shift, and go to state 87
    YT_17_  shift, and go to state 88
    YT_18_  shift, and go to state 89
    YT_19_  shift, and go to state 90
    YT_20_  shift, and go to state 91
    YT_21_  shift, and go to state 92
    YT_22_  shift, and go to state 93
    YT_23_  shift, and go to state 94

    T_ID          reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_ID [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_DEC_CONST   reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_DEC_CONST [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_HEX_CONST   reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_HEX_CONST [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_NUM_PREFIX  reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_NUM_PREFIX [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_OP_NEG      reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_OP_NEG [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_OP_BIN_NEG  reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_OP_BIN_NEG [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_OP_PLUS     reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_OP_PLUS [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_OP_MINUS    reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_OP_MINUS [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    T_PAR_LEFT    reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)
T_PAR_LEFT [reduce using rule 131 (ynt_aut_opc_dadr2AR_ACC_0_409__0)]
    $default      reduce using rule 120 (ynt_aut_opc_badr2AR_C_0_439__0)

    ynt_aut_Rn_0_378__0  go to state 95

And while parsing, the token "A" (YT_11_) is parsed with rule
const_num_basic: T_DEC_CONST and this writes following error from semantic action, where we convert yytext to a number.

***Error while converting constant "A" (dec).

All the needed sources are added as attachment and can be compiled with script c.sh.

Best regards
  Adam Husar

Attachment: c.sh
Description: Binary data

Attachment: lexan_merged_gen.l
Description: Binary data

Attachment: syntan_merged_gen.yy
Description: Binary data

Attachment: main.cpp
Description: Binary data

Attachment: 8051.asm
Description: Binary data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]