Re: Semantic actions in Yacc ?

------ From frazerw@dseg.ti.com (Frazer Worley, #909980 DAD)
> I want to add semantic actions to a Yacc parser. The way I'd considered
> of doing this is to add actions before and after each nonterminal in
> the grammar, as I do not yet know where I'll need semantic checks and
> where I won't.
>
> eg. Consider a binary grammar.
>
> grammar : { SemanticBlk1() ; } digits { SemanticBlk2() ; }
> ;
>
> digits : /* empty */
> | {} digits {} digit {}
> ;
>
> digit : {} ZERO_TOK {}
> | {} ONE_TOK {}
> ;
>
> Now this causes reduce/reduce conflicts in Yacc. Is there a way to
> avoid this ? Or is there a better way to add semantic actions ?


Yes, you can avoid this by only adding semantic actions at the end of
productions. For most languages that is an acceptable limitation.
There are some notable exceptions, such as C, where the appropriate
time to declare an identifier before the end of the declaration
production. (It is also possible to rewrite the C grammar so that it
has a reduction at the point where the semantics are required, but it
does not look like the C grammar in the standard.)


However, if you start with the notion that you want to build a
representation of your program, then the most likely place where you
will want to build up the representation is at the end of each
production, since that is when you know what you are building.


Thus, the best course, is to assume no semantic actions until you have
established the points where you *need* them, and you cannot defer
them any longer without accepting illegal programs. If you follow
that course, you will probably not introduce any semantic actions
which introduce conflicts.


> I think I can translate this defn. into LL1 and generate a recursive
> descent parser - which won't have problems with the semantic actions.
> However - this would be a real undertaking for my target language
> [>300 productions] - so I was wondering whether an application exists
> to do this already - yacc2rdp or something ?


There are tools which translate yacc grammars into other formalisms.
If your grammar is not of the appropriate class for the tool, the tool
may or may not be able to tweak it into an appropriate grammar. (Most
grammars from standards committees are not LL (and many are not even
LR).)


However, having your grammar in LL form may not solve your semantic
action problem. If the grammar needs look-ahead at the point where
you want to insert a semantic check, you either have to defer the
check until the look-ahead is resolved or insert the check knowing
that it will be applied to some inappropriate fragments.


> Or, is there another compiler generator which I could use instead
> of Yacc which would enable me to do what I want ?


If you accept my definition of what you want, a tool which allows you
to put the semantics where you need (and perhaps automates much of
that process) there are numerous choices.


First, of all, yacc (or bison) will probably work just fine. You will
probably not *need* any semantics at locations which cause conflicts.


Or you could try a tool which automates more of the process. The
thing to look for in such a tool is the automatic construction of AST
classes for you. You will find tools which do that with varying
amounts of sophistication. The AST construction tools will all
generally be able to at least build a parse tree for you. [At last
years OOPSLA conference, I presented a paper on the AST construction
features of Yacc++(r) to the Workshop of OO Compilation. You can ftp
the papers from the workshop from everest.ee.umn.edu::/pub/oopsla.]


-Chris Clark


Compiler Resources, Inc.
85 Main St, Ste 310
Hopkinton, MA 01748


email: compres@world.std.com
voice: 1(508) 435-5016
fax: 1(508) 435-4847
--

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