LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 06-28-2006, 05:36 PM   #1
IncendiaryProgrammer
LQ Newbie
 
Registered: Jun 2006
Posts: 11

Rep: Reputation: 0
Newbie Yacc/Bison shift reduce question


Hi.

Since yacc/bison only has 1 token of look-ahead, I expect a shift reduce conflict in the second "STRING IDEN ..." rule in the code segment pasted below, but I don't get one. Then in a similar situation, I get a shift reduce conflict! See fprintf(stdout, ..) statements below.

What's happening?

Thanks in advance!

Code:
/* Two questions about shift reduce conflicts found in fprintf(stdout, ..)
statements.  Thanks!!  */
 
/* ..... */
  |  DOUBLE IDEN becomes OBRACK number_list CBRACK {
      myasgn.name=$2;
      myasgn.vl=$5;
      myasgn.type=VECTOR;
      addAssign(myasgn);
      gotit=1;
    }
  |  STRING IDEN becomes OBRACK string_list CBRACK {
      myasgn.name=$2;
      myasgn.vl=$5;
      myasgn.type=VECTOR;
      addAssign(myasgn);
      gotit=1;
    }  
  |  STRING IDEN becomes EXTRACT CBRACK string_list {
      fprintf(stdout, "Why is there no shift reduce conflict here?!?!\n");
      /* assignLook($3)->assign; */
     }
  |  datatype IDEN becomes EXTRACT PLUS string_list {
      fprintf(stdout, "But there is a shift reduce conflict when I do this?!\n");
     }
  ;
 
 
datatype: LONG | DOUBLE | STRING | IVEC | FVEC | VECTOR | SCALAR
  ;
 
/* ...... */
Compiler complaints:
Code:
gparmod6.y: conflicts: 5 shift/reduce
gparmod6.y:171.11-14: warning: rule never reduced because of conflicts: datatype: LONG
gparmod6.y:171.18-23: warning: rule never reduced because of conflicts: datatype: DOUBLE
gparmod6.y:171.27-32: warning: rule never reduced because of conflicts: datatype: STRING
gparmod6.y:171.36-39: warning: rule never reduced because of conflicts: datatype: IVEC
gparmod6.y:171.43-46: warning: rule never reduced because of conflicts: datatype: FVEC
Note: the conflicts dissapear, as expected, if I change
datatype IDEN becomes ....

to
datatype EXTRACT IDEN becomes ...

so that yacc can use that token of look-ahead.

Last edited by IncendiaryProgrammer; 06-28-2006 at 05:50 PM.
 
Old 06-29-2006, 08:24 PM   #2
IncendiaryProgrammer
LQ Newbie
 
Registered: Jun 2006
Posts: 11

Original Poster
Rep: Reputation: 0
Aidez-moi s'il vous plait?

Any ideas?
 
Old 07-01-2006, 02:14 PM   #3
IncendiaryProgrammer
LQ Newbie
 
Registered: Jun 2006
Posts: 11

Original Poster
Rep: Reputation: 0
Any thoughts (even if they are guesses) would be appreciated... I haven't been able to find anything in the literature about why that "string iden.." rule wouldn't cause a conflict.
 
Old 07-01-2006, 05:41 PM   #4
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,610
Blog Entries: 4

Rep: Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905
Consider what decisions the parser must make and when it is obliged to make them...

In the first case, when we see "STRING IDEN becomes," then even though there are two possible rules that we could be following at this moment in time, there's only one thing that we must do: we must shift. It is not until the next symbol appears that we have narrowed things down to just one rule (OBRACK vs. EXTRACT), and even then we're still going to continue to shift.

However... if you introduce the fourth rule, a shift/reduce conflict immediately appears. When presented with the input stream "STRING IDEN," we could either shift that symbol onto the stack and proceed, as we did before, or we could reduce STRING to an instance of DATATYPE. The situation is ambiguous: a shift/reduce conflict.

When grokking parser problems, it's really important to understand how the parsing engine actually works: what information it is presented with (this information having been generated from the grammar), what its choices are (shift .. that is to say "push" .. or reduce), and how it will make that decision. The grammar is not the actual input that drives the engine: the parsing engine is a state-machine.
 
Old 07-01-2006, 06:52 PM   #5
IncendiaryProgrammer
LQ Newbie
 
Registered: Jun 2006
Posts: 11

Original Poster
Rep: Reputation: 0
What a helpful response, sundialsvcs! Thanks. If only there were karma so that I could give you some .
 
Old 07-02-2006, 11:15 AM   #6
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,610
Blog Entries: 4

Rep: Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905Reputation: 3905
You're welcome. I guess it always annoyed me, somehow, that parsers were made out to be so gosh-darned mysterious (and subsequently inflicted upon generations of grad-students) when they really are not.
  • A parser is a state-machine. In other words, it bounces from one "state" to another, doing different things based on its "state" and its "current input." This lets us build a very complicated algorithm using a very simple piece of code that's driven by a very intricate, but entirely machine-generated, table of constant numbers. All of the source-code, except those tables, fits very neatly on a couple of printed pages.
  • What it uses as its input is twofold: (1) a stack of symbols that it has recently seen; and (2) the "current symbol" that it is looking at right now. ("Scanners" are similar, but their input consists of characters.)
  • At any moment in time, a parser can do [only] one of two things: "shift" or "reduce." (Then, of course, it switches to some other state...)
  • Shift actually means "push." The current symbol is pushed onto the top of the stack. You do this when the current input-symbol is acceptable but, by itself, does not mean anything. The next symbol will be read, and the process begins again.
  • Reduce means to remove so-many symbols from the top of the stack and to replace it with just one. You do this when you "recognize" that the symbols you just removed "together, mean something significant." In this case the parser doesn't read another symbol right away, as it might perform several "reduces" in a row.
  • Usually, the parser gets to call some bit of C-code .. some subroutine, usually .. when it has recognized something.
  • The parser cannot do both a shift and a reduce at the same time. But if you write the grammar incorrectly, you can produce an ambiguous situation that would require it to do just that ... where either choice would be equally valid, and it's not possible to un-ambiguously decide what to do based on a single input-symbol. It's a fork in the road where either road is equally "correct." This ambiguous situation is called a shift/reduce conflict, and it is not allowed. You must design your grammar, and quite possibly your language, to prevent this.
  • If you get your jollies out of cryptic terminology like "LALR(0)," please take a moment to enjoy the zen-moment .. .. because the previous bullet-point is all that it really means. (The terms were, of course, invented by graduate students for use in their PhD theses ... and such documents were never meant to be, you know, read by mere mortals. )
  • The parser state-machine isn't actually "walking through the grammar" while it's doing its work. Rather, it is walking through a bunch of state-tables that have been generated from that grammar. Ordinarily you do not have to look closely at their contents.
  • And that's it! A comparatively simple process, and certainly a fast one, that has been couched in needlessly obscure phrases and force-fed to college students. To quickly understand it, start with the parser source-code and work backwards. "Use the Source, Luke!"

Last edited by sundialsvcs; 07-02-2006 at 11:19 AM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Yacc(Bison) Parameter Parsing -- Modifying a Scientific Programming Language! IncendiaryProgrammer Programming 3 06-23-2006 04:29 PM
Analyse of logs of a serial device (yacc/bison/flex..) fUNkYbOOStER Programming 0 06-21-2006 07:41 AM
Yacc/Bison question russinoff Programming 1 06-17-2006 01:54 PM
Bison and Yacc Compatibility Problem oulevon Programming 1 10-23-2005 10:56 PM
yacc, Bison Config Linux - General 6 02-21-2002 02:18 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 09:11 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration