Re: Reduce/Reduce conflict in Algol60 grammar

Andru Luvisi <luvisi@andru.sonoma.edu>
11 Oct 2006 23:21:33 -0400

          From comp.compilers

Related articles
Reduce/Reduce conflict in Algol60 grammar leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-10-10)
Re: Reduce/Reduce conflict in Algol60 grammar luvisi@andru.sonoma.edu (Andru Luvisi) (2006-10-11)
Re: Reduce/Reduce conflict in Algol60 grammar idknow@gmail.com (idknow@gmail.com) (2006-10-11)
Re: Reduce/Reduce conflict in Algol60 grammar wyrmwif@tsoft.org (SM Ryan) (2006-10-11)
Re: Reduce/Reduce conflict in Algol60 grammar cfc@shell01.TheWorld.com (Chris F Clark) (2006-10-12)
Re: Reduce/Reduce conflict in Algol60 grammar wyrmwif@tsoft.org (SM Ryan) (2006-10-13)
Re: Reduce/Reduce conflict in Algol60 grammar kenrose@nc-sys.com (Ken Rose) (2006-10-14)
Re: Reduce/Reduce conflict in Algol60 grammar bobduff@shell01.TheWorld.com (Robert A Duff) (2006-10-14)
[2 later articles]
| List of all articles for this month |

From: Andru Luvisi <luvisi@andru.sonoma.edu>
Newsgroups: comp.compilers
Date: 11 Oct 2006 23:21:33 -0400
Organization: Compilers Central
References: 06-10-036
Keywords: algol60, parse

>>>>> "Leonardo" == Leonardo Teixeira Passos <leonardo@dcc.ufmg.br> writes:


        Leonardo> Note the common part between primary and
        Leonardo> boolean_primary, which leads to the conflict. The only
        Leonardo> way that I could resolve this was to merge
        Leonardo> arithmetic_expression and boolean_expression, respecting
        Leonardo> the precedence estabelished, and then distinguish them
        Leonardo> through semantic actions.


I seem to recall that this was the standard solution in the 1960s. The
trouble is that it makes perfect sense for numbers and arithmetic
operators to be in a boolean expression.


For example, consider "i + 3*j > 100". You can't tell that it might
be a boolean expression until you get to the ">".


If you're really interested, you could check out "Computing: A Human
Activity" by Peter Naur, "Algol 60 Implementation" by Randell and
Russell, and "Programming Systems and Languages" edited by Rosen.
Also, Dijkstra wrote a couple of interesting papers on Algol 60
compilation:
        http://www.cs.utexas.edu/users/EWD/MCReps/MR35.PDF


The Naur book contains some papers that go into detail about the type
checking. The compiler described didn't build syntax trees. It did
"pseudo evaluation" where at compile time it would perform all of the
operations using a stack, but instead of actual values, all that was
stuck on the stack was type identifiers. An expression could be
"pseudo evaluated" and if at any point an operator was applied while
invalid types were on the stack, it was a type error. Also, the final
type of the expression could be determined by looking at the last type
left on the stack when the pseudo evaluation was finished.


Best of luck,
Andru
--
Andru Luvisi


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.