shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
|
View:
New views
12 Messages
—
Rating Filter:
Alert me
|
 |
shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by osama abdelwahed
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by osama abdelwahed
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Simon Richter-2
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Hisashi Nakai
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Etienne M. Gagnon
::
Rate this Message:
Without your translated version, it is hard to tell. If the only LALR(1) conflict in the original grammar is the if/else shift-reduce conflict, then the usual stmt-noif solution should have eliminated all conflicts. So, either there was a little mistake in the solution, either the original grammar had additional conflicts. SableCC 2 and 3 are effectively LALR(1). Actually, SableCC 3 does even automatically resolve some LALR(1) conflicts by inlining conflicting productions. My recommendation is to check your stmt-noif transformations and also verify that the original Yacc warning report didn't include additional conflicts. SableCC only reports the first conflict it finds. Have fun! Etienne Hisashi Nakai a écrit : Hi, I tried to translate a C grammar for yacc into sablecc's one. The original one I have can be got from http://www.csd.uwo.ca/~watt/home/courses/2008-09/cs4447a/parts/ansi-c-grammar/gram.y # I got it from the internet using ftp some little time ago... It includes one shift/reduce conflict, which is made from dangling- else. I translated straightforwardly, but I met some messages about conflicts maybe they do not look like the same for dangling-else's one. I think it is an LALR(1) grammar, and, the both yacc and sablecc are based on LALR(1), then I think the sablecc should accept as yacc (of course, except for one shift/reduce conflict). Can someone help this or tell me the pointer to refer about this problem ? Thanks in advance. In Message-ID: 20090103185117.GA25981@... Simon Richter Simon.Richter@... wrote : -- Etienne M. Gagnon, Ph.D. SableCC: http://sablecc.org _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Hisashi Nakai
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Etienne M. Gagnon
::
Rate this Message:
Hi Hisashi,
I see a little discrepancy in your translation. In the Yacc grammar, there are two types of type name:
shift/reduce conflict in state [stack: TAsterisk *] on TVoid in {
[ PPointer = TAsterisk * ] followed by TVoid (reduce),
[ PTypeSpecifier = * TVoid ] (shift)
}
It seems that the Yacc grammar uses the usual hack, letting the lexer
distinguish between an identifier and a type name.Have fun! Etienne PS: Please do not CC me. I am already subscribed to the mailing-list! Hisashi Nakai wrote : I removed the if-else rule and then yacc did not issue any message. -- Etienne M. Gagnon, Ph.D. SableCC: http://sablecc.org _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Hisashi Nakai
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by krischan83
::
Rate this Message:
|
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Etienne M. Gagnon
::
Rate this Message:
Hi Hisashi,
SableCC 3 removed the filter() method from the parser class due to its incompatibility with CST->AST transformations. In other words, SableCC 3's Parser class is not customizable.By the way, in your master thesis, there is the explanation about node variable in chapter 5, but in version 3.2, it does not seem to exist in Parser class. I found nodeList variable instead. Is it right to use it as node variable ? I won't go into the details, but it would be a hell to try to fix SableCC 3 to offer a well designed filter() method. SableCC 4 has investigators which lets custom user code investigate subtrees while parsing. It also has semantic selectors to allow user code to select among productions based on semantics. In other words, SableCC 4 has a clean solution for this, but it will not reintroduce the filter method. But it is not yet available... So, your only immediate solution is to go back to using SableCC 2, which provides the filter() method, which is required for the ANSI C lexer/parser hack. WARNING: Do not forget that the parser is ALWAYS one token ahead, in SableCC 2. This means that if you want to build a typedef table, you must make sure to get your REDUCE before the ";" of the typedef declaration, so that the typedef is in effect for any identifier that follows the ";". E.g. ... typedef int myint; myint x = 3; ...As the parser is LALR(1), it must look at the next token before making the reduction. The following grammar would fail to achieve what you want: ... typedef_decl = typedef_keyword ... semicolon; ...To reduce typedef_decl, the parser asks the lexer for the token that follows semicolon, so it gets "myint", an identifier which is not a typename (not yet in the typedef table)! To avoid this, make sure the the semicolon is the token that follows the reduction used by the filter() method. As you see, all this is quite tricky. That's why I put a lot of work in designing clean mechanisms to use semantics for parsing decisions in SableCC 4, while protecting users from such low-level worries as the lookahead problem. Yacc accepts shift/reduce conflict as it takes shift rather than reduce. In the future, can sablecc treat shift/reduce conflict as yacc (or user can select) ? I've already answered this somewhere the archives. In a few words, in SableCC 4 you can write: stmt = {if} if_token exp then_token stmt Dangling else_stmt |
...;
Dangling else_stmt = else_token stmt;
This is different from Yacc in that it is an explicit grammar
disambiguation directive, not a parsing-algorithm-specific conflict
resolution directive. It is backed on a formal proof that the language
is not modified (it only selects among the multiple parse trees of the
language). In other words, it does not come with unexpected side
effects.Etienne -- Etienne M. Gagnon, Ph.D. SableCC: http://sablecc.org _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Etienne M. Gagnon
::
Rate this Message:
Hi Christian,
If I understood correctly, Hishashi's trying to take the usual approach of detecting typedef's while parsing, and using this information in the lexer to discriminate between identifiers and type names. This can be implemented in SableCC 2 by overriding the filter() methods of both Lexer and Parser classes. This is tricky, but it works if done carefully. Etienne krischan83 wrote: > I think about to hack the token stream provided by the lexer... > > Does anybody have experiences with such a way? > -- Etienne M. Gagnon, Ph.D. SableCC: http://sablecc.org _______________________________________________ SableCC-Discussion mailing list SableCC-Discussion@... http://lists.sablecc.org/listinfo/sablecc-discussion |
|
|
Re: shift/reduce and reduce/reduce conflict in ANSI C Yacc grammar
by Hisashi Nakai
::
Rate this Message:
|
signature.asc (265 bytes) | Free embeddable forum powered by Nabble | Forum Help |
