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

0 Members and 1 Guest are viewing this topic.

Offline legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
yacc expert? rule useless in parser due to conflicts
« on: February 10, 2019, 10:52:37 pm »
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  :-//
 

Offline sokoloff

  • Super Contributor
  • ***
  • Posts: 1799
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #1 on: February 10, 2019, 11:29:12 pm »
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

  • Super Contributor
  • ***
  • Posts: 1799
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #2 on: February 10, 2019, 11:44:25 pm »
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: 3476
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #3 on: February 10, 2019, 11:54:28 pm »
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 legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: yacc expert? rule useless in parser due to conflicts
« Reply #4 on: February 11, 2019, 12:32:57 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); }
                ;

it seems sensible to TABs, Now, it compiles without wornings, 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
« Last Edit: October 21, 2019, 09:09:27 pm by legacy »
 

Offline sokoloff

  • Super Contributor
  • ***
  • Posts: 1799
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #5 on: February 11, 2019, 12: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: 3476
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #6 on: February 11, 2019, 04:02:50 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)

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

  • Super Contributor
  • ***
  • Posts: 1799
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #7 on: February 11, 2019, 12: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 legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: yacc expert? rule useless in parser due to conflicts
« Reply #8 on: February 11, 2019, 01:48:06 pm »
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)
 

Offline sokoloff

  • Super Contributor
  • ***
  • Posts: 1799
  • Country: us
Re: yacc expert? rule useless in parser due to conflicts
« Reply #9 on: February 11, 2019, 02:04:23 pm »
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 legacyTopic starter

  • Super Contributor
  • ***
  • !
  • Posts: 4415
  • Country: ch
Re: yacc expert? rule useless in parser due to conflicts
« Reply #10 on: February 11, 2019, 09:09:01 pm »
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.
 

Offline mrflibble

  • Super Contributor
  • ***
  • Posts: 2051
  • Country: nl
Re: yacc expert? rule useless in parser due to conflicts
« Reply #11 on: March 04, 2019, 01:33:25 am »
it has a defect
...
lines must begin with a space, otherwise the yy_lex doesn't work correctly.

Disclaimer: It's been a few years since I last lexed a yacc.  :horse:

Now with that out of the way ...

In the definition of lines, the handling of newline struck me as somewhat odd. When you get a situation like this where whitespaces are required at the start/end of line, without this being the design intent, that's usually a hint. The hint being that maybe the handling of newlines and whitespaces might need some attention.

Code: [Select]
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; }    // <== That one.
        | lines line           { list_line(); unknown=0; dcflag=0; }
        | lines error          { list_line(); unknown=0; dcflag=0; }
        ;

Is there a specific reason you want that newline there? To the innocent bystander this comes across as organically grown code. Especially since later on in the definition of line you are playing around with '\n' as well.

Code: [Select]
line:
          defsym                /* define symbol (label) */
        | stmnt                 /* opcode */
        | defcon                /* build-in defines */
        | skip                  /* comment... */
        | prepro                /* preprocessor command */
        | END                   { return(0); }                  // <== Here.
//      | END '\n'              { return(0); }                  // <== And here.
        ;

Since the full code is not included there is no way to be sure, but I suspect that handling of whitespace and newlines with regard to tokenization might need a bit of polish.
 


Share me

Digg  Facebook  SlashDot  Delicious  Technorati  Twitter  Google  Yahoo
Smf