LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
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-04-2010, 03:06 AM   #1
dayalan_cse
Member
 
Registered: Oct 2006
Posts: 124

Rep: Reputation: 15
Yacc conflicts - How to understand grammar conflict


Hello,

I am getting shift/reduce and reduce/reduce conflict in my yacc grammar code.

yacc generates (i.e yacc -d -v parser.y) its grammar and state information in the parser.output file.

How can i interpret the below information and understand which grammar state is conflicting with other grammar state? Please help me to understand.


State 159 conflicts: 1 shift/reduce
State 1863 conflicts: 1 shift/reduce
State 1865 conflicts: 1 shift/reduce
State 1960 conflicts: 1 shift/reduce
 
Old 06-04-2010, 12:52 PM   #2
ForzaItalia2006
Member
 
Registered: Dec 2009
Location: Walldorf, Germany
Distribution: (X)Ubuntu, Arch, Gentoo
Posts: 205

Rep: Reputation: 67
Hey,

Quote:
Originally Posted by dayalan_cse View Post
yacc generates (i.e yacc -d -v parser.y) its grammar and state information in the parser.output file.
Why don't you use bison? I think this is more common nowadays in Linux environments.

Quote:
Originally Posted by dayalan_cse View Post
How can i interpret the below information and understand which grammar state is conflicting with other grammar state? Please help me to understand.
Well, I'm not sure how familiar you are with grammars and the specifics of shift/reduce parsers, but this error tries to tell you that there is one (or several states) wherein the parser can't determine if it should reduce the symbols on the stack or if it should shift the current symbol.

Quote:
Originally Posted by dayalan_cse View Post
State 159 conflicts: 1 shift/reduce
State 1863 conflicts: 1 shift/reduce
State 1865 conflicts: 1 shift/reduce
State 1960 conflicts: 1 shift/reduce
If I remember correctly from bison debugging output, you should check first of all which rules are in the states mentioned above and then check which rule specifically causes the problems.

What kind of grammar did you build? A programming language?

Andi
 
Old 06-05-2010, 02:01 AM   #3
ArthurSittler
Member
 
Registered: Jul 2008
Distribution: Slackware
Posts: 124

Rep: Reputation: 30
examine state table using -v switch

Use the -v switch will make yacc dump the entire state table. When you do this, redirect the output of yacc into a file so that you can examine the state table.

yacc and bison create state tables with a state for each possible step of progress through each production in the grammar. In those cases where there are multiple productions which can lead through the same sequence of nonterminals and tokens, those sequences will be merged. yacc will then look at the next token to decide which available alternative of different grammar productions it should chooses.

Each state is assigned an arbitrary but unique number. Each state is represented by a table of state numbers to which the parser will transition indexed by the token number of the next (i.e., the lookahead) token. Associated with each state is a sequence of nonterminals and tokens that yacc has shifted. The numbers in the error messages are the state numbers of the states where yacc is unable to choose whether it should shift the next token or reduce the shifted tokens to a nonterminal.

Remember that yacc is lalr(1). That is, it can only look at one single lookahead token from the scanner to decide whether to shift the token or reduce the sequence of shifted tokens to a nonterminal. The lookahead token could be the initial token in some sequence that could reduce to something that follows some nonterminal to which some sequence on the top of the sequence could reduce. Or it could be the next token of some other sequence into which some other sequence of nonterminals and tokens at the top of the parse stack could be reduced.

If, for some state, for some single lookahead token, there is both a possibility to shift that token and a possibility to reduce to a nonterminal, then there is a shift/reduce conflict for that state.

If, for some state, for some single lookahead token, there are two different nonterminals into which the parser could reduce some sequence of nonterminals and terminals from the top of the stack, then there is a reduce/reduce conflict.

Once you know what sequence of tokens and nonterminals yacc has seen to get into the state with the shift/reduce conflict, you can look through your grammar to find what productions share the sequence of tokens and nonterminals.

The classical reference for compiler writing using lex and yacc is Compilers Principles, Techniques, and Tools, by Aho, Sethi, and Ullman ISBN 0-201-10088-6. This is commonly known as "The Dragon Book". Though it was published back in 1986, it is still a standard reference for the subject. As you will find by searching the web, there are more modern tools including lalr(k) parser generators with arbitrary (usually very small) k.
 
1 members found this post helpful.
Old 06-14-2010, 12:20 AM   #4
dayalan_cse
Member
 
Registered: Oct 2006
Posts: 124

Original Poster
Rep: Reputation: 15
Quote:
Originally Posted by ForzaItalia2006 View Post
Hey,



Why don't you use bison? I think this is more common nowadays in Linux environments.



Well, I'm not sure how familiar you are with grammars and the specifics of shift/reduce parsers, but this error tries to tell you that there is one (or several states) wherein the parser can't determine if it should reduce the symbols on the stack or if it should shift the current symbol.



If I remember correctly from bison debugging output, you should check first of all which rules are in the states mentioned above and then check which rule specifically causes the problems.

What kind of grammar did you build? A programming language?

Andi

Hi Andi,

thanks for your information.

What is the difference between yacc and bison? which one is latest?

Thanks,
Deenadayalan
 
Old 06-14-2010, 12:23 AM   #5
dayalan_cse
Member
 
Registered: Oct 2006
Posts: 124

Original Poster
Rep: Reputation: 15
Quote:
Originally Posted by ArthurSittler View Post
Use the -v switch will make yacc dump the entire state table. When you do this, redirect the output of yacc into a file so that you can examine the state table.

yacc and bison create state tables with a state for each possible step of progress through each production in the grammar. In those cases where there are multiple productions which can lead through the same sequence of nonterminals and tokens, those sequences will be merged. yacc will then look at the next token to decide which available alternative of different grammar productions it should chooses.

Each state is assigned an arbitrary but unique number. Each state is represented by a table of state numbers to which the parser will transition indexed by the token number of the next (i.e., the lookahead) token. Associated with each state is a sequence of nonterminals and tokens that yacc has shifted. The numbers in the error messages are the state numbers of the states where yacc is unable to choose whether it should shift the next token or reduce the shifted tokens to a nonterminal.

Remember that yacc is lalr(1). That is, it can only look at one single lookahead token from the scanner to decide whether to shift the token or reduce the sequence of shifted tokens to a nonterminal. The lookahead token could be the initial token in some sequence that could reduce to something that follows some nonterminal to which some sequence on the top of the sequence could reduce. Or it could be the next token of some other sequence into which some other sequence of nonterminals and tokens at the top of the parse stack could be reduced.

If, for some state, for some single lookahead token, there is both a possibility to shift that token and a possibility to reduce to a nonterminal, then there is a shift/reduce conflict for that state.

If, for some state, for some single lookahead token, there are two different nonterminals into which the parser could reduce some sequence of nonterminals and terminals from the top of the stack, then there is a reduce/reduce conflict.

Once you know what sequence of tokens and nonterminals yacc has seen to get into the state with the shift/reduce conflict, you can look through your grammar to find what productions share the sequence of tokens and nonterminals.

The classical reference for compiler writing using lex and yacc is Compilers Principles, Techniques, and Tools, by Aho, Sethi, and Ullman ISBN 0-201-10088-6. This is commonly known as "The Dragon Book". Though it was published back in 1986, it is still a standard reference for the subject. As you will find by searching the web, there are more modern tools including lalr(k) parser generators with arbitrary (usually very small) k.
Hi,

Thanks for your inputs and it helped me to understand.

If we have such a big grammar for a given language, how to trace and figure out the conflicting between two non-terminals or a token (shift) and non-terminal?

Any debugging tool available to debug this shift/shift & reduce/reduce problems except going through the <yyparse>.output whole grammar?

Thank you for your inputs in advance.

Thanks,
Deenadayalan
 
Old 06-15-2010, 02:05 AM   #6
ArthurSittler
Member
 
Registered: Jul 2008
Distribution: Slackware
Posts: 124

Rep: Reputation: 30
look at progress string for conflicting state

Bison is the GNU free replacement for yacc. It has some additional features and possibly improved performance. It also had a somewhat restrictive license in that, if you use bison, any program generated by using that tool must also be made as freely available as the tool. Byacc is another version which requires that any program generated using it must acknowledge the copyright holders. I do not find any of the license restrictions onerous.

The states dumped by the -v command each have associated parse progress indicator comments and state numbers. The parse progress indicator shows what productions you might be trying to reduce in that state. The error messages tell you which states to look at for the problem. You may be able to look at the states and recognize which productions are causing the conflicts.

The brute-force method to debugging yacc conflicts is also the gentlest approach: start with some small but reasonable subset of the grammar. For compilers, this could be expressions, for instance. Also build a test input file which includes only the subset of the language accepted by the parser. You can add actions to the parser as you accumulate working grammar, or add the actions later. Then as you add more and more productions, you will start encountering conflicts. Along with the conflict error messages, this incremental development of the grammar will show you which productions cause the conflicts.

I start the whole process with a scanner generated using flex, the replacement for lex. I build a file including every token that the scanner should recognize and test the scanner with a test driver main() function. I enclose the main() in preprocessor conditionals so I can turn it off after the scanner accepts the test language file.

A makefile which invokes lex, yacc, cc, etc. helps me with the build process. I consider it indispensable. I do not believe I could ever actually remember all the command line switches. Don't forget to link in the libraries associated with flex and bison. But you must have gotten past that if you are up to the point of conflicts.
 
Old 06-15-2010, 08:04 AM   #7
MTK358
LQ 5k Club
 
Registered: Sep 2009
Posts: 6,443
Blog Entries: 3

Rep: Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714Reputation: 714
He was probably using Bison (it comes with most Linux distros). "yacc" is a symlink to "bison" in most Linux installations.
 
  


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
Grammar Kenny_Strawn General 85 03-28-2010 07:46 PM
Processing Conflict: python-devel conflicts python< 2.3.4-13.1 guarriman Fedora 2 04-23-2009 07:02 PM
yacc grammar and its corresponding lex specification for designing C Compiler aashish Linux - Software 4 10-14-2008 02:22 AM
IP conflict messages when there really are no conflicts SlackDaemon Linux - Networking 2 08-19-2006 10:45 PM
Help with grammar Mr. New General 3 06-09-2005 06:16 AM


All times are GMT -5. The time now is 09:24 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
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration