Author Topic: yacc expert? rule useless in parser due to conflicts  (Read 458 times)

0 Members and 1 Guest are viewing this topic.

Offline legacy

  • Super Contributor
  • ***
  • Posts: 3638
  • Country: 00
yacc expert? rule useless in parser due to conflicts
« on: February 11, 2019, 09:52:37 am »
Code: [Select]
prog:   lines
                ;

lines:                                  { list_line(); unknown = dcflag = 0; }  /* reset flags */
                | line                  { list_line(); unknown = dcflag = 0 ; } /* on every new line */
                | lines '\n'    { list_line(); unknown = dcflag = 0; }
                | lines line    { list_line(); unknown = dcflag = 0; }
                | lines error   { list_line(); unknown = dcflag = 0; }
                ;

line:
                | defsym                                                /* define symbol (label) */
                | stmnt                                                 /* opcode */
                | defcon                                                /* build-in defines */
                | skip                                                  /* comment... */
                | prepro                                                /* preprocessor command */
                | END '\n'              { return(0); }
                ;

Code: [Select]
ass_pars.y:78.5: warning: rule useless in parser due to conflicts [-Wother]
 line:
     ^

cannot understand what is wrong  :-//
the Bunker is open!
(shortcut)
 

Offline sokoloff

  • Frequent Contributor
  • **
  • Posts: 931
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #1 on: February 11, 2019, 10:29:12 am »
I'm no yacc expert (and that's putting things mildly!), but I think your problem is that you have one too many "or"s in both lines and line, which makes for an ambiguous grammar.

Try this:
Code: [Select]
%token defsym stmnt defcon skip prepro END

%%prog:   lines
                ;

lines:                                  { list_line(); unknown = dcflag = 0; }  /* reset flags */
                  line                  { list_line(); unknown = dcflag = 0 ; } /* on every new line */
                | lines '\n'    { list_line(); unknown = dcflag = 0; }
                | lines line    { list_line(); unknown = dcflag = 0; }
                | lines error   { list_line(); unknown = dcflag = 0; }
                ;

line:
                  defsym                                                /* define symbol (label) */
                | stmnt                                                 /* opcode */
                | defcon                                                /* build-in defines */
                | skip                                                  /* comment... */
                | prepro                                                /* preprocessor command */
                | END '\n'              { return(0); }
                ;
%%
 

Offline sokoloff

  • Frequent Contributor
  • **
  • Posts: 931
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #2 on: February 11, 2019, 10:44:25 am »
Thinking about it a bit more, you might want to allow a line to be empty, but not a lines.

(And since a lines could just be a line, you'll get the same end result, but without the grammar ambiguity.)
 

Offline rhb

  • Super Contributor
  • ***
  • Posts: 2158
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #3 on: February 11, 2019, 10:54:28 am »
For openers that is not valid syntax.  That section should be enclosed by  lines which read:

%%

your stuff

%%

Besides that you have not defined your tokens;

Quote
rhb@Hipster:/export/home/rhb/wrk/yacc$ yacc tst.y
"tst.y", line 21: fatal: undefined nonterminal: defsym
"tst.y", line 21: fatal: undefined nonterminal: stmnt
"tst.y", line 21: fatal: undefined nonterminal: defcon
"tst.y", line 21: fatal: undefined nonterminal: skip
"tst.y", line 21: fatal: undefined nonterminal: prepro
"tst.y", line 21: fatal: undefined nonterminal: END

Try this:
Code: [Select]

%token defsym stmnt defcon skip prepro END

%%
prog:   lines
                ;

lines:                                  { list_line(); unknown = dcflag = 0; }  /* reset flags */
                | line                  { list_line(); unknown = dcflag = 0 ; } /* on every new line */
                | lines '\n'    { list_line(); unknown = dcflag = 0; }
                | lines line    { list_line(); unknown = dcflag = 0; }
                | lines error   { list_line(); unknown = dcflag = 0; }
                ;

line:
                | defsym                                                /* define symbol (label) */
                | stmnt                                                 /* opcode */
                | defcon                                                /* build-in defines */
                | skip                                                  /* comment... */
                | prepro                                                /* preprocessor command */
                | END '\n'              { return(0); }
                ;

%%

Quote
rhb@Hipster:/export/home/rhb/wrk/yacc$ yacc tst.y
1 rules never reduced

conflicts: 20 shift/reduce, 4 reduce/reduce

That's pretty typical output.

I have not used lex and yacc in 27 years, so to say I'm rusty would be an understatement.  In fact, about this time 27 years ago I was wrapping up 6 weeks spent learning lex and yacc..

A few weeks later I got my first contract job with a major oil company.  As it happened my first assignment was a parser.  I finished it in 2 weeks working about 1/2 time and doing other things the rest of the time.  The project leader had allocated 2 months for the parser.  From then on I walked on water.

What are you using for a reference?  "The Unix Programming Environment" by Kernighan and Pike has a good intro to lex and yacc.   I have several feet of books on compilers, regular expressions, parsers etc.  So I can only guess what I used 27 years ago besides K&P.  But these look likely:

Introduction to Compiler Construction with Unix
Schreiner & Freeman

Lex & Yacc
Levine, Mason & Brown

I strongly urge you to work through the 4 banger calculator in K&P.
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 3638
  • Country: 00
Re: yacc expert? rule useless in parser due to conflicts
« Reply #4 on: February 11, 2019, 11:32:57 am »
The above is not the complete source, it's too long.

Code: [Select]
prog:   lines
                ;

lines:                                  { list_line(); unknown = dcflag = 0; }  /* reset flags */
                | line                  { list_line(); unknown = dcflag = 0 ; } /* on every new line */
                | lines '\n'    { list_line(); unknown = dcflag = 0; }
                | lines line    { list_line(); unknown = dcflag = 0; }
                | lines error   { list_line(); unknown = dcflag = 0; }
                ;

line:
                | defsym                                                /* define symbol (label) */
                | stmnt                                                 /* opcode */
                | defcon                                                /* build-in defines */
                | skip                                                  /* comment... */
                | prepro                                                /* preprocessor command */
                | END '\n'              { return(0); }
                ;

Now, it compiles without working (it seems sensible to TABs), but the whole source.y needs to be rewritten in a neat way.

Code: [Select]
# make
yaccompiling ass_pars.y
compiling ass_pars.c
compiling main.c
compiling misc.c
compiling symbol.c
compiling ass_lex.c
building out/as11

it's an assembly compiler. For the next project, I will consider above-suggested books.
Thanks, guys  :D
the Bunker is open!
(shortcut)
 

Offline sokoloff

  • Frequent Contributor
  • **
  • Posts: 931
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #5 on: February 11, 2019, 11:43:22 am »
Don't start every rule with a pipe.

Right now a "nothing" matches both the lines and line rules. You don't want that.
I think you might also want to allow a blank line to be a line (and so it would match as a lines and a line and not a lines and a '\n', thereby deleting the lines '\n' rule)
 

Offline rhb

  • Super Contributor
  • ***
  • Posts: 2158
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #6 on: February 11, 2019, 03:02:50 pm »
Don't start every rule with a pipe.

Right now a "nothing" matches both the lines and line rules. You don't want that.
I think you might also want to allow a blank line to be a line (and so it would match as a lines and a line and not a lines and a '\n', thereby deleting the lines '\n' rule)

It's *not* a pipe. BNF notation is *not* the Unix shell!!!! The "|" is an "or" in yacc.

 It's an allowed instance.  In regular expression notation it's the equivalent of '(A|B|C|D)'  written differently.
 

Offline sokoloff

  • Frequent Contributor
  • **
  • Posts: 931
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #7 on: February 11, 2019, 11:55:31 pm »
It's *not* a pipe.
It sure as hell is a pipe character! That it's not a Unix pipe (nor a copper pipe) is irrelevant.
BNF notation is *not* the Unix shell!!!! The "|" is an "or" in yacc.
No shit; really? I had no idea. I must have just accidentally mistyped when I called it an "or" in my first response, which then seemed to be not clearly understood, so I called the character in concern a "pipe" in the later response to draw attention to the change I made to eliminate the ambiguous grammar rule warning:
I think your problem is that you have one too many "or"s in both lines and line, which makes for an ambiguous grammar.

In regular expression notation it's the equivalent of '(A|B|C|D)'  written differently.
Agreed (and previously understood). The concern is that the rules above have (|A|B|C|D) being a "lines" and (|E|F|G|H) being a "line", with the leading empty case on both, which leads to ambiguity in the grammar.
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 3638
  • Country: 00
Re: yacc expert? rule useless in parser due to conflicts
« Reply #8 on: February 12, 2019, 12:48:06 am »
Code: [Select]
prog:   lines
        ;

lines:
         /* empty line */      { list_line(); unknown=0; dcflag=0; }
                               /* on every new line */
//      | line                 { list_line(); unknown=0; dcflag=0; }
        | lines '\n'           { list_line(); unknown=0; dcflag=0; }
        | lines line           { list_line(); unknown=0; dcflag=0; }
        | lines error          { list_line(); unknown=0; dcflag=0; }
        ;

line:
          defsym                /* define symbol (label) */
        | stmnt                 /* opcode */
        | defcon                /* build-in defines */
        | skip                  /* comment... */
        | prepro                /* preprocessor command */
        | END                   { return(0); }
//      | END '\n'              { return(0); }
        ;

does this look better? it compiles without warning, and the resulting compiled module passes all the test cases.

Code: [Select]
; do you like a comment?

PORTA           equ             $00                             ; Port A Date Register
PACTL           equ             $26                             ; Port A Control Register
SPCR            equ             $28                             ; Control Register
BAUD            equ             $2b                             ; SCI Baud Rate Register
SCSR            equ             $2e                             ; SCI Status Register
SCDAT           equ             $2f                             ; SCI Date Register
HPRIO           equ             $3c                             ; Mode Register

offset          equ             $a0                             ; start
len                     equ             $a2                             ;

                        org             $0000                   ;

getbyte         brclr   #$20,SCSR,x,*   ;
                        ldaa    SCDAT,x                 ;
                        staa    0,y                             ;
                        ldaa    0,y                             ;
                        iny
                        brclr   #$c0,SCSR,x,*   ; Tranceiver Ready
                        staa    SCDAT,x                 ; Echo
                        rts

delay           ldy             #$ffff
delayloop       dey
                        nop
                        bne             delayloop
                        rts

                        end

The grammar understands the source, and the compiler is correctly able to compile it.
(yes, I know there is GNU AS, GAS/11, but it's not directly compatible with Motorola Macro Assembly/11)
the Bunker is open!
(shortcut)
 

Offline sokoloff

  • Frequent Contributor
  • **
  • Posts: 931
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #9 on: February 12, 2019, 01:04:23 am »
does this look better? it compiles without warning, and the resulting compiled module passes all the test cases.
Yup looks good.
The grammar understands the source, and the compiler is correctly able to compile it.
(yes, I know there is GNU AS, GAS/11, but it's not directly compatible with Motorola Macro Assembly/11)
Good deal!  :-+
 

Offline legacy

  • Super Contributor
  • ***
  • Posts: 3638
  • Country: 00
Re: yacc expert? rule useless in parser due to conflicts
« Reply #10 on: February 12, 2019, 08:09:01 am »
it has a defect

this works
Code: [Select]
org       $0000
 anda    #$00
 end

this does not work
Code: [Select]
org       $0000
anda    #$00
end

file guineapig2.s (1): syntax error
org       $0000


lines must begin with a space, otherwise the yy_lex doesn't work correctly.
the Bunker is open!
(shortcut)
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf